Problem:


Score : 600 points

Problem Statement

We have a tree with N vertices. The i-th edge connects Vertex A_i and B_i bidirectionally.

Takahashi is standing at Vertex u, and Aoki is standing at Vertex v.

Now, they will play a game of tag as follows:

1. If Takahashi and Aoki are standing at the same vertex, the game ends. Otherwise, Takahashi moves to a vertex of his choice that is adjacent to his current vertex.

2. If Takahashi and Aoki are standing at the same vertex, the game ends. Otherwise, Aoki moves to a vertex of his choice that is adjacent to his current vertex.

3. Go back to step 1.

Takahashi performs his moves so that the game ends as late as possible, while Aoki performs his moves so that the game ends as early as possible.

Find the number of moves Aoki will perform before the end of the game if both Takahashi and Aoki know each other's position and strategy.

It can be proved that the game is bound to end.

Constraints

2 \leq N \leq 10^5

1 \leq u,v \leq N

u \neq v

1 \leq A_i,B_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N u v
A_1 B_1
:
A_{N-1} B_{N-1}

Output

Print the number of moves Aoki will perform before the end of the game.

Sample Input 1

5 4 1
1 2
2 3
3 4
3 5

Sample Output 1

2

If both players play optimally, the game will progress as follows:

Takahashi moves to Vertex 3.

Aoki moves to Vertex 2.

Takahashi moves to Vertex 5.

Aoki moves to Vertex 3.

Takahashi moves to Vertex 3.

Here, Aoki performs two moves.

Note that, in each move, it is prohibited to stay at the current vertex.

Sample Input 2

5 4 5
1 2
1 3
1 4
1 5

Sample Output 2

1

Sample Input 3

2 1 2
1 2

Sample Output 3

0

Sample Input 4

9 6 1
1 2
2 3
3 4
4 5
5 6
4 7
7 8
8 9

Sample Output 4

5



Sample input:
5 4 1
1 2
2 3
3 4
3 5


Sample output:
2

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

N, u, v = map(int, input().split())
u -= 1
v -= 1

edges = [[] for _ in range(N)]
for _ in range(N - 1):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)
    edges[to].append(fr)

def minDist(start):
    minDist = [10**10] * N
    que = deque([(start, 0, -1)])
    while que:
        now, d, pr = que.popleft()

        if minDist[now] <= d:
            continue
        minDist[now] = d

        for to in edges[now]:
            if to == pr:
                continue
            if minDist[to] > d + 1:
                que.append((to, d + 1, now))

    return minDist

minDistU = minDist(u)
minDistV = minDist(v)

ans = 0
for du, dv in zip(minDistU, minDistV):
    if du <= dv:
        ans = max(ans, dv - 1)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N,u,v=map(int,input().split())
u-=1;v-=1
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    G[a].append(b)
    G[b].append(a)
if len(G[u])==1 and G[u][0]==v:
    print(0)
    exit()
distu=[-1 for i in range(N)]
q=deque([])
q.append(u)
while(len(q)>0):
    r=q.pop()
    for p in G[r]:
        if distu[p]!=-1:
            continue
        distu[p]=distu[r]+1
        q.append(p)
distv=[-1 for i in range(N)]
q=deque([])
q.append(v)
while(len(q)>0):
    r=q.pop()
    for p in G[r]:
        if distv[p]!=-1:
            continue
        distv[p]=distv[r]+1
        q.append(p)
dist=[distv[i] if distu[i]<=distv[i] else 0 for i in range(N)]
print(max(dist))

Submission status: Accepted

Solution code:
N, U, V = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N - 1)]

graph = [[] for _ in range(N + 1)]
for A, B in AB:
  graph[A].append(B)
  graph[B].append(A)

INF = 10 ** 15
dist_U = [INF] * (N + 1)
dist_V = [INF] * (N + 1)

def dfs(start, dist):
  stack = [start]
  dist[start] = 0
  
  while stack:
    s = stack.pop()
    for g in graph[s]:
      if dist[g] > dist[s] + 1:
        dist[g] = dist[s] + 1
        stack.append(g)

