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

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

from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist

du = dijkstra(g,N,u-1)
dv = dijkstra(g,N,v-1)
d = []
for i in range(N):
    if dv[i]-du[i]>=0:
        d.append(dv[i])
ans = max(d)-1
print(ans)

Solution (Python):
N,u,v=[int(i) for i in input().split(" ")]
u-=1
v-=1
graph={}
for i in range(N-1):
    A,B=[int(j) for j in input().split(" ")]
    if A-1 in graph:
        d=graph[A-1]
        d.append(B-1)
        graph[A-1]=d
    else:
        graph[A-1]=[B-1]
    if B-1 in graph:
        d=graph[B-1]
        d.append(A-1)
        graph[B-1]=d
    else:
        graph[B-1]=[A-1]

dist_takahashi=[-1 for i in range(N)]
dist_takahashi[u]=0
next=[u]
d=1
while -1 in dist_takahashi:
    _next=[]
    for n in next:
        nodes=graph[n]
        for i in nodes:
            if dist_takahashi[i]==-1:
                _next.append(i)
    for n in _next:
        dist_takahashi[n]=d
    next=_next
    d+=1

dist_aoki=[-1 for i in range(N)]
dist_aoki[v]=0
next=[v]
d=1
while -1 in dist_aoki:
    _next=[]
    for n in next:
        nodes=graph[n]
        for i in nodes:
            if dist_aoki[i]==-1:
                _next.append(i)
    for n in _next:
        dist_aoki[n]=d
    next=_next
    d+=1


retval=0

for i in range(N):
    if dist_aoki[i]<dist_takahashi[i]:
        continue

    retval=max(retval,dist_aoki[i]-1)


print(retval)

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
def prime_decomposition(n): 
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(int(n))
  return table

def make_divisors(n): 
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

import heapq
import sys

input = sys.stdin.readline

def dijkstra_heap(s,edge):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])

n,w,p = map(int,input().split())

edge = [[] for i in range(n)]
dg = 10**7

for i in range(n-1):
    x,y = map(int,input().split())
    z = 1
    x -= 1
    y -= 1
    edge[x].append(dg + y)
    edge[y].append(dg + x)

import heapq




"""
for _ in [0]*m:
    u,v,w = map(int,input().split())
    edge[u-1].append(w*dg+v-1)
    
"""



s = w-1
ss = p-1
d = [-1]*n
d[s] = 0

d2 = [-1]*n
d2[ss] = 0
edgelist = []
edgelist2 = []
for e in edge[s]:
    heapq.heappush(edgelist,e)

for e in edge[ss]:
    heapq.heappush(edgelist2,e)
    

