Problem:


Score : 600 points

Problem Statement

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

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

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

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

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

3. Go back to step 1.

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

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

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

Constraints

2 \leq N \leq 10^5

1 \leq u,v \leq N

u \neq v

1 \leq A_i,B_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

5 4 1
1 2
2 3
3 4
3 5

Sample Output 1

2

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

Takahashi moves to Vertex 3.

Aoki moves to Vertex 2.

Takahashi moves to Vertex 5.

Aoki moves to Vertex 3.

Takahashi moves to Vertex 3.

Here, Aoki performs two moves.

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

Sample Input 2

5 4 5
1 2
1 3
1 4
1 5

Sample Output 2

1

Sample Input 3

2 1 2
1 2

Sample Output 3

0

Sample Input 4

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

Sample Output 4

5



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


Sample output:
2

Submission status: Accepted

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

n, u, v = map(int, readline().split())
m = map(int,read().split())
data = list(zip(m,m))

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

def dfs(v):
    dist = [None] * (n + 1)
    dist[v] = 0
    stack = deque([v])
    while stack:
        x = stack.popleft()
        for y in graph[x]:
            if dist[y] is None:
                dist[y] = dist[x] + 1
                stack.append(y)
    return dist


res = 0
for i, j in zip(dfs(u), dfs(v)):
    if i is None:
      continue
    if i <= j:
        if j > res:
            res = j
print(res - 1)

Submission status: Accepted

Solution code:
from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
import heapq
#https://atcoder.jp/contests/abc148/tasks/abc148_f
#F - Playing Tag on Tree
"""
"""
N = gi()
U = gi()
V = gi()
t = [[] for i in range(N + 1)]
d = [[-1 for i in range(2)] for j in range(N + 1)]

for _ in range(1, N):
    a = gi()
    b = gi()
    t[a].append(b)
    t[b].append(a)


def bfs(s, di):
    d[s][di] = 0
    q = deque()
    q.append(s)
    while len(q):
        v = q.pop()
        for u in t[v]:
            if d[u][di] >= 0:
                continue
            d[u][di] = d[v][di] + 1
            q.append(u)


bfs(U, 0)
bfs(V, 1)

ans = 0
for l in range(1, N + 1):
    if len(t[l]) > 1:
        continue
    du = d[l][0]
    dv = d[l][1]
    #print(l, du, dv)
    if dv >= du:
        ans = max(ans, dv - 1)

print(ans)

Submission status: Accepted

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

N, u, v = map(int, input().split())
u -= 1
v -= 1
F = [[] for _ in range(N)]
for _ in range(N-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  F[a].append(b)
  F[b].append(a)
a_dist = [-1]*N
t_dist = [-1]*N
a_dist[v] = 0
t_dist[u] = 0
def dfs(p):
  dist = [-1]*N
  stack = [p]
  dist[p] = 0
  while stack:
    q = stack.pop()
    for nq in F[q]:
      if dist[nq] == -1:
        dist[nq] = dist[q]+1
        stack.append(nq)
  return dist
a_dist = dfs(v)
t_dist = dfs(u)
ans = 0
for t, a in zip(t_dist, a_dist):
  if t < a:
    temp = a-1
    if ans < temp:
      ans = temp
    
print(ans)

Submission status: Accepted

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


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

GRAPH = {i:[] for i in range(1, n + 1)}
for _ in range(n - 1):
    a, b = map(int, input().split())
    GRAPH[a].append(b)
    GRAPH[b].append(a)

def dfs(now, prev = 0):
    PARENT[now] = prev
    DEPTH[now] = DEPTH[prev] + 1
    if len(GRAPH[now]) == 1:
        LEAVES.append((DEPTH[now], now))
    
    for w in GRAPH[now]:
        if w == prev:
            continue
        next = w
        dfs(next, now)

PARENT = {}
DEPTH = {0:-1}
LEAVES = []
dfs(v)

PATH = {i:False for i in range(1, n + 1)}
now = u
while True:
    PATH[now] = True
    if now == v:
        break
    now = PARENT[now]

LEAVES.sort(reverse = True)
for leaf in LEAVES:
    now = leaf[1]
    while True:
        if PATH[now]:
            break
        now = PARENT[now]
    lca = now
    
    du, dv = DEPTH[u] - DEPTH[lca], DEPTH[lca]
    if du < dv:
        print(leaf[0] - 1)
        exit()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)

