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
N,ppl,oni = map(int,input().split())
ppl -= 1
oni -= 1
AB = [ []for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    AB[a-1].append(b-1)
    AB[b-1].append(a-1)

def dfs(start):
    dist = [-1 for i in range(N)]
    dist[start] = 0
    que = deque()
    que.append(start)
    while que:
        q = que.popleft()
        for nextr in AB[q]:
            if dist[nextr] == -1:
                dist[nextr] = dist[q] +1
                que.append(nextr)
    return dist
    
if len(AB[ppl]) == 1 and oni in AB[ppl]:
    print(0)
else:
    ppldist = dfs(ppl)
    onidist = dfs(oni)
    maxa = max(onidist)
    ans = 0
    for i in range(N):
        if ppldist[i] < onidist[i]:
            ans = max(ans,onidist[i]-1)
    print(ans)

Submission status: Accepted

Solution code:
def bfs(k):
    flag=[-1]*(n+1)
    que=[k]
    flag[k]=0
    cnt=1
    while que:
        h=[]
        for uu in que:
            for vv in data[uu]:
                if flag[vv]==-1:
                    flag[vv]=cnt
                    h.append(vv)
        que=h
        cnt+=1
    return flag

n,u,v=map(int,input().split())
data=[[] for i in range(n+1)]
for _ in range(n-1):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)
T=bfs(u)
A=bfs(v)
ans=0
for i in range(1,n+1):
    if T[i]<A[i]:
        ans=max(ans,A[i]-1)
print(ans)

Submission status: Accepted

Solution code:

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

def dfs_deep_measure(st, n, reach):
    deep = [-1] * n
    check = [0] * n
    stack = [st]
    check[st] = 1
    deep[st] = 0
    while len(stack) > 0:
        tmp = stack.pop(-1)
        tmp_list = reach[tmp]
        for i in tmp_list:
            if check[i] != 1:
                stack.append(i)
                check[i] = 1
                deep[i] = deep[tmp]+1
    return deep

a_route = dfs_deep_measure(v, n, reach)
t_route = dfs_deep_measure(u, n, reach)
ans = 0
for i in range(len(a_route)):
    if t_route[i] < a_route[i]:
        ans = max(ans, a_route[i]-1)

print(ans)

Submission status: Accepted

Solution code:
n, u, v = map(int, input().split())
u, v = u-1, v-1
reach = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    reach[a].append(b)
    reach[b].append(a)

def x_route(x, reach):
    x_route = [-1] * n
    check = [0] * n
    stack = [x]
    check[x] = 1
    x_route[x] = 0
    while len(stack) > 0:
        tmp = stack.pop(-1)
        tmp_list = reach[tmp]
        for i in tmp_list:
            if check[i] != 1:
                stack.append(i)
                check[i] = 1
                x_route[i] = x_route[tmp]+1
    return x_route

a_route = x_route(v, reach)
t_route = x_route(u, reach)
ans = 0
for i in range(len(a_route)):
    if t_route[i] < a_route[i]:
        ans = max(ans, a_route[i]-1)

print(ans)

Submission status: Accepted

Solution code:
#%%
n, u, v = map(int, input().split())
u, v = u-1, v-1
reach = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    reach[a].append(b)
    reach[b].append(a)

def x_route(x, reach):
    x_route = [[-1, -1] for _ in range(n)]
    check = [0] * n
    stack = [x]
    check[x] = 1
    x_route[x] = [-1, 0]
    while len(stack) > 0:
        tmp = stack.pop(-1)
        tmp_list = reach[tmp]
        for i in tmp_list:
            if check[i] == 1:
                pass
            else:
                stack.append(i)
                check[i] = 1
                x_route[i] = [tmp, x_route[tmp][1]+1] 
    return x_route

a_route = x_route(v, reach)
t_route = x_route(u, reach)
ans = 0
for i in range(len(a_route)):
    if t_route[i][1] < a_route[i][1]:
        ans = max(ans, a_route[i][1]-1)

print(ans)

Submission status: Accepted

