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):
import sys
input = sys.stdin.readline
N,U,V = map(int, input().split())
d = [set() for _ in range(N+1)]
dps = [0 for _ in range(N+1)]
dpss = [0 for _ in range(N+1)]

def it(v):
    stack = [v]
    vs = set()
    path = []
    while True:
        if not len(stack):
            break
        v = stack.pop()
        if v > 0:
            path.append(v)
            vs.add(v)
            for u in d[v]:
                if u in vs:
                    continue
                if u == V:
                    r = path[:]
                dps[u] = dps[v] + 1
                stack.append(-v)
                stack.append(u)
        else:
            path.pop()
    return r

def it2(v, path):
    stack = [v]
    vs = set()
    while True:
        if not len(stack):
            break
        v = stack.pop()
        vs.add(v)
        for u in d[v]:
            if u in vs:
                continue
            if dps[v] >= dpss[v] and u not in path:
                continue
            dpss[u] = dpss[v] + 1
            stack.append(u)

for _ in range(N-1):
    a, b = [int(x) for x in input().split()]
    d[a].add(b)
    d[b].add(a)

path = set(it(U))
it2(V, path)
print(max(dpss)-1)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

def dfs(node, count,li):
    global node_par
    li[node] = count
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            node_par[i] = node
            dfs(i, count + 1,li)
        
node_par = [0 for i in range(n+1)]

finished = set()
dfs(u,0,takahashi)


finished = set()
dfs(v,0,aoki)


par = u
start = u
while takahashi[par] < aoki[par]:
    start = par
    par = node_par[start]

ans_height = [0 for i in range(n+1)]
finished = set([node_par[start]])
dfs(start,0,ans_height)
print(max(ans_height) + aoki[start] - 1)

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

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

def dfs(node, count,li):
    li[node] = count
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i, count + 1,li)
def dfs_par(node, count,li):
    global node_par
    li[node] = count
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            node_par[i] = node
            dfs_par(i, count + 1,li)
        
node_par = [0 for i in range(n+1)]

finished = set()
dfs(u,0,takahashi)


finished = set()
dfs_par(v,0,aoki)


par = u
start = u
while takahashi[par] < aoki[par]:
    start = par
    par = node_par[start]

ans_height = [0 for i in range(n+1)]
finished = set([node_par[start]])
dfs(start,0,ans_height)
print(max(ans_height) + aoki[start] - 1)

Solution (Python):
import sys
from collections import defaultdict as dd
import heapq
input = sys.stdin.readline
N, u, v = map(int, input().split())
e = dd(list)
for _ in range(N - 1):
  a, b = map(int, input().split())
  e[a].append((b, 1))
  e[b].append((a, 1))
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 6)
      v0 = v // (10 ** 6)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 6) + p[0])
    return d
d = dijkstra(N, e)
p = d.path(v, 0)
pp = d.path(u, 0)


res = 0
for i in range(1, N + 1):
  if p[i] > pp[i]: res = max(p[i], res)
print(res - 1)

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

def bfs(s):
  dist = [-1]*N
  que = deque([s-1])
  dist[s-1] = 0
  while que:
    v = que.popleft()
    d = dist[v]
    for w in edge[v]:
      if dist[w]>-1: continue
      dist[w] = d+1
      que.append(w)
  return dist

ud,vd = bfs(u),bfs(v)
ans = 0
for ud_i,vd_i in zip(ud,vd): ans = max(ans, vd_i-1) if ud_i<vd_i else ans
print(ans)

Solution (Python):
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)

isLeaf, dU, dV = [len(g) == 1 for g in G], [-1] * N, [-1] * N

for D, P in [(dU, u - 1), (dV, v - 1)]:
    S = [(P, 0)]
    while len(S) > 0:
        p, d = S.pop()
        D[p] = d
        for g in G[p]:
            if D[g] == -1:
                S.append((g, d + 1))

ans = 0
for i in range(N):
    if isLeaf[i] and dU[i] < dV[i]:
        ans = max(ans, dV[i] - 1)

print(ans)

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

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

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

from collections import deque
def dfs(g, s, d_list):
  stack = deque()
  stack.append(s)
  d_list[s] = 0
  while stack:
    x = stack.pop()
    for new_x in g[x]:
      if d_list[new_x] == -1:
        stack.append(new_x)
        d_list[new_x] = d_list[x]+1
  return d_list