def dfs(array, current, count):
  array[current - 1] = count
  for neighbour in graph[current]:
    if array[neighbour - 1] == -1:
      array = dfs(array, neighbour, count + 1)
  else:
    return array

T = [-1 for x in range(100000)]
A = [-1 for x in range(100000)]

graph = {}

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

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

  try:
    graph[b].append(a)
  except KeyError:
    graph[b] = [a]

T = dfs(T, u, 0)
A = dfs(A, v, 0)

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

Submission status: Accepted

Solution code:
n,u,v = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(n-1)]

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

for a,b in lis:
    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

takahashi = dfs(u)
aoki = dfs(v)

ans = 0

for i in range(1,n+1):
    if takahashi[i] < aoki[i]:
        ans = max(ans,aoki[i]-1)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

def BFS(s):
 dist=[-1 for i in range(n)]
 dist[s]=0

 que=deque()
 que.append(s)

 while que:
  x=que.popleft()
  for p in tree[x]:
   if dist[p]==-1:
    que.append(p)
    dist[p]=dist[x]+1

 return dist

u_dist=BFS(u-1)
v_dist=BFS(v-1)

l=0
for u_d,v_d in zip(u_dist,v_dist):
 if u_d<v_d:
  l=max(l,v_d)

print(l-1)

Submission status: Accepted

Solution code:
def solve(N,u,v,G):
    
    def ikisaki(u):
        U = [0]*(N+1)
        u_que = [[u,0,-1]]
        u_visited = [0]*(N+1)
        u_visited[u] = 1
        while u_que != []:
            now,kaisuu,parent = u_que.pop()
            for to in G[now]:
                if to != parent:
                    U[to] = kaisuu+1
                    if len(G[to])!=1:
                        u_que.append([to,kaisuu+1,now])
        return U
    V = ikisaki(v)
    U = ikisaki(u)
    
    maxV = 0
    for i in range(1,N+1):
        if V[i] > U[i]:
            maxV = max(maxV,V[i])
    print(maxV-1)
    

    

N,u,v = map(int,input().split())
from collections import defaultdict
G = defaultdict(list)
for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)

solve(N,u,v,G)

Submission status: Accepted

Solution code:
import sys
import math
import heapq
from collections import deque
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,u,v=LI()

TR=[[] for i in range(N+1)]
for _ in range(N-1):
    i,j=LI()
    TR[i].append(j)
    TR[j].append(i)

DIST1=[-1]*(N+1)
DIST2=[-1]*(N+1)
FIFO = deque()

FIFO.append((v,0))
while FIFO:
    edge, dist = FIFO.popleft()
    DIST1[edge] = dist
    for i in TR[edge]:
        if DIST1[i] == -1:
            FIFO.append((i, dist+1))

FIFO.append((u, 0))

farest = 0
while FIFO:
    edge, dist = FIFO.popleft()
    DIST2[edge] = dist
    farest = max(farest, DIST1[edge])
    for i in TR[edge]:
        if DIST2[i] == -1 and dist+1 < DIST1[i]:
            FIFO.append((i, dist+1))

# print(DIST1)
# print(DIST2)
print(max(0, farest-1))

Submission status: Accepted

Solution code:
N,u,v = map(int,input().split())
l = []
from collections import defaultdict
from collections import deque
d = defaultdict(list)
for i in range(N-1):
    ta,tb = map(int,input().split())
    d[ta-1].append(tb-1)
    d[tb-1].append(ta-1)

def dfs(x):

    l = deque()
    l.append(x-1)
    dp = [-1] * N
    dp[x-1] = 0
    # print(l)
    while l:
        t = l.pop()
        for i in d[t]:
            # print(i)
            if dp[i] ==-1:
                dp[i] = dp[t]+1
                l.append(i)
        # print(l)
    return dp

distu = dfs(u)
distv = dfs(v)
M = 0
for i , j in zip(distu,distv):
    if i < j:
        M = max(M,j-1)
print(M)

Submission status: Accepted

Solution code:
class tree:
    def __init__(self,n):
        self.edge = [set() for i in range(n)]
    def add_edge_dual(self,f,e):
        self.edge[f].add(e)
        self.edge[e].add(f)
    def add_edge_single(self,f,e):
        self.edge[f].add(e)
    def connected(self,node):
        return self.edge(node)


