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:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 5 + 1)


def dfsu(s, p):
    for t in g[s]:
        if t == p:
            continue
        du[t] = du[s] + 1
        dfsu(t, s)


def dfsv(s, p):
    for t in g[s]:
        if t == p:
            continue
        dv[t] = dv[s] + 1
        dfsv(t, s)


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

du = [0] * n
dv = [0] * n
dfsu(u, -1)
dfsv(v, -1)

mx = 0
for i in range(n):
    if du[i] < dv[i]:
        mx = max(mx, dv[i])
print(mx - 1)

Submission status: Accepted

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

n,g,s = map(int,input().split())
G = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  
def dfs(V,v,d):
  if V[v] != -1:
    return
  V[v] = d
  for nv in G[v]:
    dfs(V,nv,d+1)
  
if len(G[g-1])==1 and G[g-1][0]==s-1:
  print(0)
else:
  vs = [-1]*n
  vg = [-1]*n
  dfs(vs,s-1,0)
  dfs(vg,g-1,0)
  
  ans = 0
  for i in range(n):
    if vs[i]>vg[i]:
      ans = max(ans,vs[i])
      
  print(ans-1)

Submission status: Accepted

Solution code:
n,u,v=map(int,input().split())
u-=1
v-=1
ki=[[]for _ in range(n)]
for _ in range(n-1):
  a,b=map(lambda x:int(x)-1,input().split())
  ki[a].append(b)
  ki[b].append(a)
du=[0]*n
dv=[0]*n
from collections import deque
def distance(i):
  seen=[-1]*n
  seen[i]=0
  todo=deque([i])
  while todo:
    t=todo.popleft()
    l=ki[t]
    d=seen[t]
    for li in l:
      if seen[li]==-1:
        seen[li]=d+1
        todo.append(li)
  return seen
du=distance(u)
dv=distance(v)
ans=0
for i in range(n):
  if dv[i]>du[i]:
    ans=max(ans,dv[i])
print(ans-1)

Submission status: Accepted

Solution code:
import sys
import  math
import fractions
from collections import deque
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,u,v=nm()
u=u-1
v=v-1
INF=10**18
edge=[[] for i in range(N)]

def bfs(start,edge):
    d=[INF]*N
    d[start]=0
    q=deque([start])
    while (q):
        e=q.popleft()
        for i in edge[e]:
            if(d[e]+1<d[i]):
                d[i]=d[e]+1
                q.append(i)   
    return d


for i in range(N-1):
    A,B=nm()
    edge[B-1].append(A-1)
    edge[A-1].append(B-1)


d_A=bfs(u,edge)
d_B=bfs(v,edge)

ans=0
for i in range(N):
    #if(d_A[0]%2==d_B[0]%2):
    #    continue
    #else:
    if(d_A[i]<d_B[i]):
        tmp=max(d_A[i],d_B[i])
        ans=max(ans,tmp)