dt = dfs(g, u, dt)
da = dfs(g, v, da)

d = 0
for i in range(n):
  if dt[i] < da[i]:
    d = max(d, da[i])
    
print(d-1)

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

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

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

from collections import deque
def dfs(g, s, d_list):
  stack = deque()
  stack.append(s)
  d_list[s] = 0
  while stack:
    x = stack.pop()
    for new_x in g[x]:
      if d_list[new_x] == -1:
        stack.append(new_x)
        d_list[new_x] = d_list[x]+1
  return d_list

dt = dfs(g, u, dt)
da = dfs(g, v, da)

d = 0
for i in range(n):
  if dt[i] < da[i]:
    d = max(d, da[i])
    
print(d-1)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
N, u, v = map(int, input().split())
G = {k: [] for k in range(N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    
    G[a].append(b)
    G[b].append(a)


def dfs(ci, d, p, dist):
    dist[ci] = d
    for ni in G[ci]:
        if ni == p:
            continue
        dfs(ni, d+1, ci, dist)


def calcDist(start):
    dist = [-1]*(N+1)
    dfs(start, 0, -1, dist)
    return dist


distU = calcDist(u)
distV = calcDist(v)

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

Solution (Python):
from collections import deque

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

ab_list = [
  tuple(map(int, input().split())) for _ in range(N - 1)
]

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


for a, b in ab_list:
  graph[a].append(b)
  graph[b].append(a)
  
def dfs(v):
  dist = [-1] * (N+1)
  stack = [v]
  dist[v] = 0
  while stack:
    v = stack.pop()
    dw = dist[v] + 1
    for w in graph[v]:
      if dist[w] >= 0:
        continue
      dist[w] = dw
      stack.append(w)
  return dist


DU = dfs(u)
DV = dfs(v)

answer = 0
for u, v in zip(DU[1:], DV[1:]):
  if u < v:
    
    x = v - 1
    answer = max(answer, x)

print(answer)

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


import heapq
def dijkstra(s, E):
    inf = float("inf")
    d = [inf for i in range(len(E))]
    d[s] = 0
    q = [(0, s)]
    while q:
        c, p = heapq.heappop(q)
        if d[p] < c:
            continue
        for cost, to in E[p]:
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q, (d[to], to))
    return d


def main():
    N, u, v = map(int, input().split())
    E = [[] for i in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        E[a-1].append((1, b-1))
        E[b-1].append((1, a-1))
    du = dijkstra(u-1, E)
    dv = dijkstra(v-1, E)
    ans = 0
    for i, j in zip(du, dv):
        if i < j:
            ans = max(ans, j)
    print(ans - 1)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline
N, u, v = [int(x) for x in input().strip().split()]

m = [[] for n in range(N)]
f_aokikun = [False for n in range(N)]
f_takahashikun = [False for n in range(N)]
aokikun = [0 for n in range(N)]
takahashikun = [0 for n in range(N)]
takahashikun_enable = [1 for n in range(N)]
for n in range(N-1):
    a, b = [int(x) for x in input().strip().split()]
    m[a-1].append(b)
    m[b-1].append(a)

def aokifunc(c, f, p, cost):
    c[p-1] = cost
    f[p-1] = True
    for p_next in m[p-1]:
        if f[p_next-1]:
            continue
        aokifunc(c, f, p_next, cost+1)

def takahashifunc(c, f, p, cost, aokikun, takahashikun_enable):
    if aokikun[p-1] <= cost:
        takahashikun_enable[p-1] = 0
    c[p-1] = 0
    f[p-1] = True
    for p_next in m[p-1]:
        if f[p_next-1]:
            continue
        takahashifunc(c, f, p_next, cost+1, aokikun, takahashikun_enable)

aokifunc(aokikun, f_aokikun, v, 0)
takahashifunc(takahashikun, f_takahashikun, u, 0, aokikun, takahashikun_enable)
print(max([i * j for i, j in zip(aokikun, takahashikun_enable)])-1)

Solution (Python):
n,u,v=[int(j) for j in input().split()]
u,v=u-1,v-1
l=[[] for i in range(n)]
for i in range(n-1):
    a,b=[int(j)-1 for j in input().split()]
    l[a].append(b)
    l[b].append(a)
k=[10**18 for i in range(n)]
from collections import deque
q=deque([u])
k[u]=0
s=set()
while q:
    p=q.popleft()
    s.add(p)
    for i in l[p]:
        if i not in s:
            q.append(i)
            k[i]=k[p]+1

k2=[10**18 for i in range(n)]
from collections import deque
q=deque([v])
k2[v]=0
s=set()
while q:
    p=q.popleft()
    s.add(p)
    for i in l[p]:
        if i not in s:
            q.append(i)
            k2[i]=k2[p]+1
ans=0
for i in range(n):
    if k[i]<=k2[i]:
        if ans<k2[i]:
            ans=k2[i]

print(ans-1)

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

"""
高橋くんの戦略
最も遠くに行けるなら言って往復
そのためには、遠くに行くときのポイントに青木より早く到達しなければいけない
青木くん -> 最も遠くに向かって進んでいく
"""

from collections import deque

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



used_a = [-1] * N
used_a[V-1] = 0 
q = deque([V-1])
while len(q) > 0:
    a = q.popleft()
    Vs = G[a]
    for u in Vs:
        if used_a[u] == -1:
            q.append(u)
            used_a[u] = used_a[a] + 1


used_t = [-1] * N
used_t[U-1] = 0 
q = deque([U-1])
while len(q) > 0:
    a = q.popleft()
    Vs = G[a]
    for u in Vs: 
        if used_t[u] == -1:
            q.append(u)
            used_t[u] = used_t[a] + 1

ans = 0


for a,t in zip(used_a,used_t):
    if a > t: 
        ans = max(ans,a-1)
print(ans)

Solution (Python):
import sys,collections,math,random;sys.setrecursionlimit(10**7)
from fractions import gcd
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

n,u,v = Is()
tree = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = Is()
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

md_u, md_v = [-1]*n, [-1]*n
qs = [[u-1,0]], [[v-1,0]]
for md,q in zip([md_u,md_v],qs):
    while q:
        n,d = q.pop()
        md[n] = d
        for e in tree[n]:
            if md[e] == -1:
                q.append([e,d+1])

ans = -2
for a,b in zip(md_u,md_v):
    if a < b:
        ans = max(b,ans)
print(ans-1)

Solution (Python):
from collections import deque

def main():
    N, u, v, *AB = map(int, open(0).read().split())

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

    def solve(s):
        D = [-1] * (N + 1)
        D[s] = 0

        Q = deque([s])
        while Q:
            a = Q.popleft()
            for b in E[a]:
                if D[b] != -1:
                    continue
                D[b] = D[a] + 1
                Q.append(b)

        return D[1:]

    T = solve(u)
    A = solve(v)

    print(-1 + max(a for t, a in zip(T, A) if t < a))

main()

Solution (Python):
from collections import deque

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

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

dist_from_u = [-1] * N
dist_from_u[u] = 0
dist_from_v = [-1] * N
dist_from_v[v] = 0

parent = deque([u])
while parent:
  p = parent.popleft()
  children = neighbors[p]
  for child in children:
    if dist_from_u[child] == -1:
      dist_from_u[child] = dist_from_u[p] + 1
      parent.append(child)

parent = deque([v])
while parent:
  p = parent.popleft()
  children = neighbors[p]
  for child in children:
    if dist_from_v[child] == -1:
      dist_from_v[child] = dist_from_v[p] + 1
      parent.append(child)

max_dist = 0
for du, dv in zip(dist_from_u, dist_from_v):
  if du < dv:
    max_dist = max(max_dist, dv)

print(max_dist - 1)

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

graph = [[] for i in range(N+1)]
for i,j in AB:
    graph[i].append(j)
    graph[j].append(i)
    
r = [-1 for i in range(N+1)] 
Q = deque()
Q.append(u)
r[u] = 0

while Q:
    x = Q.pop()
    for to in graph[x]:
        if r[to] == -1:
            r[to] = r[x] + 1
            Q.append(to)
            
c = [-1 for i in range(N+1)]  
Q=deque()
Q.append(v)
c[v] = 0

while Q:
    x = Q.pop()
    for to in graph[x]:
        if c[to] == -1:
            c[to] = c[x] + 1
            Q.append(to)
ans = 0            
for i in range(N+1):
    if r[i] < c[i]:
        ans = max(ans, c[i])

print(max(0, ans-1))

Solution (Python):
from collections import deque

N, u, v, *AB = map(int, open(0).read().split())

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

def solve(s):
    D = [-1] * (N + 1)
    D[s] = 0

    Q = deque([s])
    while Q:
        a = Q.popleft()
        for b in E[a]:
            if D[b] != -1:
                continue
            D[b] = D[a] + 1
            Q.append(b)

    return D[1:]

T = solve(u)
A = solve(v)

print(-1 + max(a for t, a in zip(T, A) if t < a))

Solution (Python):

import sys
from collections import deque

def solve(N: int, u: int, v: int, A: "List[int]", B: "List[int]"):
    matrix = [[] for _ in range(N+1)]
    for i in range(N-1):
        matrix[A[i]].append(B[i])
        matrix[B[i]].append(A[i])

    takahashi_dist = [-1]*(N+1)
    aoki_dist = [-1]*(N+1)

    queue_takahashi = deque([(u,0)])

    while queue_takahashi:
        node,dist = queue_takahashi.popleft()
        takahashi_dist[node] = dist

        for nd in matrix[node]:
            if takahashi_dist[nd] == -1:
                queue_takahashi.append((nd,dist+1))
    

    queue_aoki = deque([(v,0)])
    while queue_aoki:
        node,dist = queue_aoki.popleft()
        aoki_dist[node] = dist

        for nd in matrix[node]:
            if aoki_dist[nd] == -1:
                queue_aoki.append((nd,dist+1))

    answer = 0
    for j in range(1,N+1):
        if aoki_dist[j] > takahashi_dist[j]:
            answer = max(answer,aoki_dist[j]-1)
    print(answer)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    u = int(next(tokens))  
    v = int(next(tokens))  
    A = [int()] * (N - 1)  
    B = [int()] * (N - 1)  
    for i in range(N - 1):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, u, v, A, B)

if __name__ == '__main__':
    main()

Solution (Python):
def f_playing_tag_on_tree():
    from collections import deque

    def bfs(tree, distance, first_pos):
        q = deque([(first_pos, -1)])
        while q:
            current, parent = q.pop()
            for child in tree[current]:
                if child == parent:
                    continue
                distance[child] = distance[current] + 1
                q.appendleft((child, current))

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

    
    dist_aoki = [0] * N
    bfs(tree, dist_aoki, V - 1)
    dist_takahashi = [0] * N
    bfs(tree, dist_takahashi, U - 1)

    ans = 0
    for aoki, takahashi in zip(dist_aoki, dist_takahashi):
        
        if aoki > takahashi:
            
            
            ans = max(ans, aoki - 1)
    return ans

print(f_playing_tag_on_tree())

Solution (Python):
from collections import deque

N, T, A, *AB = map(int, open(0).read().split())

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

takahashi = [-1] * (N + 1)
takahashi[T] = 0
Q = deque([T])
while Q:
    a = Q.popleft()
    for b in E[a]:
        if takahashi[b] != -1:
            continue
        takahashi[b] = takahashi[a] + 1
        Q.append(b)

aoki = [-1] * (N + 1)
aoki[A] = 0
Q = deque([A])
while Q:
    a = Q.popleft()
    for b in E[a]:
        if aoki[b] != -1:
            continue
        aoki[b] = aoki[a] + 1
        Q.append(b)

ma = 0
for t, a in zip(takahashi[1:], aoki[1:]):
    if t < a:
        ma = max(ma, a)

print(ma - 1)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
import numpy as np

n, u, v = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n-1)]

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