def dfs(graph,s):
    visited = [False for i in range(len(graph.edge))]
    distance = [-1 for i in range(len(visited))]
    visited[s] = True
    distance[s] = 0
    buf = [[s]]
    now = s
    while len(buf) != 0:
        nexts = buf[0]
        buf = buf[1:]
        temp = []
        for nex in nexts:
            for child in graph.edge[nex]:
                if visited[child] == False:
                    distance[child] = distance[nex]+1
                    temp.append(child)
                    visited[child] = True
                else:
                    continue
        if len(temp) == 0:
            continue
        else:
            buf.append(temp)
    return  distance



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

for i in range(n-1):
    a,b = map(int,input().split())
    t.add_edge_dual(a-1,b-1)

taka = dfs(t,u-1)
aoki = dfs(t,v-1)

aofar = -1
for i in range(n):
    if taka[i] < aoki[i]:
        if aoki[i] > aofar:
            aofar = aoki[i]


print(aofar-1)

# print(sorted(taka,key=lambda x:-x))
# print(sorted(aoki,key=lambda x:-x))
#
# print()
# print(far,aofar)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,u,v = LI()
    ab = [LI() for _ in range(n-1)]
    e = collections.defaultdict(list)
    for a,b in ab:
        e[a].append(b)
        e[b].append(a)

    def search(s, ea):
        d = collections.defaultdict(lambda: inf)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        for u in ea:
            v[u] = True
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv in e[u]:
                if v[uv]:
                    continue
                vd = k + 1
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d

    du = search(u, [])
    dv = search(v, [])
    r = 0
    for i in range(n):
        if du[v] - du[u] < 3:
            break
        r += 1
        for c in e[u]:
            if dv[u] > dv[c]:
                u = c
                break
        for c in e[v]:
            if du[v] > du[c]:
                v = c
                break

    ea = []
    t = dv[u]
    for c in range(1, n+1):
        if dv[c] < t:
            ea.append(c)
    d = search(u, ea)
    m = max(d.values())
    r += m
    s = t - dv[v]
    if s > 1:
        r += 1

    return r


print(main())

Submission status: Accepted

Solution code:
from collections import deque
INFTY = 10**6
N,u,v = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
du = [INFTY for _ in range(N+1)]
du[u] = 0
que = deque([(0,u)])
hist = [0 for _ in range(N+1)]
hist[u] = 1
while que:
    c,i = que.popleft()
    for j in G[i]:
        if hist[j]==0:
            que.append((c+1,j))
            du[j] = c+1
            hist[j] = 1
dv = [INFTY for _ in range(N+1)]
dv[v] = 0
que = deque([(0,v)])
hist = [0 for _ in range(N+1)]
hist[v] = 1
while que:
    c,i = que.popleft()
    for j in G[i]:
        if hist[j]==0:
            que.append((c+1,j))
            dv[j] = c+1
            hist[j] = 1
cmax = 0
for i in range(1,N+1):
    if du[i]<dv[i]:
        cmax = max(cmax,dv[i])
print(cmax-1)

Submission status: Accepted

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

import collections

def bfs(x):
    X = [ -1 ] * (n + 1)
    q = collections.deque([ (x, 0) ])
    X[x] = 0
    while q:
        node, dist = q.popleft()
        for dst in V[node]:
            if X[dst] == -1:
                X[dst] = dist + 1
                q.append((dst, dist + 1))
    return X

T = bfs(u)
A = bfs(v)

ans = 0
for i in range(1, len(T)):
    if T[i] < A[i]:
        ans = max(ans, A[i] - 1)
print(ans)

Submission status: Accepted

Solution code:
N,u,v=map(int,input().split())
G=[set() for i in range(N)]
for i in range(N-1):
  A,B=map(int,input().split())
  G[A-1].add(B-1)
  G[B-1].add(A-1)
disA=[-1]*N
disB=[-1]*N
disA[u-1]=0
disB[v-1]=0
import collections

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

q.append(v-1)      
while(q):
  x=q.popleft()
  for y in G[x]:
    if disB[y]==-1:
      disB[y]=disB[x]+1
      q.append(y)
ans=0
for i in range(N):
  if disA[i]<disB[i]:
    ans=max(ans,disB[i]-1)
print(ans)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 5)

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

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

t = [0] * n
a = [0] * n

def dfs(x, p, d, c):
    if len(e[x]) == 1:
        if e[x][0] == p:
            return
    for y in e[x]:
        if y == p:
            continue
        if c == 0:
            t[y] = d
        else:
            a[y] = d
        dfs(y, x, d+1, c)