Solution code:
#%%
n, u, v = map(int, input().split())
u, v = u-1, v-1
a, b = [0] * (n-1), [0] * (n-1)
reach = [[] for _ in range(n)]
for i in range(n-1):
    a[i], b[i] = map(lambda x: int(x)-1, input().split())
    reach[a[i]].append(b[i])
    reach[b[i]].append(a[i])

a_route = [[-1, -1] for _ in range(n)]
check = [0] * n
stack = [v]
check[v] = 1
a_route[v] = [-1, 0]

while len(stack) > 0:
    tmp = stack.pop(-1)
    tmp_list = reach[tmp]
    for i in tmp_list:
        if check[i] == 1:
            pass
        else:
            stack.append(i)
            check[i] = 1
            a_route[i] = [tmp, a_route[tmp][1]+1]

t_route = [[-1, -1] for _ in range(n)]
check = [0] * n
stack = [u]
check[u] = 1
t_route[u] = [-1, 0]

while len(stack) > 0:
    tmp = stack.pop(-1)
    tmp_list = reach[tmp]
    for i in tmp_list:
        if check[i] == 1:
            pass
        else:
            stack.append(i)
            check[i] = 1
            t_route[i] = [tmp, t_route[tmp][1]+1]
    
ans = 0
for i in range(len(a_route)):
    if t_route[i][1] < a_route[i][1]:
        ans = max(ans, a_route[i][1]-1)

print(ans)

Submission status: Accepted

Solution code:
#%%
n, u, v = map(int, input().split())
u, v = u-1, v-1
a, b = [0] * (n-1), [0] * (n-1)
reach = [[] for _ in range(n)]
for i in range(n-1):
    a[i], b[i] = map(lambda x: int(x)-1, input().split())
    reach[a[i]].append(b[i])
    reach[b[i]].append(a[i])

##############################################################
#①aoki_route
#深さ、前のてんの情報
a_route = [[-1, -1] for _ in range(n)]
check = [0] * n
stack = [v]
check[v] = 1
a_route[v] = [-1, 0]

while len(stack) > 0:
    tmp = stack.pop(-1)
    tmp_list = reach[tmp]
    for i in tmp_list:
        if check[i] == 1:
            pass
        else:
            stack.append(i)
            check[i] = 1
            a_route[i] = [tmp, a_route[tmp][1]+1]

tmp = -1
for i in range(len(a_route)):
    if a_route[i][1] > tmp:
        tmp = a_route[i][1]
        AA = i

aoki_A = [AA]
tmp = AA
while True:
    tmp = a_route[tmp][0]
    if tmp == -1:
        break
    aoki_A.append(tmp)
"""
print('aoki')
print(a_route)
print('AA', AA)
print(aoki_A)
print('------------------')
"""

#########################################################################
#t_route
#前のてんの情報、深さ
t_route = [[-1, -1] for _ in range(n)]
check = [0] * n
stack = [u]
check[u] = 1
t_route[u] = [-1, 0]

while len(stack) > 0:
    tmp = stack.pop(-1)
    tmp_list = reach[tmp]
    for i in tmp_list:
        if check[i] == 1:
            pass
        else:
            stack.append(i)
            check[i] = 1
            t_route[i] = [tmp, t_route[tmp][1]+1]

takahashi_A = [AA]
tmp = AA
while True:
    tmp = t_route[tmp][0]
    if tmp == -1:
        break
    takahashi_A.append(tmp)
"""
print('takahashi')
print(t_route)
print(AA)
print(takahashi_A)
print('---------------')
"""

#####################################################
#3　点Cを求める
tmp = -1
CC = -1
for i in range(min(len(aoki_A), len(takahashi_A))):
    if aoki_A[i] != takahashi_A[i]:
        CC = tmp
        break
    tmp = aoki_A[i]
"""
print('CC', CC)
('----------------------------------')
"""
#####################################################
#4　AA - BB
#前のてんの情報、深さ、お高橋の点を通っているかの情報
x_route = [[-1, -1, -1] for _ in range(n)]
check = [0] * n
stack = [CC]
check[CC] = 1
x_route[CC] = [-1, 0, -1]