def dfs(graph, start):
    stack = deque([start])
    dist = [-1]*n
    dist[start] = 0
    while stack:
        node = stack.pop()
        dist_x = dist[node] + 1
        for child in graph[node]:
            if dist[child] != -1:
                continue
            dist[child] = dist_x
            stack.append(child)
    return dist

distance1 = np.array(dfs(graph, u-1))
distance2 = np.array(dfs(graph, v-1))

distance = distance2[distance1<distance2]
ans = max(distance)-1
print(ans)

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


N, V, U = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]

V -= 1
U -= 1
graph = [[] for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)



children_depths = [-1 for _ in range(N)]
parents = [None for _ in range(N)]


def dfs(v, parent):
    ret = 0
    for u in graph[v]:
        if u == parent:
            continue
        ret = max(ret, dfs(u, v) + 1)
    children_depths[v] = ret
    parents[v] = parent
    return ret


dfs(U, None)

v = V
dist = 1
while parents[v] != U:
    v = parents[v]
    dist += 1


p_cnt = 0
v = V
ans = 0
while dist > 0:
    ans = max(ans, dist - 1 + children_depths[v] + p_cnt)
    v = parents[v]
    p_cnt += 1
    dist -= 2
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    def dfs(start):
        stack=[start]
        used=[False]*N
        d=[-1]*N
        d[start]=0
        while stack:
            node=stack.pop()
            used[node]=True
            for x in cns[node]:
                if not used[x]:
                    d[x]=d[node]+1
                    stack.append(x)
        return d
    
    N,u,v=map(int,input().split())
    u-=1
    v-=1
    A,B=[0]*(N-1),[0]*(N-1)
    cns=[[] for _ in range(N)]
    for i in range(N-1):
        A[i],B[i]=map(lambda x: int(x)-1,input().split())
        cns[A[i]].append(B[i])
        cns[B[i]].append(A[i])

    u_l = dfs(u)
    v_l = dfs(v)
    ans=0
    for U,V in zip(u_l,v_l):
        if V > U:
            ans=max(ans,V-1)
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

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