dfs(u, -1, 1, 0)
dfs(v, -1, 1, 1)
ans = 0
for i in range(n):
    if t[i] < a[i]:
        ans = max(a[i], ans)

print(ans-1)

Submission status: Accepted

Solution code:
from collections import deque

def BFS(s):
 tree=[[] for i in range(n)]
 for i in list:
  tree[i[0]-1].append(i[1]-1)
  tree[i[1]-1].append(i[0]-1)

 dist=[-1 for i in range(n)]
 dist[s-1]=0

 que=deque()
 que.append(s-1)
 while que:
  x=que.popleft()
  for p in tree[x]:
   if dist[p]==-1:
    que.append(p)
    dist[p]=dist[x]+1
 return dist

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

u_dist=BFS(u)
v_dist=BFS(v)

l=0
for u_d,v_d in zip(u_dist,v_dist):
 if u_d<v_d:
  l=max(l,v_d)

print(l-1)

Submission status: Accepted

Solution code:
from collections import deque

def BFS(s):
    tree=[[] for i in range(n)]
    for i in list:
      tree[i[0]-1].append(i[1]-1)
      tree[i[1]-1].append(i[0]-1)

    dist=[-1 for i in range(n)]
    dist[s-1]=0

    que=deque()
    que.append(s-1)
    while que:
        x=que.popleft()
        for p in tree[x]:
            if dist[p]==-1:
                que.append(p)
                dist[p]=dist[x]+1
    return dist

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

u_dist=BFS(u)
v_dist=BFS(v)

l=0
for u_d,v_d in zip(u_dist,v_dist):
 if u_d<v_d:
  l=max(l,v_d)

print(l-1)

Submission status: Accepted

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