while len(stack) > 0:
    tmp = stack.pop(-1)
    tmp_list = reach[tmp]
    for i in tmp_list:
        if check[i] == 1:
            pass
        else:
            stack.append(i)
            check[i] = 1
            x_route[i] = [tmp, x_route[tmp][1]+1, x_route[tmp][2]]
            if i == u:
                x_route[i] = [tmp, x_route[tmp][1]+1, 1]

tmp = -1
for i in range(len(x_route)):
    if x_route[i][1] > tmp and x_route[i][2] == 1:
        tmp = x_route[i][1]
        BB = i
"""
print('CC - BB')
print(x_route)
print('BB', BB)
"""


('#######################')
dai = [AA, BB, CC]
aoki = []
takahashi = []
for i in range(3):
    aoki.append(a_route[dai[i]][1])
    takahashi.append(t_route[dai[i]][1])
"""
print(aoki)
print(takahashi)
"""
"""

if takahashi[2] < aoki[2]:
    print(aoki[0]-1)
else:
    print(max(aoki[2], aoki[1]-1))




#print(a_route)
#print(t_route)
"""
    
ans = 0
for i in range(len(a_route)):
    if t_route[i][1] < a_route[i][1]:
        ans = max(ans, a_route[i][1]-1)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
[考察]
　高橋君が最も遠くに逃げる場合
　:= (高橋君が先に行ける頂点)Λ(青木君から最も遠い頂点)