print(ans-1)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**5)
n, u, v = map(int, input().split())
u -= 1
v -= 1
m_mat = [[] for i in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    m_mat[a].append(b)
    m_mat[b].append(a)
u_map = [-1]*n
v_map = [-1]*n
u_map[u] = 0
v_map[v] = 0


def dfs(current, depth, ma):
    for nex in m_mat[current]:
        if ma[nex] > -1:
            continue
        ma[nex] = depth
        dfs(nex, depth+1, ma)


dfs(u, 1, u_map)
dfs(v, 1, v_map)

ans = -1
for i in range(n):
    if u_map[i] < v_map[i] and v_map[i] > ans:
        ans = v_map[i]

print(ans-1)

Submission status: Accepted

Solution code:
from collections import deque
n,u,v=map(int,input().split())
g=[set([]) for _ in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a].add(b)
    g[b].add(a)

leaf=[]
for i in range(1,n+1):
    if(len(g[i])==1):
        leaf.append(i)

d_u=[-1 for _ in range(n+1)]
d_v=[-1 for _ in range(n+1)]

def bfs(start,d):
    d[start]=0
    q=deque([start])

    while(len(q)>0):
        qi=q.popleft()
        di=d[qi]

        next_qi=g[qi]
        for i in next_qi:
            if(d[i]==-1):
                d[i]=di+1
                q.append(i)

    return d


d_u=bfs(u, d_u)
d_v=bfs(v, d_v)


if(u in leaf and list(g[u])[0]==v):
    print(0)
else:
    ans=0
    for li in leaf:
        if(d_u[li]<d_v[li]):
            ans=max(ans,d_v[li]-1)
    print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**6
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,u,v = LI()
    root = [[] for _ in range(N)]
    for _ in range(N-1):
        a,b = LI()
        root[a-1].append(b-1)
        root[b-1].append(a-1)
    T = [INF for _ in range(N)]
    A = [INF for _ in range(N)]

    def calc_d(m,x):
        q = collections.deque()
        q.append((x,0))
        while q:
            a,d = q.popleft()
            m[a] = d
            for b in root[a]:
                if m[b] > d+1:
                    q.append((b,d+1))

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
N,U,V = map(int,input().split())
U,V = U-1,V-1
AB = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for _ in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

prev = [-1] * N
def dfs(v,p=-1):
    for to in es[v]:
        if to==p: continue
        prev[to] = v
        dfs(to,v)
dfs(U)

path = [V]
while prev[path[-1]] >= 0:
    path.append(prev[path[-1]])
ban = set(path[:(len(path)+1)//2])

reach = [0] * N
reach[U] = 1
def dfs2(v,p=-1):
    for to in es[v]:
        if to==p: continue
        if to in ban: continue
        reach[to] = 1
        dfs2(to,v)
dfs2(U)

depth = [0] * N
ans = 0
def dfs3(v,p=-1):
    global ans
    for to in es[v]:
        if to==p: continue
        depth[to] = depth[v] + 1
        if reach[to]:
            ans = max(ans, depth[v])
        dfs3(to,v)
dfs3(V)

print(ans)

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 148
# F - Playing Tag on Tree
# https://atcoder.jp/contests/abc148/tasks/abc148_f
from collections import deque

import sys
input = sys.stdin.readline
N, U, V = map(int, input().split())
U -= 1
V -= 1
G = [[] for _ in [0]*N]
for _ in [0]*(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

INF = 10**10

T = [INF]*N
T[U] = 0
A = [INF]*N
A[V] = 0


def bfs(v, dist):
    q = deque()
    q.append(v)
    k = 0
    visited = [0]*N
    while q:
        v = q.popleft()
        visited[v] = 1
        k = dist[v]

        for u in G[v]:
            if visited[u]:
                continue
            q.append(u)
            dist[u] = k+1


bfs(U, T)
bfs(V, A)

if A[U] <= 1:
    print(0)
    exit()

farthest = 0
node = -1
for i, (t, a) in enumerate(zip(T, A)):
    if t < a and farthest < a:
        farthest = a
        node = i

print(farthest-1)

Submission status: Accepted

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

graph = [[] for _ in range(N)]
for i, (Ai, Bi) in enumerate(AB):
    graph[Ai - 1].append(Bi - 1)
    graph[Bi - 1].append(Ai - 1)

import heapq
MY_INF = 10 ** 18

q = [(0, u - 1)]
d_u = [MY_INF] * N
d_u[u - 1] = 0
while len(q) > 0:
    dist, src = heapq.heappop(q)
    for dst in graph[src]:
        dist_tmp = dist + 1
        if d_u[dst] > dist_tmp:
            d_u[dst] = dist_tmp
            heapq.heappush(q, (dist_tmp, dst))

q = [(0, v - 1)]
d_v = [MY_INF] * N
d_v[v - 1] = 0
while len(q) > 0:
    dist, src = heapq.heappop(q)
    for dst in graph[src]:
        dist_tmp = dist + 1
        if d_v[dst] > dist_tmp:
            d_v[dst] = dist_tmp
            heapq.heappush(q, (dist_tmp, dst))

# print("#", d_u)
# print("#", d_v)
            
ans = 0
for i in range(N):
    if d_u[i] < d_v[i] and ans < d_v[i] - 1:
        ans = d_v[i] - 1

print(ans)

Submission status: Accepted

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

def bfs(s):
    q = deque([s])
    dist = [-1]*N
    dist[s] = 0
    leaf = set()
    
    while q:
        v = q.popleft()
        flag = True
        
        for nv in G[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+1
                q.append(nv)
                flag = False
                
        if flag:
            leaf.add(v)
    
    return dist, leaf

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)

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

for i in range(N):
    if i not in leaf and d1[i]<=d2[i]:
        ans = max(ans, d2[i])

print(ans)

Submission status: Accepted

Solution code:
N, S, T = map(int, input().split())
S -= 1
T -= 1

edges = [[] for _ in range(N)]
for _ in range(N - 1):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append(to)
    edges[to].append(fr)

def calc(s):
    minDist = [10**18] * N
    minDist[s] = 0
    st = [s]
    while st:
        now = st.pop()
        d = minDist[now] + 1
        for to in edges[now]:
            if minDist[to] > d:
                minDist[to] = d
                st.append(to)

    return minDist

minDistS = calc(S)
minDistT = calc(T)

ans = 0
for s, t in zip(minDistS, minDistT):
    if s <= t:
        ans = max(ans, t - 1)
print(ans)

Submission status: Accepted

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

def dfs(v,p,d):
    dist[v]=d
    for nv in G[v]:
        if nv==p:
            continue
        dfs(nv,v,d+1)
        
def getSP(v):
    p=v
    if dist[v]==lim:
        return p
    for nv in G[v]:
        if dist[nv]<dist[v]:
            p=getSP(nv)
    return p
    
def depth(v,p,d):
    global maxd
    maxd=max(maxd,dist[v])
    for nv in G[v]:
        if dist[nv]<dist[v]:
            continue
        depth(nv,v,d+1)
    
N,u,v=map(int,input().split());u,v=u-1,v-1
if u==v:
    print(0)
    exit()

G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
    
dist=[-1]*N
dfs(v,-1,0)

lim=dist[u]-(dist[u]-1)//2
SP=getSP(u)
 
maxd=-1
depth(SP,-1,0)

print(maxd-1)

Submission status: Accepted

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

def dfs(v,p,d):
    dist[v]=d
    for nv in G[v]:
        if nv==p:
            continue
        dfs(nv,v,d+1)
        
def getSP(v):
    p=v
    if dist[v]==lim:
        return p
    for nv in G[v]:
        if dist[nv]<dist[v]:
            p=getSP(nv)
    return p
    
def depth(v,p,d):
    global maxd
    maxd=max(maxd,dist[v])
    for nv in G[v]:
        if dist[nv]<dist[v]:
            continue
        depth(nv,v,d+1)
    
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(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
    
dist=[-1]*N
dfs(v,-1,0)

lim=dist[u]-(dist[u]-1)//2
SP=getSP(u)
 
maxd=-1
depth(SP,-1,0)

print(maxd-1)

Submission status: Accepted

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

def dfs(v,p,d):
    dist[v]=d
    for nv in G[v]:
        if nv==p:
            continue
        dfs(nv,v,d+1)
def getSP(v):
    p=v
    if dist[v]==lim:
        return p
    for nv in G[v]:
        if dist[nv]<dist[v]:
            p=getSP(nv)
    return p
def depth(v,p,d):
    sdist[v]=d
    for nv in G[v]:
        if dist[nv]<dist[v]:
            continue
        depth(nv,v,d+1)
    
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(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
dist=[-1]*N
dfs(v,-1,0)
lim=dist[u]-(dist[u]-1)//2
SP=getSP(u)
sdist=[-1]*N
depth(SP,-1,0)
D,tmp=-1,-1
for i in range(N):
    if sdist[i]>tmp:
        D=i
        tmp=sdist[i]
print(dist[D]-1)

Submission status: Accepted

Solution code:
def dfs(c,lst):
 n=len(lst)
 ans=[0]*n
 stack = [c-1]
 check = [0]*n #チェック済みリスト
 while stack != [] :
  d=stack.pop()
  if check[d]==0:
   check[d]=1
   for i in lst[d]:
    if check[i]==0:
     stack.append(i)
     ans[i]=ans[d]+1
 return(ans)
import sys
input = sys.stdin.readline
N,u,v=map(int,input().split())
ki=[[] for f in range(N)]
for i in range(N-1):
 a,b = map(int,input().split())
 ki[a-1].append(b-1)
 ki[b-1].append(a-1)
U=dfs(u,ki)
V=dfs(v,ki)
ans=0
for i in range(N):
 if V[i]>U[i]:
  ans=max(ans,V[i]-1)
print(ans)

Submission status: Accepted

Solution code:
def bfs(p):
    stack=[p]
    check = [-1]*n
    check[p] = 0
    while len(stack):
        v = stack.pop()
        for i in root[v]:
            if check[i] == -1:
                check[i]=check[v]+1
                stack.append(i)
    return check
    


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

move_count_u = bfs(u)
move_count_v = bfs(v)

ans = 0

for i in range(n):
    if move_count_u[i] < move_count_v[i]:
        ans = max(move_count_v[i]-1, ans)
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc148/tasks/abc148_f


import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def dist_on_tree(tree, s, N):
    '''tree...(to,cost)の隣接リスト形式
    s...始点ノード
    N...ノード数'''
    from collections import deque
    D = [-1] * N
    D[s] = 0
    que = deque([(s, 0)])  # 現在のノード、そこまでの距離
    while que:
        now, dist = que.popleft()
        for to, cost in tree[now]:
            if D[to] != -1:
                continue
            D[to] = dist + cost
            que.append((to, dist + cost))
    return D


INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations

N, u, v = read_ints()
tree = defaultdict(lambda: [])
for _ in range(N - 1):
    a, b = read_ints()
    a -= 1
    b -= 1
    tree[a].append((b, 1))
    tree[b].append((a, 1))


# u...逃げる v...追いかける
# u,vからxへの距離をud[x],vd[x]とすると、ud[x]<vd[x]を満たすxが答えの候補となる(∵ud[x]>=vd[x]は追いかける方の陣地、その中に突っ込むのは必ず不利 =は距離が同じ、ということはその前に衝突している
# ud[x]<=vd[x]のなかで最も大きなvd[x]-1が答え(uが壁から跳ね返ってvが動かずとも衝突する)

ud = dist_on_tree(tree, u - 1, N)
vd = dist_on_tree(tree, v - 1, N)
dist = ud[v - 1]
# print(ud)
# print(vd)

ans = 0
for x in range(N):
    # if ud[x] + vd[x] == dist and ud[x] == vd[x]:
    #     ans = max(ans, vd[x] - 1 if (vd[x] - ud[x]) & 1 else vd[x])
        # ans
    if ud[x] >= vd[x]:
        continue
    ans = max(ans, vd[x] - 1)

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict as d
from collections import deque

def bfs(adj, start, n):
	visited = [0] * (n + 1)
	tab = [0] * n
	q = deque([start])
	visited[start] = 1
	while q:
		s = q.popleft()
		for i in adj[s]:
			if visited[i] == 0:
				q.append(i)
				visited[i] = 1
				tab[i - 1] = tab[s - 1] + 1
	return tab

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

takahashi = bfs(adj, u, n)
aoki = bfs(adj, v, n)
res = -1
for i in range(n):
	if takahashi[i] <= aoki[i]:
		res = max(res, aoki[i] - 1)

print(res)

Submission status: Accepted

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

def distances(sommet):
	d = [-1]*(N+1)
	File = [sommet]
	d[sommet] = 0
	while File:
		s = File.pop()
		for x in adj[s]:
			if d[x]==-1:
				d[x] = 1+d[s]
				File.append(x)
	return d


t = distances(u)
a = distances(v)

# ~ print(t)
# ~ print(a)

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

Submission status: Accepted

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

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

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

stack = [u-1]
check = [False]*n
check[u-1] = True
check[v-1] = True
takahasi = [0]*n

while stack:
    now = stack.pop()
    for i in range(len(graph[now])):
        if check[graph[now][i]]:continue
        check[graph[now][i]] = True
        stack.append(graph[now][i])
        takahasi[graph[now][i]] = 1 + takahasi[now]

aoki = [0]*n
stack = [v-1]
check = [False]*n
check[v-1] = True
while stack:
    now = stack.pop()
    for i in range(len(graph[now])):
        if check[graph[now][i]]:continue
        check[graph[now][i]] = True
        stack.append(graph[now][i])
        aoki[graph[now][i]] = 1 + aoki[now]

#print(takahasi)
#print(aoki)

ans = 0
ans_= n+1
takahasi[u-1] = -1

henone = [0]*n
for i in range(n):
    if len(graph[i]) == 1:
        henone[i] = 1

for i in range(n):
    if henone[i] == 1 and takahasi[i] != 0 and takahasi[i] < aoki[i]:
        ans = max(aoki[i]-1,ans)
    """
    if takahasi[i] == 0:continue
    if takahasi[i] < aoki[i]:
        if (aoki[i] - takahasi[i]) % 2 == 1:
            ans = max(ans,aoki[i]-1)
        else:
            ans = max(ans,aoki[i])
    elif takahasi[i] == aoki[i]:
        ans_ = min(ans_,takahasi[i])
    """
print(ans)

Submission status: Accepted

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

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

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

for x,y in E:
    EDGE[x].append(y)
    EDGE[y].append(x)

from collections import deque
T=[-1]*(N+1)

Q=deque()
Q.append(u)
T[u]=0

while Q:
    x=Q.pop()
    for to in EDGE[x]:
        if T[to]==-1:
            T[to]=T[x]+1
            Q.append(to)

A=[-1]*(N+1)

Q=deque()
Q.append(v)
A[v]=0

while Q:
    x=Q.pop()
    for to in EDGE[x]:
        if A[to]==-1:
            A[to]=A[x]+1
            Q.append(to)


OK=[0]*(N+1)

for i in range(N+1):
    if T[i]<A[i]:
        OK[i]=1

ANS=0
for i in range(N+1):
    if OK[i]==1:
        ANS=max(ANS,A[i])

print(max(0,ANS-1))

Submission status: Accepted

Solution code:
n, u, v = map(int, input().split())
u, v = u-1, v-1
edges = [[] for i in range(n)]
for i in range(n-1):
    ai, bi = map(int, input().split())
    ai, bi = ai-1, bi-1
    edges[ai].append(bi)
    edges[bi].append(ai)

depth = 0
already = [0 for i in range(n)]
already[v] = 1
nodes = [v]
while nodes != []:
    depth += 1
    next_nodes = []
    for node in nodes:
        children = edges[node]
        for child in children:
            if already[child] == 0:
                already[child] = depth
                next_nodes.append(child)
    nodes = next_nodes
already[v] = 0

depth = 0
already_u = [0 for i in range(n)]
already_u[u] = 1
nodes = [u]
while nodes != []:
    depth += 1
    next_nodes = []
    for node in nodes:
        children = edges[node]
        for child in children:
            if already_u[child] == 0:
                already_u[child] = depth
                next_nodes.append(child)
    nodes = next_nodes
already_u[u] = 0

maxi = 0
for i in range(n):
    if already_u[i] < already[i]:
        maxi = max(maxi, already[i])

print(maxi-1)

Submission status: Accepted

Solution code:
N,u,v=map(int, input().split())
import sys
sys.setrecursionlimit(10**6)
T=[[] for _ in range(N)]
for i in range(N-1):
    a,b=map(int, input().split())
    T[a-1].append(b-1)
    T[b-1].append(a-1)


def dfs(start):
    tolist=T[start]
    nowd=done[start]
    for next_n in tolist:
        if done[next_n]==-1:
            done[next_n]=nowd+1
            dfs(next_n)

done=[-1]*N
done[u-1]=0
dfs(u-1)
dtaka=done.copy()
done=[-1]*N
done[v-1]=0
dfs(v-1)
dao=done.copy()
ans=0
for i in range(N):
    t=dtaka[i]
    a=dao[i]
    if a>t:
        ans=max(ans, a)
print(ans-1)

Submission status: Accepted

Solution code:
N, U, V = map(int, input().split())
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)


def dist(s):
    dist = [-1] * (N + 1)
    node = [s]
    dist[s] = 0
    while node:
        s = node.pop()
        for t in edge[s]:
            if dist[t] == -1:
                dist[t] = dist[s] + 1
                node.append(t)
    return dist


taka = dist(U)
aoki = dist(V)
can_go = taka[V]

ans = 0
for t, a in zip(taka[1:], aoki[1:]):
    if t <= a:
        ans = max(ans, a - 1)
print(ans)

Submission status: Accepted

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

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

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)

is_leaf = [True]*N
d1 = bfs(V-1)
d2 = bfs(U-1)
ans = 0

for i in range(N):
    if not is_leaf[i] and d2[i]<=d1[i]:
        ans = max(ans, d1[i])
    
print(ans)

Submission status: Accepted

Solution code:
n,u,v=map(int,input().split())
u-=1
v-=1
edge=[[]for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edge[a].append(b)
  edge[b].append(a)
aoki=[10**10]*n
taka=[10**10]*n
aoki[v]=0
taka[u]=0
Q=[v]
visited={v}
co=1
while Q:
  P=[]
  for i in Q:
    for j in edge[i]:
      if j in visited:continue
      aoki[j]=co
      visited.add(j)
      P.append(j)
  Q=P
  co+=1
Q=[u]
visited={u}
co=1
while Q:
  P=[]
  for i in Q:
    for j in edge[i]:
      if j in visited:continue
      taka[j]=co
      visited.add(j)
      P.append(j)
  Q=P
  co+=1
ans=0
for i in range(n):
  if taka[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())
u -= 1
v -= 1
graph = [[] for _ in range(N)]
for _ in range(N-1):
  a, b = map(lambda x:int(x)-1, input().split())
  graph[a] += [b]
  graph[b] += [a]

def bfs(s):
  dist = [-1]*N
  q = deque([s])
  dist[s] = 0

  while q:
    u = q.popleft()
    for v in graph[u]:
      if dist[v] == -1:
        dist[v] = dist[u] + 1
        q.append(v)

  return dist

d1 = bfs(u)
d2 = bfs(v)
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:
ma = lambda :map(int,input().split())
n,u,v = ma()
u,v = u-1,v-1
tree = [[] for i in range(n)]
import collections

for i in range(n-1):
    a,b = ma()
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
que = collections.deque([(v,0)])
vis = [False]*n
dist_v = [0]*n
while que:
    now,c = que.popleft()
    vis[now] = True
    dist_v[now] = c
    for node in tree[now]:
        if not vis[node]:
            que.append((node,c+1))
que = collections.deque([(u,0)])
vis = [False]*n
dist_u = [0]*n
while que:
    now,c = que.popleft()
    vis[now] = True
    dist_u[now] = c
    for node in tree[now]:
        if not vis[node]:
            que.append((node,c+1))
ans = 0
for i in range(n):
    if dist_u[i] < dist_v[i]:
        ans = max(ans,dist_v[i])
print(ans-1)

Submission status: Accepted

Solution code:
from collections import deque
n, u, v = map(int,input().split())
tree = [[] for _ in range(n+1)]
for _i in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)


def solve(x):
    visit = [-1 for _ in range(n+1)]
    visit[x] = 0
    q = deque([x])
    while q:
        p = q.popleft()
        for i in tree[p]:
            if visit[i] < 0:
                visit[i] = visit[p]+1
                q.append(i)
    return visit

visit_a = solve(v)
visit_t = solve(u)

x, y = [], []
for i in range(1, n+1):
    if visit_a[i] >= visit_t[i]:
        x.append(visit_a[i])
        y.append(visit_t[i])
p = x.index(max(x))

print(x[p]-1)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
n,u,v=map(int,input().split())
node=[[]for _ in range(n)]
for _ in range(n-1):
	a,b=map(int,input().split())
	node[a-1].append(b-1)
	node[b-1].append(a-1)
def dfs(i):
	visited[i]=1
	for x in node[i]:
		if visited[x]==0:
			dis[x]=dis[i]+1
			dfs(x)
inf=10**9
dis=[inf]*n;dis[u-1]=0;visited=[0]*n
dfs(u-1)
dis2=[]
from copy import copy
dis_dash=copy(dis)
dis2.append(dis_dash)
dis[v-1]=0;visited=[0]*n
dfs(v-1)
dis2.append(dis)
cnt=0
for i in range(n):
	if dis2[0][i]<dis2[1][i]:
		cnt=max(cnt,dis2[1][i])
print(cnt-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
N, u, v = map(int, input().split())
u -= 1
v -= 1
edges = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

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

def calc_dist(s):
    global dist
    dist = [0] * N
    dfs(s)
    return dist

distS = calc_dist(u)
distT = calc_dist(v)

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

Submission status: Accepted

Solution code:
from collections import deque, defaultdict
from copy import deepcopy
import sys
import resource

sys.setrecursionlimit(10**5)

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

depth = dict(zip(list(range(1,N+1)),[-1]*N))

def bfs(s):
    if graph[s]:
        for v in graph[s]:
            if depth[v] == -1:
                depth[v] = depth[s] + 1
                bfs(v)

depth = dict(zip(list(range(1,N+1)),[-1]*N))
depth[v] = 0
bfs(v)
depth_v = deepcopy(depth)

depth = dict(zip(list(range(1,N+1)),[-1]*N))
depth[u] = 0
bfs(u)
depth_u = depth
depth_v = sorted(depth_v.items(), key = lambda x:x[0])
depth_u = sorted(depth_u.items(), key= lambda x:x[0])

MAX = 0
for v,u in zip(depth_v, depth_u):
    if u[1] < v[1]:
        MAX = max(MAX,v[1])
print(MAX-1)

Submission status: Accepted

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

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

    # uv間経路を求める
    st = [u]
    prev = [None for i in range(n)]
    while st:
        x = st.pop()
        for y in adj[x]:
            if y == prev[x]: continue
            prev[y] = x
            st.append(y)
    path = [v]
    while path[-1] != u:
        path.append(prev[path[-1]])
    path = list(reversed(path))

    # crossからsquareを経由しない最遠ノードstarを求める（a59p22）
    l = len(path) - 1
    cross = path[(l - 1) // 2]
    square = path[(l - 1) // 2 + 1]
    st = [(cross, 0)]
    prev = [None for i in range(n)]
    dist = [-1 for i in range(n)]
    while st:
        x, d = st.pop()
        dist[x] = d
        for y in adj[x]:
            if y == prev[x]: continue
            if y == square: continue
            prev[y] = x
            st.append((y, d + 1))
    star_square = max(dist)

    if l % 2 == 1:
        res = (l - 1) // 2 + star_square
    else:
        res = (l - 1) // 2 + star_square + 1
    print(res)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,u,v=map(int,input().split())
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)
va=[-1]*n
q=[v-1]
va[v-1]=0
while q:
    x=q.pop()
    for j in tree[x]:
        if va[j]==-1:
            q.append(j)
            va[j]=va[x]+1
q=[u-1]
vt=[-1]*n
vt[u-1]=0
ans=0
while q:
    x=q.pop()
    ans=max(ans,va[x])
    for j in tree[x]:
        if vt[j]==-1:
            if vt[x]+1<va[j]:
                q.append(j)
                vt[j]=vt[x]+1
            elif vt[x]+1==va[j]:
                vt[j]=vt[x]+1
print(ans-1)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7
    
    # u高橋, s青木
    n,u,s = map(int, input().split())
    adj = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(n-1):
        a,b = map(int, input().split())
        adj[a-1].append(b-1)
        adj[b-1].append(a-1)
    ta = [-1]*n
    ao = [-1]*n

    d = deque([s-1])
    ao[s-1] = 0
    while d:
        v = d.popleft()
        for nv in adj[v]:
            if ao[nv] == -1:
                ao[nv] = ao[v] + 1
                d.append(nv)

    d = deque([u-1])
    ta[u-1] = 0
    while d:
        v = d.popleft()
        for nv in adj[v]:
            if ta[nv] == -1:
                ta[nv] = ta[v] + 1
                d.append(nv)

    res = 0
    for i in range(n):
        if ta[i] < ao[i]:
            res = max(res, ao[i]-1)
    print(res)

if __name__ == '__main__':
    main()