def dfs(dist, v, d=0, p=-1):
    dist[v] = d
    for u in to[v]:
        if u == p:
            continue
        dfs(dist, u, d+1, v)

def calcDist(s):
    dist = [0] * N
    dfs(dist, s)
    return dist

distS = calcDist(s)
distT = calcDist(t)

mx = 0
for i in range(N):
    if distS[i] < distT[i]:
        mx = max(mx, distT[i])
ans = mx - 1
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(700000)

from collections import deque

N, u, v = map(int, input().split())
tree = deque([deque() for i in range(N+1)])

def dfs(s, dist, d=0, p=-1):
    dist[s] = d
    for tmp in tree[s]:
        if tmp != p:
            dfs(tmp, dist, d+1, s)

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

distT, distA = [0]*N, [0]*N

dfs(u-1, distT)
dfs(v-1, distA)

ans = 0
for i in range(N):
    if distT[i] < distA[i]:
        ans = max(ans, distA[i])
print(ans-1)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, x, y = MAP()
x -= 1; y -= 1
nodes = [[] for i in range(N)]
for i in range(N-1):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    nodes[b].append(a)

def dfs(x):
    dist  = [INF] * N
    stack = [(x, 0, -1)]
    while stack:
        u, cost, prev = stack.pop()
        if dist[u] != INF:
            continue
        dist[u] = cost
        for v in nodes[u]:
            if v == prev:
                continue
            stack.append((v, cost+1, u))
    return dist