def bfs(s):
    dist = [-1]*N
    dist[s] = 0
    q = deque([s])
    
    while q:
        v = q.popleft()
        
        for nv in adj_list[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+1
                q.append(nv)
                
    return dist

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

for _ in range(N-1):
    Ai, Bi = map(int, input().split())
    adj_list[Ai-1].append(Bi-1)
    adj_list[Bi-1].append(Ai-1)

d1 = bfs(u-1)
d2 = bfs(v-1)
ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
n,u,v=map(int,input().split())
kilist=[[] for i in range(n)]
for i in range(n-1):
        a,b=map(int,input().split())
        kilist[a-1].append((b,1))
        kilist[b-1].append((a,1))    
visitedlist=[-1 for  _ in range(n)]
anslist=[0 for _ in range(n)]
searchedlist=[-1 for _ in range(n)]        
def search(i):
        searchedlist[i-1]=1
        visitedlist[i-1]=1
        flag=0
        for j in kilist[i-1]:
            if visitedlist[j[0]-1]<0:
                visitedlist[j[0]-1]=1
                flag+=1
                anslist[j[0]-1]=anslist[i-1]+j[1]
        else:
            pass
        if flag>0:    
            for k in kilist[i-1]:
                if searchedlist[k[0]-1]==-1:
                    search(k[0])
search(u)
u_list=anslist.copy()
visitedlist=[-1 for  _ in range(n)]
anslist=[0 for _ in range(n)]
searchedlist=[-1 for _ in range(n)]  

q=search(v)
v_list=anslist.copy()

maxi=0
for i in range(n):
    if u_list[i]<=v_list[i]:
        maxi=max(maxi,v_list[i])
print(maxi-1)

Submission status: Accepted

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

# bfs from v
dist_from_v = [-1]*N
dist_from_v[v] = 0
Q = {v}
while Q:
    tmp = set()
    for cur in Q:
        for next in adj[cur]:
            if dist_from_v[next] == -1:
                dist_from_v[next] = dist_from_v[cur]+1
                tmp.add(next)
    Q = tmp

# bfs from u
dist_from_u = [-1]*N
dist_from_u[u] = 0
Q = {u}
while Q:
    tmp = set()
    for cur in Q:
        for next in adj[cur]:
            if dist_from_u[next] == -1:
                if dist_from_u[cur]+1 < dist_from_v[next] or True:
                    dist_from_u[next] = dist_from_u[cur]+1
                    tmp.add(next)
    Q = tmp

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

dst_u = dist_from_u.index(max(dist_from_u))
dist_v_dst = dist_from_v[dst_u]
ans = dist_v_dst-1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
infinity=10**6

import sys
input = sys.stdin.readline
N,u,v = map(int,input().split())
u -= 1
v -= 1

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

ends = []
for i in range(N):
    if len(G[i]) == 1:
        ends.append(i)

#幅優先探索
def BFS (s):
    queue = deque()
    d = [infinity]*N
    
    queue.append(s)
    d[s]= 0
    
    while len(queue)!=0:
      u = queue.popleft()
      for v in G[u]:
      	if d[v] == infinity:
        	d[v] = d[u]+1
        	queue.append(v) 	  


  
    return d

d_nigeru = BFS(u)
d_oni = BFS(v)

ans=0
for u in ends:
    if d_nigeru[u] < d_oni[u]:
        ans = max(ans,d_oni[u]-1)

print(ans)

Submission status: Accepted

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

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

taka = [0] * N
aoki = [0] * N

def dfs(v, pre, cost, i):
    for e in edge[v]:
        if e == pre:
            continue
        cost = dfs(e, v, cost, i+1)
    cost[v] = i
    return cost

taka = dfs(u, -1, [0] * N, 0)
aoki = dfs(v, -1, [0] * N, 0)

m = 0
for i in range(N):
    if taka[i] < aoki[i]:
        m = max(m, aoki[i])

print(m-1)

Submission status: Accepted

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

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

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

# process
def getdis(idx, num, dis):
    dis[idx] = num
    for i in tree[idx] :
        if dis[i] < 0:
            dis = getdis(i, num+1, dis)
    return dis

dis_u = [-1]*n
dis_u = getdis(u-1, 0, dis_u)
dis_v = [-1]*n
dis_v = getdis(v-1, 0, dis_v)

ans = 0
for i in range(n):
    if dis_u[i] <= dis_v[i]:
        ans = max(ans, dis_v[i]-1)

# output
print(ans)

Submission status: Accepted

Solution code:
n,u,v = map(int,input().split())
u,v = u-1,v-1
link = [[] for i in range(n)]
for i in range(n-1):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  link[a].append(b)
  link[b].append(a)
tree = [[] for i in range(n)]
for i in [u,v]:
  stack = [i]
  vi = [0] * n
  tree[i].append(0)
  vi[i] = 1
  while stack:
    cur = stack.pop()
    for j in link[cur]:
      if vi[j] == 0:
        stack.append(j)
        vi[j] = 1
        tree[j].append(tree[cur][-1]+1)
m = 0
c = 0
for i,j in tree:
  if i < j:
    if m < j:
      m = j
      #c = (j-i) % 2
print(m-1)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(300000)


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

    def dfs(idx, cur, dis):
        dis[idx] = cur
        for conn in conns[idx]:
            if dis[conn] < 0:
                dis = dfs(conn, cur + 1, dis)
        return dis

    dis_u = [-1] * N
    dis_u = dfs(u, 0, dis_u)
    dis_v = [-1] * N
    dis_v = dfs(v, 0, dis_v)
    ret = 0
    for i in range(N):
        if dis_u[i] < dis_v[i]:
            ret = max(ret, dis_u[i] + (dis_v[i] - dis_u[i] - 1))
    print(ret)
    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))  # type: int
    u = int(next(tokens))  # type: int
    v = int(next(tokens))  # type: int
    A = [int()] * (N - 1)  # type: "List[int]"
    B = [int()] * (N - 1)  # type: "List[int]"
    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()

Submission status: Accepted

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

import sys
sys.setrecursionlimit(300000)


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

    can = [True] * N
    def find_v(idx, dis, visited):
        visited[idx] = True
        if idx == v:
            can[idx] = False
            return (dis, -1)
        ret = 0
        target = -1
        for conn in conns[idx]:
            if not visited[conn]:
                ret, target = find_v(conn, dis + 1, visited)
                if ret > 0:
                    if dis >= ret / 2:
                        can[idx] = False
                    if dis < ret / 2 and target == -1:
                        target = idx
                    break
        return ret, target
    visited = [False] * N
    uv, node = find_v(u, 0, visited)
    #print(can)
    #print('uv: ', uv)
    #print('node: ', node)
    #print(' ---- ' )
    def dfs(idx, dis, visited):
        visited[idx] = True
        ret = dis
        for conn in conns[idx]:
            if not visited[conn] and can[conn]:
                tmp = dfs(conn, dis + 1, visited)
                ret = max(ret, tmp)
        return ret
    visited = [False] * N
    ret = dfs(node, 0, visited)
    #print('ret:', ret)
    ret += uv // 2
    print(ret)
    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))  # type: int
    u = int(next(tokens))  # type: int
    v = int(next(tokens))  # type: int
    A = [int()] * (N - 1)  # type: "List[int]"
    B = [int()] * (N - 1)  # type: "List[int]"
    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()

