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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
I=lambda:int(input())
MI=lambda:map(int,input().split())
LI=lambda:list(map(int,input().split()))
from collections import deque

res=0
INF=10**9


N,u,v=MI()
G=[[] for _ in [0]*(N+1)]
for i in range(N-1):
    a,b=MI()
    G[a].append(b)
    G[b].append(a)


def bfs(a):
    q=deque()
    q.append(a)
    d=[INF]*(N+1)
    d[a]=0
    res=0
    while q:
        r=q.popleft()
        for nr in G[r]:
            if d[nr]==INF:
                q.append(nr)
                d[nr]=d[r]+1
                res+=1
    return d

print(max(bfs(v)[1:])-1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
from copy import deepcopy
N, u, v = map(int, input().split())
G = defaultdict(lambda: [])

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


if G[u] == [v]:
    print(0)
    exit()


def bfs(v):
    seen = [0]*(N+1)
    queue = deque()
    dist = [-1]*(N+1)
    dist[v] = 0
    seen[v] = 1
    queue.append(v)
    while queue:
        q = queue.popleft()
        for nx in G[q]:
            if seen[nx]:
                continue
            dist[nx] = dist[q] + 1
            seen[nx] = 1
            queue.append(nx)
    return dist

dist = bfs(v)
ans = 0
for node in range(1, N+1):
    if len(G[node])==1:
        #leaf
        ans = max(ans, dist[node]-1)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

adj = [[] for i in range(100001)]

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

def bfs(u):
	vis = [False]*100001
	dist = [0]*100001
	Q = deque()
	vis[u]=True
	dist[u]=0
	Q.append(u)
	while Q:
		p = Q.popleft()
		for v in adj[p]:
			if vis[v]== False:
				vis[v]=True
				Q.append(v)
				dist[v]=1+dist[p]

	return dist

l1 = bfs(u)
l2 = bfs(v)
ans = []
for i in range(1,n+1):
	if l1[i] < l2[i]:
		ans.append(l2[i])

print(max(ans)-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
def bfs(u):
	vis = [False]*100001
	dist = [0]*100001
	Q = deque()
	vis[u]=True
	dist[u]=0
	Q.append(u)
	while Q:
		p = Q.popleft()
		for v in adj[p]:
			if vis[v]== False:
				vis[v]=True
				Q.append(v)
				dist[v]=1+dist[p]

	return dist


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

adj = [[] for i in range(100001)]

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

l1 = bfs(u)
l2 = bfs(v)
ans = []
for i in range(1,n+1):
	if l1[i] < l2[i]:
		ans.append(l2[i])

print(max(ans)-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
def bfs(u):
	vis = [False]*100001
	dist = [0]*100001
	Q = deque()
	vis[u]=True
	dist[u]=0
	Q.append(u)
	while Q:
		p = Q.popleft()
		for v in adj[p]:
			if vis[v]== False:
				vis[v]=True
				Q.append(v)
				dist[v]=1+dist[p]

	return dist


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

adj = [[] for i in range(n+1)]

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

l1 = bfs(u)
l2 = bfs(v)
ans = []
for i in range(1,n+1):
	if l1[i] < l2[i]:
		ans.append(l2[i])

print(max(ans)-1)

Submission status: Wrong Answer

Solution code:
n,u,v=map(int,input().split())
ki=[[] for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  ki[a].append(b)
  ki[b].append(a)
# 次数
dn=[len(ki[i]) for i in range(n)]
inf=float('inf')
dt=[inf]*n
da=[inf]*n
u,v=u-1,v-1
from collections import deque
todo=deque([u])
dt[u]=0
while todo:
  v=todo.popleft()
  for nv in ki[v]:
    if dt[nv]>dt[v]+1:
      dt[nv]=dt[v]+1
      todo.append(nv)
todo=deque([v])
da[v]=0
while todo:
  v=todo.popleft()
  for nv in ki[v]:
    if da[nv]>da[v]+1:
      da[nv]=da[v]+1
      todo.append(nv)
ans=0
for i in range(n):
  if dn[i]>1 and dt[i]<=da[i]:ans=max(ans,da[i])
print(ans)
exit()
print(dn)
print(dt)
print(da)

Submission status: Wrong Answer

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

ABs = [list(map(lambda x:int(x[0])-1, input().split())) for _ in range(N-1)]

#%%
roots = [[] for _ in range(N)]

for AB in ABs:
    roots[AB[0]].append(AB[1])
    roots[AB[1]].append(AB[0])

#BFS
def BFS(roots, start):
    from collections import deque
    seen = [-1 for _ in range(N)]
    seen[start] = 0
    todo = deque([start])
    while len(todo) > 0:
        checking = todo.pop()
        for root in roots[checking]:
            if seen[root] == -1:
                seen[root] = seen[checking] +1
                todo.append(root)
    return seen

from_u = BFS(roots, u)
from_v = BFS(roots, v)

from collections import deque
todo = deque([u])
max_distance = from_v[u]
position = u
seen = [False for _ in range(N)]
seen[u] = True
while len(todo) > 0:
    checking = todo.pop()
    for root in roots[checking]:
        if from_u[root] < from_v[root] and seen[root] == False:
            seen[root] = True
            todo.append(root)
            if max_distance < from_v[root]:
                max_distance = from_v[root]
                position = root

print(max_distance-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, ta, ao, *AB = map(int, read().split())
    ta -= 1
    ao -= 1

    G = [[] for _ in range(N)]
    for a, b in zip(*[iter(AB)] * 2):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    dist_ta = [-1] * N
    dist_ta[ta] = 0
    queue = deque([ta])
    while queue:
        v = queue.popleft()
        for nv in G[v]:
            if dist_ta[nv] == -1:
                dist_ta[nv] = dist_ta[v] + 1
                queue.append(nv)

    dist_ao = [-1] * N
    dist_ao[ao] = 0
    queue = deque([ao])
    while queue:
        v = queue.popleft()
        for nv in G[v]:
            if dist_ao[nv] == -1:
                dist_ao[nv] = dist_ao[v] + 1
                queue.append(nv)

    d_ta = d_ao = 0
    for d1, d2 in zip(dist_ta, dist_ao):
        if d1 < d2 and d_ta <= d1:
            d_ta, d_ao = d1, d2

    if d_ao == 0:
        if dist_ta[ao] == 1:
            print(0)
        else:
            print(1)

    print(d_ao - 1)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, U, V, AB):
    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)
        g[b].append(a)

    def dfs(u):
        s = [u]
        d = {u: 0}
        while s:
            u = s.pop()
            for v in g[u]:
                if v in d:
                    continue
                d[v] = d[u] + 1
                s.append(v)
        return d

    du = dfs(U)
    dv = dfs(V)

    ans = 0
    for v in sorted(du.keys()):
        if du[v] <= dv[v]:
            ans = max(ans, du[v] + (1 if (du[v]-dv[v]) % 2 == 0 else 0))

    return ans


def main():
    N, U, V = read_int_n()
    AB = [read_int_n() for _ in range(N-1)]
    print(slv(N, U, V, AB))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, U, V, AB):
    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)
        g[b].append(a)

    def dfs(u):
        s = [u]
        d = {u: 0}
        while s:
            u = s.pop()
            for v in g[u]:
                if v in d:
                    continue
                d[v] = d[u] + 1
                s.append(v)
        return d

    du = dfs(U)
    dv = dfs(V)

    ans = 0
    for v in sorted(du.keys()):
        if du[v]<dv[v]:
            ans = max(ans, du[v] + (1 if (du[v]-dv[v]) % 2 == 0 else 0))

    return ans





def main():
    N, U, V = read_int_n()
    AB = [read_int_n() for _ in range(N-1)]
    print(slv(N, U, V, AB))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

N, u, v = map(int, input().split())
Tree = [[] for _ in range(N)]

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

def bfs(start):
  INF = 10 ** 9
  dist = [INF] * N
  dist[start] = 0
  q = deque([start])
  while q:
    v = q.popleft()
    dv = dist[v]
    for w in Tree[v]:
      dw = dv + 1
      if dw >= dist[w]:
        continue
      dist[w] = dw
      q.append(w)
  return dist

dist = bfs(v-1)
des = max(dist)

print(des-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

def bfs(s):
    seen = [0]*N
    d = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    while len(todo):
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
    return d
  
d1 = bfs(u-1)
d2 = bfs(v-1)

MAX,argmax = 0,-1
for i in range(N):
  if d1[i]<=d2[i]:
    if MAX<d1[i]:
      MAX = d1[i]
      argmax = i

print(d2[argmax]-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

def bfs(s):
    seen = [0]*N
    d = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    while len(todo):
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
    return d
  
d1 = bfs(u-1)
d2 = bfs(v-1)

MAX,argmax = 0,-1
for i in range(N):
  if d1[i]<d2[i]:
    if MAX<d1[i]:
      MAX = d1[i]
      argmax = i

if (d2[argmax]-d1[argmax])%2:
  print(d2[argmax]-1)
else:
  print(d2[argmax])

Submission status: Wrong Answer

Solution code:
from collections import deque

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

def bfs(s):
    seen = [0]*N
    d = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    while len(todo):
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
    return d
  
d1 = bfs(u-1)
d2 = bfs(v-1)

MAX,argmax = 0,-1
for i in range(N):
  if d1[i]<d2[i]:
    if MAX<d1[i]:
      MAX = d1[i]
      argmax = i
print(d2[argmax]-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,u,v=map(int, input().split())
u-=1
v-=1
es=[[] for i in range(n)]
for i in range(n-1):
    a0,b0=map(int, input().split())
    es[a0-1].append(b0-1)
    es[b0-1].append(a0-1)
aoki=[-1]*n
aoki[v]=0
choku=[-1]*n
choku[u]=0
from collections import deque
que=deque([])
que.append(u)
while que:
    now=que.popleft()
    step=choku[now]
    for e in es[now]:
        if choku[e]==-1:
            choku[e]=step+1
            que.append(e)

que=deque([])
que.append(v)
while que:
    now=que.popleft()
    step=aoki[now]
    for e in es[now]:
        if aoki[e]==-1:
            aoki[e]=step+1
            que.append(e)

end=None

for i in range(n):
    if len(es[i])==1: 
        if choku[i]==0 and aoki[i]==1:
            print(0)
            exit()
        if choku[i]!=0:
            if end==None and aoki[i]-choku[i]>0:
                end=(aoki[i]-choku[i],aoki[i],choku[i])
            elif aoki[i]-choku[i]>0:
                if end[0]==aoki[i]-choku[i] and aoki[i]>end[1]:
                    end=(aoki[i]-choku[i],aoki[i],choku[i])
                elif end[0]>aoki[i]-choku[i]:
                    end=(aoki[i]-choku[i],aoki[i],choku[i])

#print(end)
if end!=None:
    print(max(end[2]-(end[0]-1), aoki[u]-1))
else:
    print(aoki[u]-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,u,v=map(int, input().split())
u-=1
v-=1
es=[[] for i in range(n)]
for i in range(n-1):
    a0,b0=map(int, input().split())
    es[a0-1].append(b0-1)
    es[b0-1].append(a0-1)
aoki=[-1]*n
aoki[v]=0
choku=[-1]*n
choku[u]=0
from collections import deque
que=deque([])
que.append(u)
while que:
    now=que.popleft()
    step=choku[now]
    for e in es[now]:
        if choku[e]==-1:
            choku[e]=step+1
            que.append(e)

que=deque([])
que.append(v)
while que:
    now=que.popleft()
    step=aoki[now]
    for e in es[now]:
        if aoki[e]==-1:
            aoki[e]=step+1
            que.append(e)

end=None

for i in range(n):
    if len(es[i])==1: 
        if choku[i]==0 and aoki[i]==1:
            print(0)
            exit()
        if choku[i]!=0:
            if end==None and aoki[i]-choku[i]>0:
                end=(aoki[i]-choku[i],aoki[i],choku[i])
            elif aoki[i]-choku[i]>0:
                if end[0]==aoki[i]-choku[i] and aoki[i]>end[1]:
                    end=(aoki[i]-choku[i],aoki[i],choku[i])
                #elif end[0]>aoki[i]-choku[i]:
                    #end=(aoki[i]-choku[i],aoki[i],choku[i])

#print(end)
if end!=None:
    print(max(end[2]-(end[0]-1), aoki[u]-1))
else:
    print(aoki[u]-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,u,v=map(int, input().split())
u-=1
v-=1
es=[[] for i in range(n)]
for i in range(n-1):
    a0,b0=map(int, input().split())
    es[a0-1].append(b0-1)
    es[b0-1].append(a0-1)
aoki=[-1]*n
aoki[v]=0
choku=[-1]*n
choku[u]=0
from collections import deque
que=deque([])
que.append(u)
while que:
    now=que.popleft()
    step=choku[now]
    for e in es[now]:
        if choku[e]==-1:
            choku[e]=step+1
            que.append(e)

que=deque([])
que.append(v)
while que:
    now=que.popleft()
    step=aoki[now]
    for e in es[now]:
        if aoki[e]==-1:
            aoki[e]=step+1
            que.append(e)

end=None

for i in range(n):
    if len(es[i])==1: 
        if choku[i]==0:
            continue
        if end==None and aoki[i]-choku[i]>0:
            end=(aoki[i]-choku[i],aoki[i],choku[i])
        elif aoki[i]-choku[i]>0:
            if end[0]==aoki[i]-choku[i] and aoki[i]>end[1]:
                end=(aoki[i]-choku[i],aoki[i],choku[i])
            elif end[0]>aoki[i]-choku[i]:
                end=(aoki[i]-choku[i],aoki[i],choku[i])

if end!=None:
    print(max(end[2]-(end[0]-1), aoki[u]-1))
else:
    print(aoki[u]-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,u,v=map(int, input().split())
u-=1
v-=1
es=[[] for i in range(n)]
for i in range(n-1):
    a0,b0=map(int, input().split())
    es[a0-1].append(b0-1)
    es[b0-1].append(a0-1)
aoki=[-1]*n
aoki[v]=0
choku=[-1]*n
choku[u]=0
from collections import deque
que=deque([])
que.append(u)
while que:
    now=que.popleft()
    step=choku[now]
    for e in es[now]:
        if choku[e]==-1:
            choku[e]=step+1
            que.append(e)

que=deque([])
que.append(v)
while que:
    now=que.popleft()
    step=aoki[now]
    for e in es[now]:
        if aoki[e]==-1:
            aoki[e]=step+1
            que.append(e)

end=None

for i in range(n):
    if len(es[i])==1: 
        if end==None and aoki[i]-choku[i]>0:
            end=(aoki[i]-choku[i],aoki[i],choku[i])
        elif aoki[i]-choku[i]>0:
            if end[0]==aoki[i]-choku[i] and aoki[i]>end[1]:
                end=(aoki[i]-choku[i],aoki[i],choku[i])
            elif end[0]>aoki[i]-choku[i]:
                end=(aoki[i]-choku[i],aoki[i],choku[i])

if end!=None:
    print(max(end[2]-(end[0]-1), aoki[u]-1))
else:
    print(aoki[u]-1)

Submission status: Wrong Answer

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

def dfs(v,d):
  ret=d
  checked[v]=1
  for u in g[v]:
    if checked[u]==1:
      continue
    ret=max(ret,dfs(u,d+1))
  return ret  

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)
checked=[0]*(n+1)
ans=dfs(v,0)-1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,u,v = map(int,input().split())
branch = [list(map(int,input().split())) for _ in range(n-1)]
link = [[] for _ in range(n)]
for i in branch:
    link[i[0]-1].append(i[1]-1)
    link[i[1]-1].append(i[0]-1)

q_a = deque([u-1])
q_b = deque([v-1])
dist_a = [-1 for _ in range(n)]
dist_b = [-1 for _ in range(n)]
dist_a[u-1] = 0
dist_b[v-1] = 0
while len(q_a)>0:
    check = q_a.popleft()
    for j in link[check]:
        if dist_a[j] == -1:
            dist_a[j] = dist_a[check]+1
            q_a.append(j)
while q_b:
    check = q_b.popleft()
    for m in link[check]:
        if dist_b[m] == -1:
            dist_b[m] = dist_b[check]+1
            q_b.append(m)

ans = 0
flg = 100000
for k in range(n):
    compare = 0
    if dist_b[k]>dist_a[k] and dist_a[k] != 0:
        if (dist_b[k] - dist_a[k])%2 == 1:
            compare = dist_b[k]-1
        else:
            compare = dist_b[k]
    elif dist_b[k] == dist_a[k]:
        flg = min(flg,dist_b[k])
        compare = flg      
    if compare > ans:
        ans = compare
print(ans)

Submission status: Wrong Answer

Solution code:
class LCA(object):
    def __init__(self, n, root, edges, decrement=True):
        """
        :param n: 頂点数
        :param root: 木の根
        :param edges: 辺のリスト
        :param decrement:

        :param self.depth: rootを根とした時の各頂点の深さ
        """
        self.n = n
        self.decrement = decrement
        self.root = root - self.decrement
        self.edges = [set() for _ in range(self.n)]
        for x, y in edges:
            self.add_edge(x,y)
        self.k_max = (self.n - 1).bit_length()
        self.depth = [-1 if i != self.root else 0 for i in range(self.n)]
        self.doubling = [[-1] * self.n for _ in range(self.k_max)]
        self.parent = [-1]*self.n
        self.dfs()
        for i in range(1, self.k_max):
            for k in range(self.n):
                if self.doubling[i - 1][k] != -1:
                    self.doubling[i][k] = self.doubling[i - 1][self.doubling[i - 1][k]]

    def add_edge(self, x, y):
        """
        後から追加した場合は update() をする
        """
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        self.edges[y].add(x)

    def update(self):
        self.depth = [-1 if i != self.root else 0 for i in range(self.n)]
        self.doubling = [[-1] * self.n for _ in range(self.k_max)]
        self.dfs()
        for i in range(1, self.k_max):
            for k in range(self.n):
                if self.doubling[i - 1][k] != -1:
                    self.doubling[i][k] = self.doubling[i - 1][self.doubling[i - 1][k]]


    def dfs(self):
        next_set = [self.root]
        while next_set:
            p = next_set.pop()
            for q in self.edges[p]:
                if self.depth[q] == -1:
                    self.depth[q] = self.depth[p] + 1
                    self.doubling[0][q] = p
                    next_set += [q]

    def get(self, u, v):
        """
        :return: u と v の最近共通祖先の頂点番号を返す
        """
        if self.decrement:
            u -= 1
            v -= 1
        if self.depth[v] < self.depth[u]:
            u, v = v, u

        for i in range(self.k_max):
            """ v を u の位置まで遡らせる """
            if (self.depth[v] - self.depth[u]) >> i & 1:
                v = self.doubling[i][v]
        if v == u:
            """ v の祖先が u だった場合"""
            return u + self.decrement

        for i in range(self.k_max-1, -1, -1):
            """ k = 2**(k_max-1), ..., 2**0 について、 
            「k個先を確認して共通祖先でないなら u1,v1 をk個先に移動」ということを繰り返す"""
            parent_u, parent_v = self.doubling[i][u], self.doubling[i][v]
            if parent_u != parent_v:
                u, v = parent_u, parent_v
        return self.doubling[0][u] + self.decrement

    def distance(self, u, v):
        """
        :return: u と v の最短距離を求める
        備考: 経路復元をしようとすると O(E)かかるので、経路復元が必要な場合は dfs を用いるとよい
        """
        lca_at = self.get(u,v)
        if self.decrement:
            u -= 1
            v -= 1
            lca_at -= 1
        return self.depth[u] + self.depth[v] - 2*self.depth[lca_at]

    def distance_list(self, start=1, save=False):
        """
        :param start: スタート地点
        :return: スタート地点から各点への距離のリスト
        """
        dist = [-1]*self.n
        if self.decrement:
            start -= 1
        if not save:
            self.parent = [-1] * self.n
        p, t = start, 0
        self.parent[p] = -2
        dist[p] = 0
        next_set = deque([(p, t)])

        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                if self.parent[q] != -1:
                    continue
                if q == xx-1:
                    continue
                dist[q] = t + 1
                self.parent[q] = p
                next_set.append((q, t + 1))
        return dist

    def most_distant_point(self, start=1, save=False):
        """
        計算量　O(N)
        :return: (start から最も遠い頂点, 距離)
        """
        if not save:
            self.parent = [-1] * self.n
        res = (start - self.decrement, 0)
        temp = 0
        for i, dist in enumerate(self.distance_list(start, save=save)):
            if dist > temp:
                temp = dist
                res = (i + self.decrement, dist)
        return res

#################################################################################################
import sys
from collections import deque
input = sys.stdin.readline

N, u, v = map(int, input().split())
edges = []
for _ in range(N-1):
    x, y = map(int, input().split())
    edges.append((x,y))
xx = -2
lca = LCA(N, 1, edges, decrement=True)
p = lca.get(u,v)
lu, lv = lca.depth[u-1] - lca.depth[p-1], lca.depth[v-1] - lca.depth[p-1]
if lu <= lv:
    q, _ = lca.most_distant_point(v)
    print(lca.distance(q,v)-1)
    exit()
else:
    L = (lu+lv)//2
    cnt = 0
    lca.distance_list()
    if lca.depth[u-1] >= lca.depth[v-1]:
        a = u-1
        while cnt < L:
            a = lca.parent[a]
            cnt += 1
        xx, s = lca.parent[a], a
    else:
        a = v-1
        while cnt < L+1:
            a = lca.parent[a]
            cnt += 1
        xx, s = a, lca.parent[a]
    q, _ = lca.most_distant_point(s)
    print(lca.distance(q,v)-1)
    exit()

Submission status: Wrong Answer

Solution code:
class LCA(object):
    def __init__(self, n, root, edges, decrement=True):
        """
        :param n: 頂点数
        :param root: 木の根
        :param edges: 辺のリスト
        :param decrement:

        :param self.depth: rootを根とした時の各頂点の深さ
        """
        self.n = n
        self.decrement = decrement
        self.root = root - self.decrement
        self.edges = [set() for _ in range(self.n)]
        for x, y in edges:
            self.add_edge(x,y)
        self.k_max = (self.n - 1).bit_length()
        self.depth = [-1 if i != self.root else 0 for i in range(self.n)]
        self.doubling = [[-1] * self.n for _ in range(self.k_max)]
        self.parent = [-1]*self.n
        self.dfs()
        for i in range(1, self.k_max):
            for k in range(self.n):
                if self.doubling[i - 1][k] != -1:
                    self.doubling[i][k] = self.doubling[i - 1][self.doubling[i - 1][k]]

    def add_edge(self, x, y):
        """
        後から追加した場合は update() をする
        """
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        self.edges[y].add(x)

    def update(self):
        self.depth = [-1 if i != self.root else 0 for i in range(self.n)]
        self.doubling = [[-1] * self.n for _ in range(self.k_max)]
        self.dfs()
        for i in range(1, self.k_max):
            for k in range(self.n):
                if self.doubling[i - 1][k] != -1:
                    self.doubling[i][k] = self.doubling[i - 1][self.doubling[i - 1][k]]


    def dfs(self):
        next_set = [self.root]
        while next_set:
            p = next_set.pop()
            for q in self.edges[p]:
                if self.depth[q] == -1:
                    self.depth[q] = self.depth[p] + 1
                    self.doubling[0][q] = p
                    next_set += [q]

    def get(self, u, v):
        """
        :return: u と v の最近共通祖先の頂点番号を返す
        """
        if self.decrement:
            u -= 1
            v -= 1
        if self.depth[v] < self.depth[u]:
            u, v = v, u

        for i in range(self.k_max):
            """ v を u の位置まで遡らせる """
            if (self.depth[v] - self.depth[u]) >> i & 1:
                v = self.doubling[i][v]
        if v == u:
            """ v の祖先が u だった場合"""
            return u + self.decrement

        for i in range(self.k_max-1, -1, -1):
            """ k = 2**(k_max-1), ..., 2**0 について、 
            「k個先を確認して共通祖先でないなら u1,v1 をk個先に移動」ということを繰り返す"""
            parent_u, parent_v = self.doubling[i][u], self.doubling[i][v]
            if parent_u != parent_v:
                u, v = parent_u, parent_v
        return self.doubling[0][u] + self.decrement

    def distance(self, u, v):
        """
        :return: u と v の最短距離を求める
        備考: 経路復元をしようとすると O(E)かかるので、経路復元が必要な場合は dfs を用いるとよい
        """
        lca_at = self.get(u,v)
        if self.decrement:
            u -= 1
            v -= 1
            lca_at -= 1
        return self.depth[u] + self.depth[v] - 2*self.depth[lca_at]

    def distance_list(self, start=1, save=False):
        """
        :param start: スタート地点
        :return: スタート地点から各点への距離のリスト
        """
        dist = [-1]*self.n
        if self.decrement:
            start -= 1
        if not save:
            self.parent = [-1] * self.n
        p, t = start, 0
        self.parent[p] = -2
        dist[p] = 0
        next_set = deque([(p, t)])

        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                if self.parent[q] != -1:
                    continue
                if q == x-1:
                    continue
                dist[q] = t + 1
                self.parent[q] = p
                next_set.append((q, t + 1))
        return dist

    def most_distant_point(self, start=1, save=False):
        """
        計算量　O(N)
        :return: (start から最も遠い頂点, 距離)
        """
        res = (start - self.decrement, 0)
        temp = 0
        for i, dist in enumerate(self.distance_list(start, save=save)):
            if dist > temp:
                temp = dist
                res = (i + self.decrement, dist)
        return res

#################################################################################################
import sys
from collections import deque
input = sys.stdin.readline

N, u, v = map(int, input().split())
edges = []
for _ in range(N-1):
    x, y = map(int, input().split())
    edges.append((x,y))

lca = LCA(N, 1, edges, decrement=True)
p = lca.get(u,v)
lu, lv = lca.depth[u-1] - lca.depth[p-1], lca.depth[v-1] - lca.depth[p-1]
if lu <= lv:
    q, _ = lca.most_distant_point(v)
    print(lca.distance(q,v)-1)
    exit()
else:
    L = (lu+lv)//2
    a, x, cnt = u-1, -2, 0
    lca.distance_list()
    while cnt < L+1:
        a = lca.parent[a]
        cnt += 1
    x = a+1
    q, _ = lca.most_distant_point(u)
    print(lca.distance(q,v)-1)
    exit()