res1 = dfs(x)
res2 = dfs(y)

mx = -INF
for i in range(N):
    
    if res1[i] <= res2[i]:
        
        mx = max(mx, res2[i])

print(mx - 1)

Solution (Python):


import heapq
class Dijkstra():
    """
    ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
    ・負のコストがない場合のみ
    ・計算量はO(E log|V|)　
    ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
    """
    
    
    
    
    class Edge():
        
        
        def __init__(self, _to, _cost):
            self.to =_to
            self.cost = _cost
    
    def __init__(self, V):
        
        self.G = [[] for _ in range(V)] 
        self. _E = 0 
        self._V = V 
    
    
    def E(self):
        return self._E
    
    
    def V(self):
        return self._V
    
    def add(self, _from, _to, _cost):
        
        self.G[_from].append(self.Edge(_to,_cost))
        self._E +=1
        
    def add2(self, _from, _to, _cost):
        
        self.G[_from].append(self.Edge(_to, _cost))
        self.G[_to].append(self.Edge(_from, _cost))
        self._E +=1
        
    def shortest_path(self,s):
        
        
        que = [] 
        d = [float("inf")] * self.V()
        prev = [None]*self.V() 
        d[s] = 0
        heapq.heappush(que,(0,s)) 
        
        while len(que)!=0:
            
            cost,v = heapq.heappop(que)
            
            
            if d[v] < cost:
                continue
                
            
            for i in range(len(self.G[v])):
                e = self.G[v][i] 
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost 
                    prev[e.to] = v
                    heapq.heappush(que,(d[e.to],e.to)) 
                    
        return d



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


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