Submission status: Accepted

Solution code:
import sys,heapq
input = sys.stdin.readline
def main():
    n,u,v = map(int,input().split())
    u,v = u-1,v-1

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

    for _ in [0]*(n-1):
        a,b = map(int,input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)

    #cost:vからの距離
    cost = [0]*n
    new = [v]
    c = 1
    while len(new):
        tank = []
        for e in new:
            for go in edge[e]:
                if go != v and cost[go] == 0:
                    cost[go] = c
                    tank.append(go)
        c += 1
        new = tank

    if cost[u]%2 == 1:
        res = cost[u]//2
        now = u
        for _ in [0]*res:
            for e in edge[now]:
                if cost[now] > cost[e]:
                    now = e
        
        new = [now]
        while len(new):
            tank = []
            for e in new:
                for go in edge[e]:
                    if cost[go] > cost[e]:
                        tank.append(go)
            res += 1
            new = tank
        
        print(res-1)

    else:
        res = cost[u]//2-1
        now = u
        for _ in [0]*res:
            for e in edge[now]:
                if cost[now] > cost[e]:
                    now = e
        
        new = [now]
        while len(new):
            tank = []
            for e in new:
                for go in edge[e]:
                    if cost[go] > cost[e]:
                        tank.append(go)
            res += 1
            new = tank
        
        print(res)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque 
import sys
input = sys.stdin.readline  #文字列入力では注意！

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

def bfs(start):
    q = deque()
    q.append([start,0])
    visited = set()
    lis = [0]*N
    while q:
        now,dis = q.popleft()
        if now in visited:
            continue
        lis[now] = dis
        visited.add(now)
        for node in tree[now]:
            q.append([node,dis+1])    
    return lis
ut = bfs(u)
vt = bfs(v)

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

Submission status: Accepted

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

import queue

dist_t = [0] * n
dist_a = [0] * n

elb_t = [0] * n
elb_a = [0] * n

ab = [[] for j in range(n)]

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

u -= 1
v -= 1

q = queue.Queue()

q.put(u)
elb_t[u] = 1
dist_t[u] = 0

while not q.empty():
    tmp = q.get()
    for i in range(len(ab[tmp])):
        idx = ab[tmp][i]
        if elb_t[idx] != 1:
            if dist_t[idx] != 0:
                dist_t[idx] = min(dist_t[idx], dist_t[tmp] + 1)
            else:
                dist_t[idx] = dist_t[tmp] + 1
            elb_t[idx] = 1
            q.put(idx)

q = queue.Queue()

q.put(v)
elb_a[v] = 1
dist_a[v] = 0

while not q.empty():
    tmp = q.get()
    for i in range(len(ab[tmp])):
        idx = ab[tmp][i]
        if elb_a[idx] != 1:
            dist_a[idx] = dist_a[tmp] + 1
            elb_a[idx] = 1
            q.put(idx)

ans = 0

for i in range(n):
    if dist_a[i] > dist_t[i]:
        ans = max(ans,dist_a[i]-1)

print(ans)

Submission status: Accepted

Solution code:
def solve():
    from collections import deque
    from sys import stdin
    f_i = stdin
    
    N, u, v = map(int, f_i.readline().split())
    u -= 1
    v -= 1
    adj = [[] for i in range(N)]
    for i in range(N - 1):
        A, B = map(int, f_i.readline().split())
        A -= 1
        B -= 1
        adj[A].append(B)
        adj[B].append(A)
    
    INF = 10 ** 5
    tak_dist = [INF] * N
    tak_dist[u] = 0
    aoki_dist = [INF] * N
    aoki_dist[v] = 0
    
    # BFS takahashi
    q = deque([(u, 0)])
    while q:
        pos, dist = q.popleft()
        dist += 1
        for next_pos in adj[pos]:
            if tak_dist[next_pos] > dist:
                tak_dist[next_pos] = dist
                q.append((next_pos, dist))
    
    # BFS aoki
    q = deque([(v, 0)])
    while q:
        pos, dist = q.popleft()
        dist += 1
        for next_pos in adj[pos]:
            if aoki_dist[next_pos] > dist:
                aoki_dist[next_pos] = dist
                q.append((next_pos, dist))
    
    d = (d2 for d1, d2 in zip(tak_dist, aoki_dist) if d1 < d2)
    print(max(d) - 1)

solve()