dfs(U, dist_U)
dfs(V, dist_V)
#print("dist_U", dist_U)
#print("dist_V", dist_V)

answer = []
for i in range(1, N + 1):
  if dist_U[i] < dist_V[i]:
    answer.append(dist_V[i] - 1)
print(max(answer))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
# 再帰上限を引き上げる
sys.setrecursionlimit(10**6)

n, u, v = map(int, input().split())
u, v = u-1, v-1
l = [[] for i in range(n)]
for i in range(n-1):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  l[a].append(b)
  l[b].append(a)

def dfs(G, cr, seen, dist):
  seen[cr] = 1
  for i in G[cr]:
    if seen[i] == 0:
      dist[i] = dist[cr] + 1
      dfs(G, i, seen, dist)
  return dist

seen_u = [0]*n
seen_v = [0]*n
dist_u = [0]*n
dist_v = [0]*n

T1 = dfs(l, u, seen_u, dist_u)
T2 = dfs(l, v, seen_v, dist_v)

for i in range(n):
  if dist_u[i] >= dist_v[i]:
    dist_v[i] = -1
    
print(max(dist_v)-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

# 再帰上限を引き上げる
sys.setrecursionlimit(10**6)

# G:graph, cr:current node, seen:is seen?, dist:out;each distance
def dfs(G,cr,seen,dist):
	seen[cr] = 1
	for i in G[cr]: #G[cr]から行ける各頂点へ
		if seen[i] == 0: #まだ通っていなかったら
			dist[i] = dist[cr]+1
			dfs(G,i,seen,dist)


n,u,v = (int(x) for x in input().split())

u,v = u-1,v-1

a = [[] for i in range(n)]

for i in range(n-1):
	# 配列indexは0開始だからinputは-1
	l,m = (int(x)-1 for x in input().split())
	a[l].append(m)
	a[m].append(l)

# v視点のdistを調べる
dist_u = [0]*n
dist_v = [0]*n

dfs(a,u,[0]*n,dist_u)
# u視点のdistを調べる
dfs(a,v,[0]*n,dist_v)

for i in range(n):
	if dist_u[i] >= dist_v[i]: # vが追いつける距離なら
		dist_v[i] = -1

print(max(dist_v) - 1)

Submission status: Accepted

Solution code:
N, u, v = map(int, input().split())
L = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    L[a - 1].append(b - 1)
    L[b - 1].append(a - 1)

Leaf = []  # 葉かどうかを記録する
for i in range(N):
    c = 0
    for j in L[i]:
        c = c + 1
    if c == 1:
        Leaf.append(True)
    else:
        Leaf.append(False)

UD = [0 for i in range(N)]  # 各頂点のuからの距離
UD[u - 1] = -1  # 0でないなら訪問済みとする
M = L[u - 1]  # 次に訪れるノードのリスト
d = 1  # uからの距離
while True:
    new_M = []
    for i in M:
        if UD[i] == 0:  # 0 ならiに隣接するノードをnew_Mに追加
            UD[i] = d
            for j in L[i]:
                new_M.append(j)
        else:
            pass
    M = new_M
    if len(M) == 0:
        break
    d = d + 1
UD[u-1] = 0

VD = [0 for i in range(N)]
VD[v-1] = -1
M = L[v-1]
d = 1

while True:
    new_M = []
    for i in M:
        if VD[i] == 0:  # 0 ならiに隣接するノードをnew_Mに追加
            VD[i] = d
            for j in L[i]:
                new_M.append(j)
        else:
            pass
    M = new_M
    if len(M) == 0:
        break
    d = d + 1
VD[v-1] = 0




d = -1
index = u-1
# vよりもuの方が近く,最もvから離れている葉を見つける
for i in range(N):
    if Leaf[i]:
        if UD[i] < VD[i]:
            if d < VD[i]:
                d = VD[i]

print(d-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)

n, u, v = map(int, input().split())
to = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    to[a].append(b)
    to[b].append(a)

def DFS(s, dist, to, d = 0, p = -1):
    dist[s] = d
    for v in to[s]:
        if v == p:
            continue
        DFS(v, dist, to, d + 1, s)
    
def calcDist(s, dist, to):
    DFS(s, dist, to)
    
distU = [0] * (n + 1)
distV = [0] * (n + 1)

calcDist(u, distU, to)
calcDist(v, distV, to)
ans = 0
for i in range(n + 1):
    if distU[i] < distV[i]:
        ans = max(ans, distV[i])
print(ans - 1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

from collections import deque

################ DANGER ################
test = ""
#test = \
"""
9 6 1
1 2
2 3
3 4
4 5
5 6
4 7
7 8
8 9
ans 5
"""

"""
5 4 1
1 2
2 3
3 4
3 5
ans 2
"""

"""
5 4 5
1 2
1 3
1 4
1 5
ans 1
"""
########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
########################################  
        
n, taka, aoki = map(int, input2().split())

edges = [0] * (n-1)
for i in range(n-1):
    edges[i] = tuple(map(int, input2().split()))

adjacencyL = [[] for i in range(n+1)]
for edge in edges:
    adjacencyL[edge[0]].append(edge[1])
    adjacencyL[edge[1]].append(edge[0])    

################ DANGER ################
#print("taka", taka, "aoki", aoki)
#import matplotlib.pyplot as plt
#import networkx as nx
#G = nx.DiGraph()
#G.add_edges_from(edges)
#nx.draw_networkx(G)
#plt.show()
########################################

takaL = [None] * (n+1)
aokiL = [None] * (n+1)
takaL[taka] = 0
aokiL[aoki] = 0
takaQ = deque([taka])
aokiQ = deque([aoki])

for L, Q in ((takaL, takaQ), (aokiL, aokiQ)):
    while Q:
        popN = Q.popleft()
        for a in adjacencyL[popN]:
            if L[a] == None:
                Q.append(a)
                L[a] = L[popN] + 1
                
    #print(L)
    
print(max(aokiL[i] for i in range(1, n+1) if takaL[i] < aokiL[i]) - 1)

Submission status: Accepted

Solution code:

import copy
import sys

# 再帰上限を引き上げる
sys.setrecursionlimit(10**6)

def dfs(graph, v, d):
    seen[v] = True # 訪問済みかどうか
    dist[v] = d # 距離を記録

    # 頂点vから行ける頂点を全探索
    for i in graph[v]:
        if seen[i]:
            continue
        dfs(graph, i, d+1)

# ここから本文
N, u, v = map(int, input().split())

u -= 1
v -= 1

# グラフ構造を作る
graph = [[] for i in range(N)]
for i in range(N - 1):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    graph[A].append(B)
    graph[B].append(A)

# 青木くんからの各頂点の距離
seen = [False for i in range(N)]
dist = [0 for i in range(N)]
dfs(graph, v, 0)
aoki_dist = copy.deepcopy(dist)

# 高橋くんからの各頂点の距離
seen = [False for i in range(N)]
dist = [0 for i in range(N)]
dfs(graph, u, 0)
takahashi_dist = copy.deepcopy(dist)

ans = 0
for i in range(N):
    if aoki_dist[i] > takahashi_dist[i]:
        if aoki_dist[i] - 1 > ans:
            ans = aoki_dist[i] - 1      

print(ans)

Submission status: Accepted

Solution code:
I = [int(_) for _ in open(0).read().split()]
n, u, v = I[:3]
A, B = I[3::2], I[4::2]
S = [set() for _ in range(n+1)]
for a, b in zip(A, B):
    S[a].add(b)
    S[b].add(a)
def cal(x):
  dist=[None]*(n+1)
  dist[x]=0
  st=set([x])
  while st:
    x=st.pop()
    for i in S[x]:
      if dist[i]==None:
        dist[i]=dist[x]+1
        st.add(i)
  return dist

T=cal(u)
A=cal(v)
ans=0
for t,a in zip(T[1:],A[1:]):
  if t<a:
    ans=max(ans,a-1)
print(ans)

Submission status: Accepted

Solution code:
N, u, v = map(int, input().split())
u, v = u - 1, v - 1
T = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    T[a].append([b, 1])
    T[b].append([a, 1])


def dijkstra(graph, start, inf=float('inf')):
    import heapq
    n = len(graph)
    distances = [inf] * n
    distances[start] = 0
    visited = [False] * n

    # 距離・頂点
    hq = [(0, start)]
    while hq:
        dist, fr = heapq.heappop(hq)
        visited[fr] = True

        for to, cost in graph[fr]:
            new_dist = distances[fr] + cost
            if (visited[to]) or (distances[to] <= new_dist):
                continue

            distances[to] = new_dist
            heapq.heappush(hq, (new_dist, to))

    return distances


U_dist = dijkstra(T, u)
V_dist = dijkstra(T, v)

ans_candidates = [dv for du, dv in zip(U_dist, V_dist) if du < dv]
print(max(ans_candidates) - 1)

Submission status: Accepted

Solution code:
n, u, v = map(int, input().split())
matrix = [[] for _ in range(n)]
import sys
sys.setrecursionlimit(10**8)
for _ in range(n-1):
    a,b = map(int, input().split())
    matrix[a-1].append(b-1)
    matrix[b-1].append(a-1)

C = [0]*n
D = [0]*n

def dfs(x, pre, cnt, c):
    c[x] = cnt
    cnt += 1
    for a in matrix[x]:
        if a == pre:
            continue
        dfs(a, x, cnt, c)

dfs(v-1, -1, 0, C)
dfs(u-1, -1, 0, D)
ans=0

for i in range(n):
    if C[i] > D[i]:
        ans = max(ans, C[i]-1)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)

def dfs(v, dist, d = 0, p = -1):
#     print(v, d)
    dist[v] = d
    for u in to[v]:
        if u == p:
            continue
        dfs(u, dist, d + 1, v)
def calcDist(s, dist):
    dfs(s, dist)        
n, u, v = map(int, input().split())
u -= 1
v -= 1
to = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
distS = [0] * n
distT = [0] * n
calcDist(u, distS)
calcDist(v, distT)
mx = 0
for i in range(n):
    if distS[i] < distT[i]:
        mx = max(mx, distT[i])
ans = mx - 1
print(ans)

Submission status: Accepted

Solution code:

# グラフ問題での分析が全然できなかった（初体験）
# 次回は頑張って解く！
# 解説動画をみることがMUST、基本そのまま書いている。

from heapq import heappop, heappush
N, u, v = map(int, input().split())
edges = [[] for i in range(N+1)]

for i in range(N-1):
  a, b = map(int, input().split())
  edges[a].append(b)
  edges[b].append(a)

def dfs(u):
  colors = ["white"] * (N+1)
  d = [9999999999999999] * (N + 1)
  d[u] = 0
  stack = [u]

  while stack:
    u = stack.pop()
    colors[u] = "black"

    for e in edges[u]:
      if colors[e] != "black":
        d[e] = d[u] + 1
        stack.append(e)

  return d

u_dist = dfs(u)
v_dist = dfs(v)

ans = 0
for i in range(N+1):
  if u_dist[i] < v_dist[i]:
    ans = max(ans, v_dist[i] - 1)

print(ans)

Submission status: Accepted

Solution code:
N, U, V = map(int, input().split())
A = [[] for _ in range(N)]
import sys
sys.setrecursionlimit(10**8)
for _ in range(N - 1):
    a, b = map(int, input().split())

    A[a - 1].append(b - 1)
    A[b - 1].append(a - 1)

C = [0] * N
D = [0] * N

def DFS(x, pre, cnt, C):
    C[x] = cnt
    cnt += 1
    for a in A[x]:
        if a == pre:
            continue

        DFS(a, x, cnt, C)


DFS(V - 1, -1, 0, C)
DFS(U - 1, -1, 0, D)
ans=0
for i in range(N):
    if C[i]>D[i]:
        ans =max(ans, C[i]-1)
print(ans)

Submission status: Accepted

Solution code:
N, U, V = map(int, input().split())
A = [[] for _ in range(N)]

import sys
import numpy as np
sys.setrecursionlimit(10**8)
for _ in range(N - 1):
    a, b = map(int, input().split())

    A[a - 1].append(b - 1)
    A[b - 1].append(a - 1)

C = [0] * N
D = [0] * N

def DFS(x, pre, cnt, C):
    C[x] = cnt
    cnt += 1
    for a in A[x]:
        if a == pre:
            continue

        DFS(a, x, cnt, C)


DFS(V - 1, -1, 0, C)
DFS(U - 1, -1, 0, D)

E = np.array(C) > np.array(D)
C = np.array(C)
ans = max(C[E]) - 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

n, s, t = map(int, input().split(' '))
s -= 1
t -= 1

v = [[] for i in range(n)]
f = [0]*n

for i in range(n-1):
    a, b = map(int, input().split(' '))
    a -= 1
    b -= 1
    v[a].append(b)
    v[b].append(a)
    f[a] += 1
    f[b] += 1
for i in range(n):
    if f[i] == 0:
        l.append(i)
depth = [-1]*n
depth[t] = 0
q = deque([t])
while q:
    x = q.popleft()
    for y in v[x]:
        if depth[y] < 0:
            depth[y] = depth[x]+1
            q.append(y)
l = depth[:]
d = [-1]*n
d[s] = 0
q = deque([s])
while q:
    x = q.popleft()
    for y in v[x]:
        if d[y] < 0:
            d[y] = d[x]+1
            q.append(y)
l = sorted(range(n), key=lambda x:-depth[x])
for i in l:
    if d[i] < depth[i]:
        break
print(depth[i] - 1)

Submission status: Accepted

Solution code:
from collections import deque

N, u, v = map(int, input().split())

neighbors = [[] for i in range(N + 1)]

for _ in range(N - 1):
    A, B = map(int, input().split())
    neighbors[A].append(B)
    neighbors[B].append(A)


def BFS(neighbors, s):
    q = deque([s])
    dist = [-1] * len(neighbors)
    dist[s] = 0
    while q:
        t = q.popleft()
        d = dist[t]
        nodes = neighbors[t]
        for n in nodes:
            if dist[n] < 0:
                dist[n] = d + 1
                q.append(n)
    return dist

u_cost = BFS(neighbors, u)
v_cost = BFS(neighbors, v)

ans = 0
for i in range(1, N + 1):
    if u_cost[i] < v_cost[i]:
        ans = max(ans, v_cost[i])

print(ans - 1)

Submission status: Accepted

Solution code:
#1-index
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

from collections import deque

N, u, v = map(int, input().split())
G = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    A, B = map(int, input().split())
    G[A].append(B)
    G[B].append(A)

queT = deque()
queA = deque()

checkT = [-1] * (N + 1)
checkA = [-1] * (N + 1)

checkT[u] = 0
checkA[v] = 0

queT.append(u)
queA.append(v)
flag = True
while queT or queA: #どちらかが生きているとき
    tmp_lst = []
    while queT:
        tmp = queT.popleft()
        d = checkT[tmp]
        for next_ in G[tmp]:
            if checkT[next_] == -1:
                if checkA[next_] != -1:
                    flag = False
                    turn = True #高橋くんが動くとぶつかる
                    break
                checkT[next_] = d + 1
                tmp_lst.append(next_)
        if not flag:
            break
    if not flag:
        break
    for i in tmp_lst:
        queT.append(i)
    
    tmp_lst = []
    while queA:
        tmp = queA.popleft()
        d = checkA[tmp]
        for next_ in G[tmp]:
            if checkA[next_] == -1:
                if checkT[next_] != -1:
                    flag = False
                    turn = False #青木くんが動くとぶつかる
                    break
                checkA[next_] = d + 1
                tmp_lst.append(next_)
        if not flag:
            break
    if not flag:
        break
    for i in tmp_lst:
        queA.append(i)

# print (checkT)
# print (checkA)
# print (d)
# print (turn)
# print (tmp) #現在の場所
#ここまでで二人がギリギリまで近づく位置と、どちらが動いたらぶつかるかが分かる

if turn:
    ans = 0
    check = [-1] * (N + 1)
    check[tmp] = 0
    stack = [tmp]
    while stack:
        tmp1 = stack.pop()
        tmp_d = check[tmp1]
        # flag = True
        for next_ in G[tmp1]:
            if check[next_] == -1 and checkA[next_] == -1:
                check[next_] = tmp_d + 1
                stack.append(next_)
                # flag = False
        # if flag:
        ans = max(ans, tmp_d)

else:
    ans = 0
    check = [-1] * (N + 1)
    check[tmp] = 0
    stack = [tmp]

    tmp1 = stack.pop()
    tmp_d = check[tmp1]
    # flag = True
    for next_ in G[tmp1]:
        if check[next_] == -1 and checkT[next_] != -1:
            check[next_] = tmp_d + 1
            stack.append(next_)
            # flag = False
    # if flag:
    ans = max(ans, tmp_d)

    while stack:
        tmp1 = stack.pop()
        tmp_d = check[tmp1]
        # flag = True
        for next_ in G[tmp1]:
            if check[next_] == -1 and checkA[next_] == -1:
                check[next_] = tmp_d + 1
                stack.append(next_)
                # flag = False
        # if flag:
        ans = max(ans, tmp_d)    


# print (check)
if turn:
    print (max(d + ans, 0))
else:
    print (max(d + ans - 1, 0))

Submission status: Accepted

Solution code:
# ABC148 F
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
N, u, v = nm()
u -= 1
v -= 1
G = [[] for i in range(N)]
for i in range(N-1):
    A, B = nm()
    A -= 1
    B -= 1
    G[A].append(B)
    G[B].append(A)

dist_u = [-1]*N
dist_v = [-1]*N
dist_u[u] = 0
dist_v[v] = 0

from collections import deque

q = deque()
q.append(u)
while q:
    x = q.popleft()
    for nx in G[x]:
        if dist_u[nx] == -1:
            q.append(nx)
            dist_u[nx] = dist_u[x]+1

q = deque()
q.append(v)
while q:
    x = q.popleft()
    for nx in G[x]:
        if dist_v[nx] == -1:
            q.append(nx)
            dist_v[nx] = dist_v[x]+1

ans = 0
for i in range(N):
    if dist_u[i] < dist_v[i] and dist_v[i] >= ans:
        ans = dist_v[i]

print(ans-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[21]:


N, u, v = map(int, input().split())
u = u - 1
v = v - 1


# In[22]:


eda = [[] for _ in range(N)]
for _ in range(N-1):
    A, B = map(int, input().split())
    eda[A-1].append(B-1)
    eda[B-1].append(A-1)


# In[25]:


par = [0] * N
# depth = [0] * N

stack = [v]
par[v] = -1

while stack:
    n1 = stack.pop()
    for n2 in eda[n1]:
        if n2 == par[n1]:
            continue
        par[n2] = n1
#         depth[n2] = depth[n1] + 1
        stack.append(n2)
        


# In[26]:


par


# In[27]:


dis = 0
n = u
while n != v:
    n = par[n]
    dis += 1


# In[28]:


n = u
for _ in range((dis - 1) // 2):
    n = par[n]


# In[29]:


y = (dis - 1) // 2
x = dis - y
# z = depth[n]


# In[38]:


stack = [n]
depth = [0] * N
maxd = 0

while stack:
    n1 = stack.pop()
    for n2 in eda[n1]:
        if n2 == par[n1]:
            continue
        depth[n2] = depth[n1] + 1
        maxd = max(maxd, depth[n2])
        stack.append(n2)
        


# In[41]:


z = maxd


# In[43]:


if dis % 2 == 0:
    print(y + z + 1)
else:
    print(y + z)


# In[ ]:

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n, u, v = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)

tkhs = [-1 for _ in range(n)]
aoki = [-1 for _ in range(n)]
tkhs[u-1], aoki[v-1] = 0, 0

def dfs(x, player):
	for y in adj[x]:
		if player[y] < 0:
			player[y] = player[x] + 1
			dfs(y, player)
	return

dfs(u-1, tkhs)
dfs(v-1, aoki)

ans = 0
for i in range(n):
	if tkhs[i] <= aoki[i] and len(adj[i]) > 1:
		ans = max(ans, aoki[i])

print(ans)

Submission status: Accepted

Solution code:
import heapq
import sys
sys.setrecursionlimit(10**6)
 
N,u,v = map(int, input().split())
 
es = [[] for _ in range(N+1)]
 
for i in range(N-1):
    a,b = map(int, input().split())
    es[a].append(b)
    es[b].append(a)
 
INF = float("inf")
from_u = [INF] * (N+1)
from_u[u] = -1
from_v = [INF] * (N+1)
from_v[v] = -1
 
def solve(prev, curr, distances):
    distances[curr] = distances[prev] + 1
    for next in es[curr]:
        if distances[next] == INF:
            solve(curr, next, distances)
 
solve(u,u,from_u)
solve(v,v,from_v)
 
 
 
ans = 0
for i in range(1,N+1):
    if from_u[i] < from_v[i]:
        # 追い詰めた段階で高橋君が自ら青木君のマスに戻ってくるので、最後の端っこまで追い詰めなくていいから-1
        ans = max(ans, from_v[i]-1)
 
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
N, u, v = map(int, input().split())
u -= 1
v -= 1

G = [[] for _ in range(N)]
elens = [0] * N

for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
    elens[a] += 1
    elens[b] += 1
depths = [0] * N
dists = [0] * N


TAKAHASHI = [0] * N
AOKI = [0] * N

def dfs_aoki(cur: int, past: int, d: int):
    AOKI[cur] = d

    for nx in G[cur]:
        if nx == past:
            continue
        dfs_aoki(nx, cur, d + 1)

def dfs_takahashi(cur: int, past: int, d: int):
    TAKAHASHI[cur] = d

    for nx in G[cur]:
        if nx == past:
            continue
        dfs_takahashi(nx, cur, d + 1)

dfs_takahashi(u, -1, 0)
dfs_aoki(v, -1, 0)

ans = 0

for i in range(N):
    if TAKAHASHI[i] < AOKI[i]:
        ans = max(ans, AOKI[i] - 1)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

INF = -1

n, t, a = map(int, input().split())
t -= 1
a -= 1
g = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v = map(lambda x: int(x) - 1, input().split())
    g[u].append(v)
    g[v].append(u)

def bfs(start):
    dist = [INF] * n
    dist[start] = 0
    q = deque([start])
    while q:
        cur = q.pop()
        for to in g[cur]:
            if dist[to] == INF:
                dist[to] = 1 + dist[cur]
                q.appendleft(to)
    return dist

distT = bfs(t)
distA = bfs(a)
ret = 0
for v in range(n):
    if distT[v] < distA[v]:
        ret = max(ret, distA[v] - 1)
print(ret)

Submission status: Accepted

Solution code:
from collections import deque
n,u,v = map(int,input().split())
Edge = [[] for i in range(n)]

for i in range(n-1):
    a,b = map(int,input().split())
    Edge[a-1].append(b-1)
    Edge[b-1].append(a-1)

def bfs(s):
    dist = [-1]*n
    que = deque([s-1])
    dist[s-1] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in Edge[v]:
            if dist[w] > -1:
                continue

            dist[w] = d+1
            que.append(w)
    return dist

U,V = bfs(u),bfs(v)

ans = 0

for i in range(n):
    if U[i] < V[i]:
        ans = max(ans,V[i]-1)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

N, U, V = map(int, input().split())
U, V = U-1, V-1
T = [[] for _ in range(N)]
D = [0]*N
for i in range(N-1):
    a, b, = map(int, input().split())
    a, b = a-1, b-1
    T[a].append(b)
    T[b].append(a)
    D[a] += 1
    D[b] += 1

Dist_U = [0]*N
check = [0]*N
Q = deque([(U, 0)])
while Q:
    n, d = Q.popleft()
    check[n] = 1
    Dist_U[n] = d
    for i in T[n]:
        if check[i]:
            continue
        else:
            Q.append((i, d+1))

Dist_V = [0]*N
check = [0]*N
Q = deque([(V, 0)])
while Q:
    n, d = Q.popleft()
    check[n] = 1
    Dist_V[n] = d
    for i in T[n]:
        if check[i]:
            continue
        else:
            Q.append((i, d+1))

ans = 0
for i in range(N):
    if D[i] == 1:
        if Dist_U[i] < Dist_V[i]:
            ans = max(ans, Dist_V[i]-1)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

N,u,v=map(int,input().split()) # u,vから1を引く必要がある
a=[[] for _ in range(N)] # 0-initial
for _ in range(N-1):
    Ai,Bi=map(int,input().split())
    a[Ai-1].append(Bi-1)
    a[Bi-1].append(Ai-1)
T=u-1;A=v-1

# 方針
# Tは，Tからの距離dTがAからの距離dA以下であるような点のうち，最もdAが大きい点を目指す。
dT=[-1]*N
q=deque()
q.append(T);dT[T]=0
while q:
    u=q.popleft()
    for v in a[u]:
        if dT[v]==-1:
            dT[v]=dT[u]+1
            q.append(v)

dA=[-1]*N
q=deque()
q.append(A);dA[A]=0
while q:
    u=q.popleft()
    for v in a[u]:
        if dA[v]==-1:
            dA[v]=dA[u]+1
            q.append(v)   

'''
print(a)
print(dT)
print(dA)
'''
ans=0
if a[T]!=[A] and T!=A:
    for i in range(N):
        if dT[i]<dA[i] and ans<dA[i]-1:
            ans=dA[i]-1

print(ans)

Submission status: Accepted

Solution code:
def dps_rec(no, fno, d, hen, D, MD, P):
    D[no] = d
    P[no] = fno
    maxd = d
    for h in hen[no]:
        if h == fno:
            continue
        maxd = max(maxd, dps_rec(h, no, d + 1, hen, D, MD, P))
    MD[no] = maxd
    return maxd

def dps_stc(no, fno, d, hen, D):
    stack = [(no, fno, d)]
    while not stack == []:
        t = stack.pop()
        D[t[0]] = t[2]
        for h in hen[t[0]]:
            if h == t[1]:
                continue
            stack.append((h, t[0], t[2] + 1))

def main():
    N, u, v = map(int, input().split())
    hen = {}
    for i in range(N - 1):
        A, B = map(int, input().split())
        if A in hen.keys():
            hen[A].append(B)
        else:
            hen[A] = [B]
        if B in hen.keys():
            hen[B].append(A)
        else:
            hen[B] = [A]
    DEPTH_A = [-1 for i in range(N + 1)]
    DEPTH_T = [-1 for i in range(N + 1)]
    dps_stc(v, -1, 0, hen, DEPTH_A)
    dps_stc(u, -1, 0, hen, DEPTH_T)
    ans = 0
    for a, t in zip(DEPTH_A, DEPTH_T):
        if a > t:
            ans = max(ans, a - 1)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import exit
N, u, v = map(int, input().split())

if u == v:
    print(0)
    exit()

edges = [[] for _ in range(N+1)]

for _ in range(N-1):
    A, B = map(int, input().split())
    edges[A].append(B)
    edges[B].append(A)

def calDist(start, edges):
    dest = [-1] * (N + 1)
    dest[start] = 0
    q = [start]
    while len(q) != 0:
        current = q.pop()
        for n in edges[current]:
            if dest[n] != -1:
                continue
            dest[n] = dest[current] + 1
            q.append(n)
    return dest

T = calDist(u, edges)
A = calDist(v, edges)

result = 0
for i in range(1, N+1):
    A_i = A[i]
    if T[i] >= A_i:
        continue
    if A_i > result:
        result = A_i

print(result-1)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

n,t,a=LI_()
n+=1
g,c=GI(n,n-1)

def bfs(x):  # x スタート
    v=[-1]*(n)
    p=deque()
    p.append(x)
    v[x]=0
    while p:
        c=p.popleft()
        for i in g[c]:
            if v[i]==-1:
                p.append(i)
                v[i]=v[c]+1
    return v

v=bfs(a)
w=bfs(t)
ans=0
for i in range(n):
    if v[i]>=w[i] and max([v[j] for j in g[i]])>v[i]:
        ans=max(ans,v[i])

print(ans)