while len(edgelist):
    minedge = heapq.heappop(edgelist)
    v,c = minedge%dg,minedge//dg
    if d[v] >= 0:
        continue
    d[v] = c
    for e in edge[v]:
        vNext = e%dg
        if d[vNext]:
            heapq.heappush(edgelist, (e//dg+d[v])*dg + vNext)

while len(edgelist2):
    minedge = heapq.heappop(edgelist2)
    v,c = minedge%dg,minedge//dg
    if d2[v] >= 0:
        continue
    d2[v] = c
    for e in edge[v]:
        vNext = e%dg
        if d2[vNext]:
            heapq.heappush(edgelist2, (e//dg+d2[v])*dg + vNext)


co = 0
for i in range(n):
    if co < d2[i] and d2[i]-d[i]>=0:
        co = d2[i]

print(co-1)

Solution (Python):
from collections import deque
N,u,v = map(int,input().split())
u -= 1
v -= 1 
cango = [[] for i in range(N)]

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

pres = [-1]*N
fromaoki = [-1]*N
fromaoki[v] = 0
went = [False]*N
queue =deque()
queue.append([v,0])
went[v] = True
while queue:
    curpos,prespos = queue.popleft()
    pres[curpos] = prespos
    for togo in cango[curpos]:
        if not went[togo]:
            went[togo] = True
            fromaoki[togo] = fromaoki[curpos]+1
            queue.append([togo,curpos])

route=[]
tadori = u
while tadori!=v:
    route.append(tadori)
    tadori = pres[tadori]
route.append(v)

nekko = route[len(route)//2-1] 
cantgo = route[len(route)//2]
cango[nekko].remove(cantgo)
cango[cantgo].remove(nekko)


def BFS(start):
    dist = [-1]*N
    dist[start] = 0
    went = [False]*N
    queue =deque()
    queue.append(start)
    went[start] = True
    while queue:
        curpos = queue.popleft()
        for togo in cango[curpos]:
            if not went[togo]:
                went[togo] = True
                dist[togo] = dist[curpos]+1
                queue.append(togo)
    return dist

fromnekko = BFS(nekko)
maxdist = max(fromnekko)
maxpos = fromnekko.index(maxdist)
print(fromaoki[maxpos]-1)

Solution (Python):
import sys
input = sys.stdin.readline
from heapq import heappush, heappop
inf = float('inf')
mod = 10**9 + 7



class Dijkstra:
    def __init__(self, to:list, start:int):
        self.N = len(to)
        self.to = [s[:] for s in to]
        self.start = start
        self.dist = [inf] * self.N
        self.dist[start] = 0
        
        
        
        self.pq = [(self.dist[start], start)]

    
    def update(self) -> None:
        while self.pq:
            _, v = heappop(self.pq)
            for nv, w in self.to[v]:
                if self.dist[nv] > self.dist[v] + w:
                    self.dist[nv] = self.dist[v] + w
                    heappush(self.pq, (self.dist[nv], nv))
                
                
                

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

T = Dijkstra(to, u)
T.update()
A = Dijkstra(to, v)
A.update()

adopt = 0
for d1, d2 in zip(T.dist, A.dist):
    if d1 > d2:
        continue
    adopt = max(adopt, d2)

ans = adopt - 1
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

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

depth = [[-1,-1] for _ in range(N+1)] 
depth[v][0] = 0
depth[u][1] = 0
def dfs1(E,v):
    vv = E[v]
    for vvv in vv:
        if depth[vvv][0] == -1:
            depth[vvv][0] = depth[v][0] + 1
            dfs1(E,vvv)

def dfs2(E,v):
    vv = E[v]
    for vvv in vv:
        if depth[vvv][1] == -1:
            depth[vvv][1] = depth[v][1] + 1
            dfs2(E,vvv)
dfs1(E,v)
dfs2(E,u)
depth = sorted(depth, reverse=True)
idx = 0
while True:
    if depth[idx][0] - depth[idx][1] >= 1:
        print(depth[idx][0]-1)
        exit()
    else:
        idx += 1

Solution (Python):
from collections import deque
import sys

N, u, v = map(int,input().split())
side = [[]for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    side[a-1].append(b-1)
    side[b-1].append(a-1)
node = [[-1,-1,-1]for i in range(N)]
node[v-1] = [0,v-1,-1]
queue = deque([v-1])
leaf = []
while queue:
    q = queue.popleft()
    hoge = 0
    for i in side[q]:
        if node[i][0] == -1:
            node[i][0] = node[q][0]+1
            node[i][1] = q
            queue.append(i)
            hoge += 1
    if hoge == 0:
        node[q][2] = node[q][0]
        leaf.append(q)

leaf.sort(key = lambda x:node[x][0], reverse=True)
for x in leaf:
    while x != v-1:
        if node[node[x][1]][2] < node[x][2]:
            node[node[x][1]][2] = node[x][2]
            x = node[x][1]
        else:
            x = v-1

u -= 1
turn = 0
while 1:
    turn += 1
    if node[node[u][1]][0] > turn:
        u = node[u][1]
    else:
        next = node[u][1]
        node[node[u][1]][2] = 0
        for i in side[u]:
            if node[i][2] > node[next][2]:
                next = i
        u = next
    if node[u][0] < turn:
        break

print(node[u][0])

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,tk,ao = MI()
    tk-=1
    ao-=1

    AB=LLIN_(N-1)
    edge = [[]for _ in range(N)]
    for a,b in AB:
        edge[a].append(b)
        edge[b].append(a)
    
    dist_from_tk = [-inf]*N
    dist_from_ao = [-inf]*N
    
    dist_from_ao[ao]=0
    q = deque([ao])
    while q:
        fr = q.popleft()
        for to in edge[fr]:
            if dist_from_ao[to]!=-inf:
                continue
            
            dist_from_ao[to]=dist_from_ao[fr]+1
            q.append(to)
    

    dist_from_tk[tk]=0
    q = deque([tk])
    mid = -inf
    add_flag=0
    while q:
        fr = q.popleft()
        for to in edge[fr]:
            if dist_from_tk[to]!=-inf:
                continue
            if dist_from_ao[to]<=dist_from_tk[fr]+1:
                mid = fr
                if(dist_from_ao[to]==dist_from_tk[fr]+1):
                    add_flag=1
                continue
            
            dist_from_tk[to]=dist_from_tk[fr]+1
            q.append(to)
    
    
    
    


    dist_from_mid = [-inf]*N
    dist_from_mid[mid]=0
    q = deque([mid])
    while q:
        fr = q.popleft()
        for to in edge[fr]:
            if dist_from_mid[to]!=-inf:
                continue
            if dist_from_tk[to]==-inf:
                continue
            
            dist_from_mid[to]=dist_from_mid[fr]+1
            q.append(to)
    
    
    if dist_from_ao[tk]==1 and max(dist_from_tk)==0: 
        print(0)
    elif max(dist_from_tk)==0: 
        print(1)
    else:
        ans = dist_from_tk[mid]+max(dist_from_mid)
        print(ans+add_flag)
    

if __name__ == '__main__':
    main()

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

e_list = [[] for _ in range(N)]

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

def calc_depth_table(v):
	queue = [[v, None, 0]]
	depth_table = [0] * N
	depth_table[v] = 0
	
	while queue:
		cur, pre, depth = queue.pop()
		depth += 1
		for n in e_list[cur]:
			if n != pre:
				queue.append([n, cur, depth])
				depth_table[n] = depth
	return depth_table

def calc_depth_table2(depth_from_v, u):
	queue = [[u, None, 0, depth_from_v[u], u]]
	depth_table = [0] * N
	depth_table[u] = (0, depth_from_v[u], u)
	
	while queue:
		cur, pre, depth, min_depth_from_v, min_depth_point = queue.pop()
		depth += 1
		for n in e_list[cur]:
			if n != pre:
				depth2 = depth_from_v[n]
				if min_depth_from_v > depth2:
					new_min_depth = depth2
					new_min_depth_point = n
				else:
					new_min_depth = min_depth_from_v
					new_min_depth_point = min_depth_point
				queue.append([n, cur, depth, new_min_depth, new_min_depth_point])
				depth_table[n] = (depth, new_min_depth, new_min_depth_point)
	return depth_table

depth_from_v = calc_depth_table(v)
depth_from_u = calc_depth_table2(depth_from_v, u)




max_count = 0
for i in range(N):
	a_dist = depth_from_v[i]
	t_dist, a_hit_dist, hit_pos = depth_from_u[i]
	t_hit_dist = depth_from_u[hit_pos][0]
	

	if t_hit_dist < a_hit_dist:


		if max_count < a_dist - 1:
			max_count = a_dist - 1



print(max_count)

Solution (Python):
from sys import stdout
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True 
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,u,v = inm()
u -= 1
v -= 1
dst = [ [] for i in range(n) ]
for i in range(n-1):
    a,b = inm()
    dst[a-1].append(b-1)
    dst[b-1].append(a-1)

dist = [-1]*n
q = [(v,0)]
while len(q)>0:
    i,d = q.pop()
    dist[i] = d
    for j in dst[i]:
        if dist[j] == -1:
            q.append((j,d+1))

r = dist[u]//2+1
t = dist[u]
w = u
while t>r:
    for z in dst[w]:
        if dist[z] == t-1:
            w = z
            t -= 1
            break

searched = [-1]*n
searched[w] = True
mx = t
q = [w]
while len(q)>0:
    x = q.pop()
    for y in dst[x]:
        if dist[y]>dist[x]:
            q.append(y)
            mx = max(mx,dist[y])
print(mx-1)

Solution (Python):
import sys


def inpl():
    return list(map(int, input().split()))


def set_depth(i):
    for e in edge[i]:
        if depth[e] != -1:
            continue
        depth[e] = depth[i] + 1
        parent[e] = i
        set_depth(e)
    return


def get_root_v(can_depth, u):
    if depth[u] == can_depth:
        return u
    else:
        return get_root_v(can_depth, parent[u])


def find_max_depth(v):
    if len(edge[v]) == 1 and parent[v] == edge[0]:
        return depth[v]

    tmp = depth[v]
    for e in edge[v]:
        if parent[v] == e:
            continue
        else:
            tmp = max(tmp, find_max_depth(e))
    return tmp


sys.setrecursionlimit(2 * 10**6)

N, u, v = inpl()
AB = [inpl() for _ in range(N - 1)]
edge = [[] for i in range(N + 1)]
for a, b in AB:
    edge[a].append(b)
    edge[b].append(a)

depth = [-1 for i in range(N + 1)]
depth[v] = 0

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

set_depth(v)

can_depth = depth[u] - (depth[u] - 1) // 2
root_v = get_root_v(can_depth, u)

print(find_max_depth(root_v) - 1)

Solution (Python):
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def dfsv(u,pu=-1,d=0):
        dist[u]=d
        for cu in to[u]:
            if cu==pu:continue
            dfsv(cu,u,d+1)

    def dfsu(u,pu=-1,d=0):
        res=dist[u]
        for cu in to[u]:
            if cu==pu:continue
            if dist[cu]>d+1:
                ret=dfsu(cu,u,d+1)
                if ret>res:res=ret
        return res

    to=defaultdict(list)
    n,u,v=MI()
    u,v=u-1,v-1
    for _ in range(n-1):
        a,b=MI1()
        to[a].append(b)
        to[b].append(a)
    dist=[0]*n
    dfsv(v)
    
    print(dfsu(u)-1)




main()

Solution (Python):
import sys
sys.setrecursionlimit(10**5)
n,u,v=map(int,input().split())
u=u-1
v=v-1
root=[[] for i in range(n)]

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

dp=[[-1]*n for i in range(2)]
dp[0][u]=0
dp[1][v]=0
def dfs(node,depth,par,flag):
    for vertex in root[node]:
        if vertex == par or dp[flag][vertex]!=-1:
            continue
        dp[flag][vertex]=depth+1
        dfs(vertex,depth+1,node,flag)
    return
dfs(u,0,u,0)
dfs(v,0,v,1)
buf=-1
buf1=0

for i in range(n):
    if dp[0][i]<dp[1][i] and dp[1][i]>buf:
        buf=dp[1][i]
        buf1=dp[0][i]
print(buf-1)

Solution (Python):
N,u,V = map(int,input().split())

abl = []
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)





from collections import deque
dist = [-1]*N
que = deque([u-1])
dist[u-1] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)

from collections import deque
dist2 = [-1]*N
que = deque([V-1])
dist2[V-1] = 0
while que:
    v = que.popleft()
    d = dist2[v]
    for w in G[v]:
        if dist2[w] > -1:
            continue
        dist2[w] = d + 1
        que.append(w)

ans = 0
import math
for d, d2 in zip(dist, dist2):
    if d2 > d:
        ans = max(d2-1, ans)
print(ans)

Solution (Python):
words = lambda t : list(map(t, input().split()))

n,u,v = words(int)
u -= 1
v -= 1

edges = [[] for i in range(n)]
for i in range(n-1):
    f,t = words(int)
    edges[f-1].append(t-1)
    edges[t-1].append(f-1)

from queue import Queue
def bfs1(edges,stt):
    dist = [-1] * n
    q = Queue()
    q.put(stt)
    dist[stt] = 0
    
    while not q.empty():
        v = q.get()
        
        for c in edges[v]:
            
            if dist[c] == -1:
                dist[c] = dist[v]+1
                q.put(c)
    return dist

dist_v = bfs1(edges, v)
dist_u = bfs1(edges, u)





ans = 0
for i in range(n):
    if dist_v[i] > dist_u[i]:
        ans = max(ans,dist_v[i])

print(max(ans-1,0))

Solution (Python):
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N, u, v = map(int, input().split())
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    par = [int(i) for i in range(N)]
    son = [[] for _ in range(N)]
    q = deque()
    for s in edge[v-1]:
        q.append((s, v-1))
        son[v-1].append(s)
    while q:
        now, pre = q.popleft()
        par[now] = pre
        for s in edge[now]:
            if s != pre:
                son[now].append(s)
                q.append((s, now))

    distAT = 0
    Tnow = u-1
    while Tnow != v-1:
        distAT += 1
        Tnow = par[Tnow]
    
    ans = (distAT - 1) // 2
    turn = u - 1
    for _ in range(ans): turn = par[turn]
    dist = [-1] * N
    q.append((turn, 0))
    maxback = 0
    while q:
        now, d = q.popleft()
        maxback = max(maxback, d)
        for s in son[now]: q.append((s, d+1))

    if distAT % 2 == 0:
        ans += maxback + 1
    else: ans += maxback
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

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


dist = [[float('inf')] * n for i in range(2)]
visited = [[False] * n for i in range(2)]
dq = [collections.deque() for i in range(2)]

dq[0].append((0, u-1))
dq[1].append((0, v - 1))

for i in range(2):
    while dq[i]:
        d, v = dq[i].popleft()
        if visited[i][v]:
            continue
        visited[i][v] = True
        dist[i][v] = d
        for nv in graph[v]:
            if visited[i][nv]:
                continue
            dq[i].append((d + 1, nv))

dq[0].append((0, u-1))
visited = [[False] * n for i in range(2)]
i = 0
while dq[i]:
    d, v = dq[i].popleft()
    if visited[i][v]:
        continue
    visited[i][v] = True
    if dist[0][v] >= dist[1][v]:
        continue
    for nv in graph[v]:
        if visited[i][nv]:
            continue
        dq[i].append((d + 1, nv))

max_turn = 0
for i in range(n):
    if not visited[0][i]:
        continue
    max_turn = max(max_turn, dist[1][i]-1)
print(max_turn)

Solution (Python):
def djkstra(a,in_connect_list,v):
    out_shortest_list = [10**15 for i in range(v)]
    out_shortest_list[a] = 0
    searching_list = [a]
    
    while searching_list != []:
        new_search_list = []
        for i in searching_list:
            for c in in_connect_list[i]: 
                if out_shortest_list[c] == 10**15:
                    out_shortest_list[c] = 1 + out_shortest_list[i]
                    new_search_list.append(c)
        searching_list = new_search_list
    return out_shortest_list

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

takahashi_time = djkstra(u, connnect, n)
aoki_time = djkstra(v, connnect, n)

ans_time = [ aoki_time[i]  for i in range(n) if aoki_time[i] >= takahashi_time[i] ]

print(max(0, max(ans_time)-1))

Solution (Python):
n, u, v, *L = map(int, open(0).read().split())
dist_f_v = [-1] * n
con = [[] for _ in range(n)]
for s, t in zip(*[iter(L)] * 2):
	con[s - 1].append(t - 1)
	con[t - 1].append(s - 1)
dist_f_v[v - 1] = 0
q = [v - 1]
while q:
	cur = q.pop()
	for nxt in con[cur]:
		if dist_f_v[nxt] < 0:
			dist_f_v[nxt] = dist_f_v[cur] + 1
			q.append(nxt)
dist_f_u = [-1] * n
dist_f_u[u - 1] = 0
q = [u - 1]
m = 0
while q:
	cur = q.pop()
	m = max(m, dist_f_v[cur])
	for nxt in con[cur]:
		if dist_f_u[nxt] > -1:
			continue
		if dist_f_u[cur] + 1 < dist_f_v[nxt]:
			dist_f_u[nxt] = dist_f_u[cur] + 1
			q.append(nxt)
		elif dist_f_u[cur] + 1 == dist_f_v[nxt]:
			dist_f_u[nxt] = dist_f_u[cur] + 1
print(m - 1)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)

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)


ftakahasi = [-1 for i in range(n)]
faoki = [-1 for i in range(n)]


def dfst(i, n):
    ftakahasi[i] = n
    for sg in g[i]:
        if ftakahasi[sg] == -1:
            dfst(sg, n + 1)


def dfsa(i, n):
    faoki[i] = n
    for sg in g[i]:
        if faoki[sg] == -1:
            dfsa(sg, n + 1)


dfst(u - 1, 0)
dfsa(v - 1, 0)
res1 = 0
for i in range(n):
    pt = ftakahasi[i]
    pa = faoki[i]
    if pt < pa:
        tres = pa - 1
        res1 = max(res1, tres)
print(res1)

Solution (Python):
def depth(u, E):
    ud = [None] * len(E)
    cur = E[u].copy()
    ud[u] = 0
    d = 1
    while cur:
        nxt = []
        for c in cur:
            ud[c] = d
            for i in E[c]:
                if ud[i] is None:
                    nxt.append(i)
        cur = nxt
        d += 1
    return ud

def main():
    N, u, v = list(map(int, input().split()))
    u, v = u - 1, v - 1
    E = [list() 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)

    ud = depth(u, E)
    vd = depth(v, E)
    m = 0
    for i in range(N):
        udi = ud[i]
        vdi = vd[i]
        if udi >= vdi:
            continue
        steps = udi + (vdi - udi) - 1
        m = max(steps, m)
    print(m)



main()

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

vi = u 
from collections import deque
Q = deque([vi])
checked_list = [False for i in range(N)]
checked_list[vi]=True
min_path_list = [10**27 for i in range(N)] 
min_path_list[vi] = 0
prev_list = [-1 for i in range(N)]
while len(Q)>0:
    v = Q.pop()
    for v1 in e_list[v]:
        if not checked_list[v1]:
            checked_list[v1]=True
            prev_list[v1] = v
            Q.appendleft(v1)
            min_path_list[v1]=min(min_path_list[v1],min_path_list[v]+1) 

dis=min_path_list[w]//2
w_min = min_path_list[w]
current = w
for i in range(dis):
        current = prev_list[current]
dist = min_path_list[current]
vi = current 
Q = deque([vi])
checked_list = [False for i in range(N)]
checked_list[vi]=True
checked_list[prev_list[vi]]=True
min_path_list = [10**27 for i in range(N)] 
min_path_list[vi] = 0
while len(Q)>0:
    v = Q.pop()
    for v1 in e_list[v]:
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.appendleft(v1)
            min_path_list[v1]=min(min_path_list[v1],min_path_list[v]+1) 
depth = 0
for i in range(N):
        if min_path_list[i]<10**27:
                depth = max(min_path_list[i],depth)

depth = dist+depth
print(depth-1)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

n,v,u = map(int, input().split()); u -= 1; v -= 1
g = [list() 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)
dep = [0]*n; mdep = [0]*n; par = [-1]*n

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

def dfs(v,p):
  for x in g[v]:
    if x == p:
      continue
    par[x] = v
    dep[x] = dep[v] + 1
    dfs(x,v)
    if mdep[v] < mdep[x] + 1:
      mdep[v] = mdep[x] + 1
  return
      
dfs(u,-1)
t = (dep[v]-1)//2
curv = v
for _ in range(t):
  curv = par[curv]
curu = par[curv]
if not dep[v]%2:
  curu = par[curu]
print(t + mdep[curv] + 1 - dep[v]%2)

Solution (Python):
N,u,v = map(int,input().split())
u -=1
v -=1
AB = [list(map(int,input().split())) for _ in [0]*(N-1)]

E = [[] for _ in [0]*N]
for a,b in AB:
    E[a-1].append(b-1)
    E[b-1].append(a-1)

def dist_bfs(N,E,start):
    d = [-1]*N
    d[start] = 0
    q = [start]
    while q:
        qq = []
        for i in q:
            di = d[i]
            for j in E[i]:
                if d[j]!=-1:continue
                d[j] = di+1
                q.append(j)
        q = qq
    return d

d = dist_bfs(N,E,v)

dt = d[u] - (d[u]-1)//2

w = u
dw = d[w]
while dw != dt:
    for j in E[w]:
        if d[j] == (dw-1):
            w = j
            break
    dw = d[w]
t = w

ans = d[u]-dt

tmp = 0
q = [t]
while q:
    i = q.pop()
    di = d[i]
    tmp = max(tmp,di-dt)
    for j in E[i]:
        if d[j] >di:
            q.append(j)

ans += tmp
ans += 1-d[u]%2

print(ans)

Solution (Python):
n,u,v = map(int,input().split())
inf = 10 ** 6
u -= 1
v -= 1
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  peer[a].append(b)
  peer[b].append(a)
seen = [0 for _ in range(n)]
rank = [0 for _ in range(n)]
seen[v] = 1
now = [v]
pst = [[] for _ in range(n)]
pre = [inf for _ in range(n)]
while now:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if seen[y] == 0:
        seen[y] = 1
        rank[y] = rank[x] + 1
        pst[x].append(y)
        pre[y] = x
        now.append(y)

r = rank[u]
if r % 2 == 0:
  m = r//2 + 1
  M = u
  for _ in range(r-m):
    M = pre[M]
  now = [M]
  while now != []:
    last = now
    now = []
    for x in last:
      for y in pst[x]:
        now.append(y)
  ans = rank[last[0]] - m + r - m + 1
  
  
else:
  m = r//2 + 1
  M = u
  for _ in range(r-m):
    M = pre[M]
  now = [M]
  while now != []:
    last = now
    now = []
    for x in last:
      for y in pst[x]:
        now.append(y)
  ans = rank[last[0]] - m + r - m
  
  
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

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

u -= 1
v -= 1

def bfs1():
    q = [v]
    d = 0
    D = [-1]*N
    D[v] = 0
    while q:
        qq = []
        d += 1
        for p in q:
            for np in graph[p]:
                if D[np] == -1:
                    D[np] = d
                    qq.append(np)
        q = qq
    return D

D = bfs1()
dis = D[u]
canuse = [True]*N
for i in range(N):
    if D[i] <= dis//2:
        canuse[i] = False

def bfs2():
    q = [u]
    d = 0
    D = [-1]*N
    D[u] = 0
    while q:
        qq = []
        d += 1
        for p in q:
            for np in graph[p]:
                if D[np] == -1 and canuse[np]:
                    D[np] = d
                    qq.append(np)
        q = qq
    return D


D2 = bfs2()
ans = 0
for i in range(N):
    if len(graph[i]) == 1 and D2[i] != -1:
        ans = max(D[i]-1, ans)
print(ans)