⇒高橋君が先に行ける頂点
　高橋君からの各頂点の距離(高橋君を根としたときの木の深さ),
　青木君からの各頂点の距離(青木君を根としたときの木の深さ)を求めて、
　高橋君からの距離と青木君からの距離を比較
⇒青木君から最も遠い頂点
　青木君からの各頂点の距離の最大値
"""
n,V,U = LI()
V -= 1
U -= 1

edges = [[] for _ in range(n)]

for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

if n == 2:
    print(0)
else:
    depth_v = [None]*n
    depth_v[V] = 0
    que = deque()
    que.append(V)
    while que:
        v = que.popleft()
        for u in edges[v]:
            if depth_v[u] == None:
                depth_v[u] = depth_v[v]+1
                que.append(u)
    
    depth_u = [None]*n
    depth_u[U] = 0
    que = deque()
    que.append(U)
    while que:
        u = que.popleft()
        for v in edges[u]:
            if depth_u[v] == None:
                depth_u[v] = depth_u[u] + 1
                que.append(v)
    
    ans = 0
    for v in range(n):
        if depth_v[v] < depth_u[v]:
            ans = max(ans,depth_u[v]-1)
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,V,U = LI()
V -= 1
U -= 1

edges = [[] for _ in range(n)]

for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

if n == 2:
    print(0)
else:
    depth_v = [None]*n
    depth_v[V] = 0
    que = deque()
    que.append(V)
    while que:
        v = que.popleft()
        for u in edges[v]:
            if depth_v[u] == None:
                depth_v[u] = depth_v[v]+1
                que.append(u)
    
    depth_u = [None]*n
    depth_u[U] = 0
    que = deque()
    que.append(U)
    while que:
        u = que.popleft()
        for v in edges[u]:
            if depth_u[v] == None:
                depth_u[v] = depth_u[u] + 1
                que.append(v)
    
    ans = 0
    for v in range(n):
        if depth_v[v] < depth_u[v]:
            ans = max(ans,depth_u[v]-1)
    print(ans)

Submission status: Accepted

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

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

#u〜vの最短経路を求める
r = []
parent = [-1]*N
def dfs(root,end):
    global r
    stack = []
    stack.append(root)
    parent[root] = root
    while len(stack)>0:
        p = stack.pop()
        if p==end:
            break
        for e in E[p]:
            if parent[e]==-1:
                parent[e] = p
                stack.append(e)
    p=end
    while p!=root:
        r.append(p)
        p = parent[p]
    r.append(root)

dfs(v,u)
ans += (len(r)//2)+(len(r)&1)
v = r[len(r)//2]
u = r[(len(r)//2)-1]

#uから最も遠い頂点までの距離を求める
dmax = 0
depth = [-1]*N
def dfs2(root,end,d):
    global dmax
    stack = []
    stack.append(root)
    depth[root] = d
    depth[end] = 0
    while len(stack)>0:
        p = stack.pop()
        for e in E[p]:
            if depth[e]==-1:
                depth[e] = depth[p]+1
                dmax = max(dmax,depth[e])
                stack.append(e)

dfs2(u,v,0)
ans += dmax - 1

print(ans)

Submission status: Accepted

Solution code:
n,u,v=map(int,input().split())
u-=1
v-=1
path=[[] for _ in range(n)]
for i in range(n-1):
  a,b = [int(x)-1 for x in input().split()]
  path[a].append(b)
  path[b].append(a)
parent = [-1]*n
rank = [-1]*n
que = []
que.append(v)
rank[v]=0

while(que):
  cur = que.pop()
  for nxt in path[cur]:
    if rank[nxt]==-1:
      rank[nxt]=rank[cur]+1
      parent[nxt]=cur
      que.append(nxt)
up = (rank[u]-1)//2
upto=u
for i in range(up):
  upto = parent[upto]
depth=0
que = [upto]
while(que):
  cur = que.pop()
  if len(path[cur])==1:
    depth = max(depth,rank[cur])
  else:
    for nxt in path[cur]:
      if nxt != parent[cur]:
        que.append(nxt)
print(depth-1)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  # applies to only numbers
rs = lambda: stdin.readline().rstrip()  # ignores trailing space

N, U, V = rl()
edges = [[] for _ in range(N+1)]
for i in range(N-1):
    a, b = rl()
    edges[a].append(b)
    edges[b].append(a)

def dfs(v):
    dist = [-1] * (N+1)
    dist[v] = 0
    stack = []
    stack.append(v)
    while stack:
        s = stack.pop()
        for t in edges[s]:
            if dist[t] >= 0:
                continue
            dist[t] = dist[s] + 1
            stack.append(t)
    return dist

DU, DV = dfs(U), dfs(V)
answer = 0
for u, v in zip(DU[1:], DV[1:]):
    if v > u:
        x = v - 1
        if x > answer:
            answer = x

print(answer)

Submission status: Accepted

Solution code:
N,U,V=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N-1)]
inf=10**20
c=[[] for i in range(N)]
for u,v in AB:
    c[u-1].append(v-1)
    c[v-1].append(u-1)
from heapq import heappop,heappush
def dij(c,N,s):
    d=[inf]*N
    d[s]=0
    prev=[-1]*N
    q=[]
    heappush(q,(0,s))
    while q:
        u=heappop(q)[1]
        for v in c[u]:
            temp=d[u]+1
            if d[v]>temp:
                d[v]=temp
                prev[v]=u
                heappush(q,(d[v],v))
    return d
d1=dij(c,N,U-1)
d2=dij(c,N,V-1)
r=0
for i in range(N):
    if d1[i]<d2[i]:
        r=max(r,d2[i]-1)
print(0 if len(c[U-1])==1 and c[U-1][0]==V-1 else r)

Submission status: Accepted

Solution code:
# 解説を見た

def solve(N, t, a, g) -> int:
    import sys

    sys.setrecursionlimit(10 ** 7)

    def calc_dist(init):
        dist = [-1] * N
        dist[init] = 0

        def _calc_dist(curr):
            for next_ in g[curr]:
                if dist[next_] != -1:
                    continue
                dist[next_] = dist[curr] + 1
                _calc_dist(next_)

        _calc_dist(init)
        return dist

    dist_a = calc_dist(a)
    dist_t = calc_dist(t)

    return max(dist_a[v] for v in range(N) if dist_t[v] < dist_a[v]) - 1


if __name__ == '__main__':
    N, t, a = map(int, input().split())
    t -= 1
    a -= 1

    g = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        u, v = (int(x) - 1 for x in input().split())
        g[u].add(v)
        g[v].add(u)

    print(solve(N, t, a, g))

# 青木君からの距離 > 高橋君からの距離 となる頂点Xが目的地の候補
# 青木君と高橋君の共通祖先からの距離は等しいので、
# 共通祖先への距離は、 青木君 > 高橋君 となり、高橋君は必ずXに到達できる
# Xに着いた高橋君は、手前の頂点とXとを行ったり来たりする
# a-t->at-: aが一歩進んだときに高橋君に会う(-は無人のマス目)
# at: tが手前の頂点に移動したときに青木君に会う
# いずれも手前の頂点まで青木君が移動したときにゲームが終わる
# どのXを選んでも、Xの手前でゲームが終わるので、青木君から最も遠いXを選ぶのが最善
# 頂点X: 追いつめられる位置=葉

Submission status: Accepted

Solution code:
def dfs(g,root,ds):
    q = [root]
    ds[root] = 0
    while q:
        v = q.pop()
        for c in g[v]:
            if ds[c] == -1:
                ds[c] = ds[v] + 1
                q.append(c)
        



# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
#n = int(input())
n,u,v = [int(i) for i in readline().split()]
u -= 1
v -= 1
 
g = [[] for _ in range(n)]
for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)
 
ds = [-1]*n
dg = [-1]*n

dfs(g,u,ds)
dfs(g,v,dg)

#print(ds,dg)

ans = 0
for i,j in zip(ds,dg):
    if i < j: ans = max(j-1,ans)
    
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
write = sys.stdout.write
def ii(): return int(readline())
def mi(): return map(int, readline().rstrip().split())
def li(): return list(readline().rstrip())
def lmi(): return list(map(int, readline().rstrip().split()))
def end(*arg): print(*arg); sys.exit()
# template

import collections
import itertools
edge = collections.namedtuple("edge", ["src", "to", "cost"])

# class edge():
#     def __init__(self, src: int, to: int, cost: int):
#         self.src = src
#         self.to = to
#         self.cost = cost
#     def __str__(self):
#         return "(" + str(self.src) + ", " + str(self.to) + ", " + str(self.cost) + ")"

class rootedtree():
    def __init__(self, n: int) -> None:
        _l = 0
        while pow(2, _l) < n:
            _l += 1
        self._l = _l
        self.size = n
        self.par = [[-1 for i in range(n + 1)] for i in range(_l)]
        self.graph = [[] for i in range(n)]  # type:ignore
        self.depth = [-1 for i in range(n)]
        self.root = -1

    def add_edge(self, src: int, to: int, cost: int = 1):
        self.graph[src].append(edge(src, to, cost))
        self.graph[to].append(edge(to, src, cost))

    def parent(self, x: int):
        return self.par[0][x]

    def bfs(self, s: int) -> list:
        INF = 10**9
        dist = [INF] * self.size
        que = collections.deque()  # type:ignore
        que.append(s)
        dist[s] = 0
        while len(que):
            v = que.popleft()
            for e in self.graph[v]:
                if dist[e.to] != INF:
                    continue
                dist[e.to] = dist[e.src] + 1
                que.append(e.to)
        return dist

    def __dfs1(self, r):
        root = r
        self.depth[r] = 0
        que = collections.deque()
        que.append(root)
        while len(que) != 0:
            v = que.pop()
            for u in self.graph[v]:
                if u.to != self.parent(v):
                    self.par[0][u.to] = v
                    self.depth[u.to] = self.depth[v] + 1
                    que.append(u.to)

    def build(self, _root=0) -> None:
        assert(self.root == -1)
        self.root = _root
        self.__dfs1(self.root)
        for i, j in itertools.product(range(self._l - 1), range(self.size)):
            if(self.par[i][j] == -1):
                self.par[i + 1][j] = -1
            else:
                self.par[i + 1][j] = self.par[i][self.par[i][j]]

    def lca(self, x: int, y: int) -> int:
        assert(self.root != -1)
        if self.depth[x] > self.depth[y]:
            x, y = y, x
        dif = self.depth[y] - self.depth[x]
        for i in range(self._l - 1, -1, -1):
            if dif & (1 << i):
                y = self.par[i][y]
        if x == y:
            return x
        for i in range(self._l - 1, -1, -1):
            nx = self.par[i][x]
            ny = self.par[i][y]
            if nx != ny:
                x = nx; y = ny
        return self.par[0][x]

    def depth_dif(self, x: int, y: int) -> int:
        assert(self.root != -1)
        z = self.lca(x, y)
        return self.depth[x] + self.depth[y] - 2 * self.depth[z]

def main():
    n, u, v = mi()
    u -= 1; v -= 1
    g = rootedtree(n)
    for _ in range(n - 1):
        a, b = mi()
        g.add_edge(a - 1, b - 1)
    ans = -1
    # du = g.bfs(u)
    # dv = g.bfs(v)
    # for i in range(n):
    #     if du[i] < dv[i]:
    #         ans = max(ans, dv[i])
    g.build(v)
    for i in range(n):
        x = g.lca(u, i)
        if g.depth_dif(u, x) < g.depth_dif(v, x):
            ans = max(ans, g.depth_dif(v, i))
    print(ans - 1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
write = sys.stdout.write
def ii(): return int(readline())
def mi(): return map(int, readline().rstrip().split())
def li(): return list(readline().rstrip())
def lmi(): return list(map(int, readline().rstrip().split()))
def end(*arg): print(*arg); sys.exit()
# template

import collections
import itertools

class edge():
    def __init__(self, src: int, to: int, cost: int):
        self.src = src
        self.to = to
        self.cost = cost
    def __str__(self):
        return "(" + str(self.src) + ", " + str(self.to) + ", " + str(self.cost) + ")"

class rootedtree():
    def __init__(self, n: int) -> None:
        _l = 0
        while pow(2, _l) < n:
            _l += 1
        self._l = _l
        self.size = n
        self.par = [[-1 for i in range(n + 1)] for i in range(_l)]
        self.graph = [[] for i in range(n)]  # type:ignore
        self.depth = [-1 for i in range(n)]
        self.root = -1

    def add_edge(self, src: int, to: int, cost: int = 1):
        self.graph[src].append(edge(src, to, cost))
        self.graph[to].append(edge(to, src, cost))

    def parent(self, x: int):
        return self.par[0][x]

    def bfs(self, s: int) -> list:
        INF = 10**9
        dist = [INF] * self.size
        que = collections.deque()  # type:ignore
        que.append(s)
        dist[s] = 0
        while len(que):
            v = que.popleft()
            for e in self.graph[v]:
                if dist[e.to] != INF:
                    continue
                dist[e.to] = dist[e.src] + 1
                que.append(e.to)
        return dist

    def __dfs1(self, r):
        root = r
        self.depth[r] = 0
        que = collections.deque()
        que.append(root)
        while len(que) != 0:
            v = que.pop()
            for u in self.graph[v]:
                if u.to != self.parent(v):
                    self.par[0][u.to] = v
                    self.depth[u.to] = self.depth[v] + 1
                    que.append(u.to)

    def build(self, _root=0) -> None:
        assert(self.root == -1)
        self.root = _root
        self.__dfs1(self.root)
        for i, j in itertools.product(range(self._l - 1), range(self.size)):
            if(self.par[i][j] == -1):
                self.par[i + 1][j] = -1
            else:
                self.par[i + 1][j] = self.par[i][self.par[i][j]]

    def lca(self, x: int, y: int) -> int:
        assert(self.root != -1)
        if self.depth[x] > self.depth[y]:
            x, y = y, x
        dif = self.depth[y] - self.depth[x]
        for i in range(self._l - 1, -1, -1):
            if dif & (1 << i):
                y = self.par[i][y]
        if x == y:
            return x
        for i in range(self._l - 1, -1, -1):
            nx = self.par[i][x]
            ny = self.par[i][y]
            if nx != ny:
                x = nx; y = ny
        return self.par[0][x]

    def depth_dif(self, x: int, y: int) -> int:
        assert(self.root != -1)
        z = self.lca(x, y)
        return self.depth[x] + self.depth[y] - 2 * self.depth[z]

def main():
    n, u, v = mi()
    u -= 1; v -= 1
    g = rootedtree(n)
    for _ in range(n - 1):
        a, b = mi()
        g.add_edge(a - 1, b - 1)
    ans = -1
    # du = g.bfs(u)
    # dv = g.bfs(v)
    # for i in range(n):
    #     if du[i] < dv[i]:
    #         ans = max(ans, dv[i])
    g.build(v)
    for i in range(n):
        x = g.lca(u, i)
        if g.depth_dif(u, x) < g.depth_dif(v, x):
            ans = max(ans, g.depth_dif(v, i))
    print(ans - 1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
write = sys.stdout.write
def ii(): return int(readline())
def mi(): return map(int, readline().rstrip().split())
def li(): return list(readline().rstrip())
def lmi(): return list(map(int, readline().rstrip().split()))
def end(*arg): print(*arg); sys.exit()
# template

import collections

class edge():
    def __init__(self, src: int, to: int, cost: int):
        self.src = src
        self.to = to
        self.cost = cost
    def __str__(self):
        return "(" + str(self.src) + ", " + str(self.to) + ", " + str(self.cost) + ")"

class rootedtree():
    def __init__(self, n: int) -> None:
        _l = 0
        while pow(2, _l) < n:
            _l += 1
        self._l = _l
        self.size = n
        self.par = [[-1 for i in range(n + 1)] for i in range(_l)]
        self.graph = [[] for i in range(n)]  # type:ignore
        self.depth = [-1 for i in range(n)]
        self.root = -1

    def add_edge(self, src: int, to: int, cost: int = 1):
        self.graph[src].append(edge(src, to, cost))
        self.graph[to].append(edge(to, src, cost))

    def parent(self, x: int):
        return self.par[0][x]

    def bfs(self, s: int) -> list:
        INF = 10**9
        dist = [INF] * self.size
        que = collections.deque()  # type:ignore
        que.append(s)
        dist[s] = 0
        while len(que):
            v = que.popleft()
            for e in self.graph[v]:
                if dist[e.to] != INF:
                    continue
                dist[e.to] = dist[e.src] + 1
                que.append(e.to)
        return dist

    def __dfs1(self, r):
        root = r
        self.depth[r] = 0
        que = collections.deque()
        que.append((0, root))
        while len(que) != 0:
            v = que.pop()
            for u in self.graph[v[1]]:
                if u.to != self.parent(v[1]):
                    self.par[0][u.to] = v[1]
                    self.depth[u.to] = v[0] + 1
                    que.append((v[0] + 1, u.to))

    def build(self, _root=0) -> None:
        assert(self.root == -1)
        self.root = _root
        self.__dfs1(self.root)
        for i in range(self._l - 1):
            for j in range(self.size):
                if(self.par[i][j] == -1):
                    self.par[i + 1][j] = -1
                else:
                    self.par[i + 1][j] = self.par[i][self.par[i][j]]

    def lca(self, x: int, y: int) -> int:
        assert(self.root != -1)
        if self.depth[x] > self.depth[y]:
            x, y = y, x
        dif = self.depth[y] - self.depth[x]
        for i in range(self._l - 1, -1, -1):
            if dif & (1 << i):
                y = self.par[i][y]
        if x == y:
            return x
        for i in range(self._l - 1, -1, -1):
            nx = self.par[i][x]
            ny = self.par[i][y]
            if nx != ny:
                x = nx; y = ny
        return self.par[0][x]

    def depth_dif(self, x: int, y: int) -> int:
        assert(self.root != -1)
        z = self.lca(x, y)
        return self.depth[x] + self.depth[y] - 2 * self.depth[z]

def main():
    n, u, v = mi()
    u -= 1; v -= 1
    g = rootedtree(n)
    for _ in range(n - 1):
        a, b = mi()
        g.add_edge(a - 1, b - 1)
    du = g.bfs(u)
    dv = g.bfs(v)
    ans = -1
    for i in range(n):
        if du[i] < dv[i]:
            ans = max(ans, dv[i])
    print(ans - 1)
    return


if __name__ == '__main__':
    main()