d_v=djk.shortest_path(v-1)
d_u=djk.shortest_path(u-1)


path_to_leaf_v=[]

for i in range(N):
    if len(list[i])==1:
        if d_v[i] >= d_u[i]:
            path_to_leaf_v.append(d_v[i])



ans = max(path_to_leaf_v)-1
print(ans)

Solution (Python):
from collections import deque

def solve(tree, distance, w):
    dq = deque()
    dq.appendleft((w, -1))
    while dq:
        x, prev = dq.pop()
        for a in tree[x]:
            if a == prev:
                continue
            distance[a] = distance[x] + 1
            dq.appendleft((a, x))

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

    aoki = [0] * N
    solve(tree, aoki, v - 1)
    takahashi = [0] * N
    solve(tree, takahashi, u - 1)

    ans = 1
    for a, t in zip(aoki, takahashi):
        if a > t:
            ans = max(ans, a)
    print(ans - 1)

main()

Solution (Python):
import sys

read = sys.stdin.read
N, u, v, *AB = map(int, read().split())

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


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


DU, DV = dfs(u), dfs(v)

answer = 0
for u, v in zip(DU[1:], DV[1:]):
    if u < v:
        tmp = v - 1
        if answer < tmp:
            answer = tmp

print(answer)

Solution (Python):
from collections import deque

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

depthu = [-1] * N
depthu[u] = 0
depthv = [-1] * N
depthv[v] = 0

par = deque([u])
while par:
    p = par.popleft()
    for q in table[p]:
        if depthu[q] == -1:
            depthu[q] = depthu[p] + 1
            par.append(q)

par = deque([v])
while par:
    p = par.popleft()
    for q in table[p]:
        if depthv[q] == -1:
            depthv[q] = depthv[p] + 1
            par.append(q)

p = [i for i in range(N) if depthu[i] < depthv[i]]
if p:
    print(max(depthv[i] - 1 for i in p))
else:
    print(depthu[v] - 1)

Solution (Python):
from collections import deque

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

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

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


memov = [-1] * n
q = deque()
memov[v] = 0
q.append((v, 0))

while q:
    v_, d = q.popleft()
    for nv in g[v_]:
        if memov[nv] != -1:
            continue
        memov[nv] = d + 1
        q.append((nv, d+1))

memou = [-1] * n
q = deque()
memou[u] = 0
q.append((u, 0))

while q:
    v_, d = q.popleft()
    for nv in g[v_]:
        if memou[nv] != -1:
            continue
        if d + 1 >= memov[nv]:
            continue
        memou[nv] = d + 1
        q.append((nv, d+1))

max_v = -1
max_d = 0
for i in range(n):
    if memou[i] == -1:
        continue
    if memov[i] >= max_d:
        max_v = i
        max_d = memov[i]

print(max_d - 1)

Solution (Python):
from collections import defaultdict


n, taks, aoks = map(int, input().split())
taks -= 1
aoks -= 1

edges = defaultdict(list)

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

aoki_map = [None] * n
taka_map = [None] * n


def dfs(start, edges, path):
    path[start] = 0
    todo = []
    for to in edges[start]:
        todo.append([to, 1])
        path[to] = 1

    while todo:
        node, dist = todo.pop()
        if path[node] < dist:
            continue

        for to in edges[node]:
            if path[to] is None or path[to] > dist+1:
                todo.append([to, dist+1])
                path[to] = dist+1


dfs(aoks, edges, aoki_map)


ans = [-1] * n
ans[taks] = aoki_map[taks]
taka_map[taks] = 0

todo = []
for to in edges[taks]:
    todo.append([to, 1])
    ans[to] = aoki_map[to]
    taka_map[to] = 1


while todo:
    node, dist = todo.pop()
    if taka_map[node] < dist:
        continue

    for to in edges[node]:
        if taka_map[to] is None or taka_map[to] > dist + 1:
            if aoki_map[to] > dist + 1:
                todo.append([to, dist + 1])
                taka_map[to] = dist + 1
                ans[to] = aoki_map[to]
            else:
                ans[to] = aoki_map[to]

res = max(ans)

print(res-1)