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 heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True
#for i in range(n):

ans=0

n,t,a=LI_()
n+=1
g,c=GI(n,n-1)

#for i in range(1,30):


#vにはdepthをセット & -1 で未訪問フラグ



def bfs(x):  # x スタート
    v=[-1]*(n)
    p=deque()
    p.append(x)
    v[x]=0
    while p:
        c=p.popleft()
        for i in g[c]:
            if v[i]==-1:
                p.append(i)
                v[i]=v[c]+1
    return v



v=bfs(a)
w=bfs(t)
ans=0
for i in range(n):
    if v[i]>=w[i] and max([v[j] for j in g[i]])>v[i]:
        ans=max(ans,v[i])
#print(max(0,ans-1))
print(ans)

Submission status: Accepted

Solution code:
I = [int(_) for _ in open(0).read().split()]
N, U, V = I[:3]
A, B = I[3::2], I[4::2]
G = [set() for _ in range(N + 1)]
for a, b in zip(A, B):
    G[a].add(b)
    G[b].add(a)


def dfs(x):
    dist = [None] * (N + 1)
    dist[x] = 0
    stack = set([x])
    while stack:
        x = stack.pop()
        for xn in G[x]:
            if dist[xn] is None:
                dist[xn] = dist[x] + 1
                stack.add(xn)
    return dist


distt = dfs(U)
dista = dfs(V)
ans = 0
for t, a in zip(distt[1:], dista[1:]):
    if t < a:
        ans = max(ans, a - 1)
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(n, cnt):
  aoki_visited[n] = True
  aoki[n] = cnt
  for x in edge[n]:
    if aoki_visited[x] == False:
      tami(x, cnt+1)

def tami2(n, cnt):
  choku_visited[n] = True
  if cnt <= aoki[n]:
    choku[n] = cnt
    for x in edge[n]:
      if choku_visited[x] == False:
        tami2(x, cnt+1)

N, u, v = IL()
ab = [IL() for _ in range(N-1)]

aoki = [0]*(N+1)
aoki_visited = [False]*(N+1)
choku = [0]*(N+1)
choku_visited = [False]*(N+1)

edge = [[] for _ in range(N+1)]
for a,b in ab:
  edge[a].append(b)
  edge[b].append(a)

ans = 0
aoki[v] = MAX_INT
tami(v, 0)
tami2(u, 0)
#print(aoki)
#print(choku)

for i in range(N+1):
  if choku[i] == 0 and i != u:
    continue
  if aoki[i] > choku[i]:
    ans = max(ans, aoki[i] - 1)

print(ans)

Submission status: Accepted

Solution code:
from sys import exit

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

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

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


def calc_destination(start, edges):
    destination = [-1] * (N + 1)
    destination[start] = 0
    q = [start]
    while len(q) != 0:
        current = q.pop()
        for n in edges[current]:
            if destination[n] != -1:
                continue
            destination[n] = destination[current] + 1
            q.append(n)
    return destination


tak = calc_destination(u, edges)
aok = calc_destination(v, edges)

result = 0
for i in range(1, N + 1):
    aoki = aok[i]
    if tak[i] >= aoki:
        continue
    if aoki > result:
        result = aoki
print(result - 1)

Submission status: Accepted

Solution code:
def calc_destination(start, edges, N):
    destination = [-1] * (N + 1)
    destination[start] = 0
    q = [start]
    while len(q) != 0:
        current = q.pop()
        for n in edges[current]:
            if destination[n] != -1:
                continue
            destination[n] = destination[current] + 1
            q.append(n)
    return destination

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

    if u == v:
        print(0)
        return

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

    tak = calc_destination(u, edges, N)
    aok = calc_destination(v, edges, N)

    result = 0
    for i in range(1, N + 1):
        aoki = aok[i]
        if tak[i] >= aoki:
            continue
        if aoki > result:
            result = aoki
    print(result - 1)

main()

Submission status: Accepted

Solution code:
import numpy as np 

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

pt= [[0]*0 for i in range(n)] 
for i in range(n-1):
    pt[S[i][0]-1].append(S[i][1])
    pt[S[i][1]-1].append(S[i][0])

def bfs(v):
    d=[-1]*n
    d[v-1]=0
    q=[v]
    c=1
    while q:
        q1=[]
        for i in q:
            for j in pt[i-1]:
                if d[j-1]==-1:
                    d[j-1]=c
                    q1.append(j)
        q=q1
        c+=1
    return d
bfs_v=np.array(bfs(v))
bfs_u=np.array(bfs(u))
bfs_v_replace=bfs_v[bfs_v>bfs_u]
answer=np.max(bfs_v_replace)-1
print("{}".format(answer))

Submission status: Accepted

Solution code:

import heapq
import sys
sys.setrecursionlimit(10**6)

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

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

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

INF = float("inf")
from_u = [INF] * (N+1)
from_u[u] = -1
from_v = [INF] * (N+1)
from_v[v] = -1

def solve(prev, curr, distances):
    distances[curr] = distances[prev] + 1
    for next in es[curr]:
        if distances[next] == INF:
            solve(curr, next, distances)

solve(u,u,from_u)
solve(v,v,from_v)



ans = 0
for i in range(1,N+1):
    if from_u[i] < from_v[i]:
        # 追い詰めた段階で高橋君が自ら青木君のマスに戻ってくるので、最後の端っこまで追い詰めなくていいから-1
        ans = max(ans, from_v[i]-1)

print(ans)

Submission status: Accepted

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

import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

#n,w = map(int,input().split()) #n:頂点数　w:辺の数
edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(n-1):
    z=1
    x,y = map(int,input().split())
    x-=1;y-=1
    edge[x].append([z,y]) #有向辺
    edge[y].append([z,x]) #有向辺
A=dijkstra_heap(u)
B=dijkstra_heap(v)
l=[]
for i in range(n):
    l.append([B[i],A[i]])
l.sort()
l=l[::-1]
#print(A)
#print(B)
#print(l)
for i in range(n):
    if l[i][0]>l[i][1]:
        print(l[i][0]-1)
        break

Submission status: Accepted

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


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

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


dist = []
def dfs(v, depth=0, parent=-1):
    global dist
    dist[v] = depth
    for u in graph[v]:
        # 親には行かないようにする
        if u == parent:
            continue
        dfs(u, depth + 1, v)


def calc_dist(s):
    global dist
    dist = [0 for _ in range(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])

print(mx - 1)

Submission status: Accepted

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

dist_u = [-1]*N
dist_v = [-1]*N
dist_u[u] = 0
dist_v[v] = 0

from collections import deque

H = deque()
H.append(u)
while H:
    x = H.popleft()
    for nx in table[x]:
        if dist_u[nx] == -1:
            H.append(nx)
            dist_u[nx] = dist_u[x]+1

H = deque()
H.append(v)
while H:
    x = H.popleft()
    for nx in table[x]:
        if dist_v[nx] == -1:
            H.append(nx)
            dist_v[nx] = dist_v[x]+1

tmp = 0
for i in range(N):
    if dist_u[i] < dist_v[i] and dist_v[i] >= tmp:
        tmp = dist_v[i]
        memo = i
print(tmp-1)

Submission status: Accepted

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

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


def calcDist(s):
    global dist
    dist = [0 for _ in range(N)]
    dfs(s)
    return dist


N, s, t = map(int, input().split())
s -= 1
t -= 1
to = [[] for _ in range(N)]
dist = [0 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)

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)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, u, v = (int(i) for i in input().split())
    G = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)

    d_from_u = [-1] * N
    d_from_v = [-1] * N

    def dfs(v, d):
        todo = []
        d[v] = 0
        todo.append(v)
        while todo:
            u = todo.pop()
            for next_v in G[u]:
                if 0 <= d[next_v]:
                    continue
                d[next_v] = d[u] + 1
                todo.append(next_v)

    u, v = u-1, v-1
    dfs(u, d_from_u)
    dfs(v, d_from_v)
    ans = 0
    for du, dv in zip(d_from_u, d_from_v):
        if du < dv and ans < dv - 1:
            ans = dv - 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,u,v=map(int,input().split())
E=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  E[a-1].append(b-1)
  E[b-1].append(a-1)
  
distU=[0]*N
distV=[0]*N

stack=[]
stack.append([u-1,0,-1])
while stack:
  node=stack.pop()
  e=node[0]
  dist=node[1]
  parent=node[2]
  distU[e]=dist
  children=E[e]
  for child in children:
    if child==parent:
      continue
    stack.append([child,dist+1,e])
    
stack=[]
stack.append([v-1,0,-1])
while stack:
  node=stack.pop()
  e=node[0]
  dist=node[1]
  parent=node[2]
  distV[e]=dist
  children=E[e]
  for child in children:
    if child==parent:
      continue
    stack.append([child,dist+1,e])

maxdist=0
for i in range(N):
  if maxdist<distV[i] and distU[i]<distV[i]:
    maxdist=distV[i]

print(maxdist-1)

Submission status: Accepted

Solution code:
N,u,v=map(int,input().split())
E=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  E[a-1].append(b-1)
  E[b-1].append(a-1)
  
distU=[0]*N
distV=[0]*N

stack=[]
stack.append([u-1,0,-1])
while stack:
  node=stack.pop()
  e=node[0]
  dist=node[1]
  parent=node[2]
  distU[e]=dist
  children=E[e]
  for child in children:
    if child==parent:
      continue
    stack.append([child,dist+1,e])
    
stack=[]
stack.append([v-1,0,-1])
while stack:
  node=stack.pop()
  e=node[0]
  dist=node[1]
  parent=node[2]
  distV[e]=dist
  children=E[e]
  for child in children:
    if child==parent:
      continue
    stack.append([child,dist+1,e])

maxdist=0
Vpoint=0
maxi=-1
for i in range(N):
  if maxdist<distV[i] and distU[i]<distV[i]:
    maxdist=distV[i]

print(maxdist-1)

Submission status: Accepted

Solution code:
n, uplus, vplus = map(int, input().split())
u, v = uplus-1, vplus-1
adj = [[] for _ in range(n)]
for _ in range(n-1):
  aplus, bplus = map(int, input().split())
  a, b = aplus-1, bplus-1
  adj[a].append(b)
  adj[b].append(a)

u_dist = [n] * n
u_dist[u] = 0
stack = [u]
while stack:
  vertex = stack.pop()
  for nxt in adj[vertex]:
    if u_dist[nxt] == n:
      u_dist[nxt] = u_dist[vertex] + 1
      stack.append(nxt)

v_dist = [n] * n
v_dist[v] = 0
stack = [v]
leaves = []
while stack:
  vertex = stack.pop()
  isleaf = True
  for nxt in adj[vertex]:
    if v_dist[nxt] == n:
      v_dist[nxt] = v_dist[vertex] + 1
      stack.append(nxt)
      isleaf = False
  if isleaf:
    leaves.append(vertex)

max_depth = 0
for leaf in leaves:
  depth = v_dist[leaf]
  if u_dist[leaf] < depth and max_depth < depth:
    max_depth = depth
    
print(max_depth - 1)

Submission status: Accepted

Solution code:
def main():
    n, u, v = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    u -= 1
    v -= 1
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    da = [-1]*n
    dt = [-1]*n
    dt[u] = 0
    da[v] = 0
    q = [u]
    cnt = 0
    while q:
        cnt += 1
        qq = []
        for i in q:
            for j in g[i]:
                if dt[j] == -1:
                    dt[j] = cnt
                    qq.append(j)
        q = qq
    q = [v]
    cnt = 0
    while q:
        cnt += 1
        qq = []
        for i in q:
            for j in g[i]:
                if da[j] == -1:
                    da[j] = cnt
                    qq.append(j)
        q = qq
    priority = sorted([[i, j] for i, j in enumerate(da)], key=lambda x: -x[1])

    for i, j in priority:
        if da[i] > dt[i]:
            print(da[i]-1)
            return 0


main()

Submission status: Accepted

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

Dep_u = [-1] *n 
Dep_v = [-1] *n

Dep_u[u] = 0
Dep_v[v] = 0

from collections import deque
##bfs2回が簡明
def bfs(L,x):
    Q = deque()
    Q.append(x)
    while Q:
        y = Q.popleft()
        for z in Tr[y]:
            if L[z] == -1:
                L[z] = L[y] + 1
                Q.append(z)
                
bfs(Dep_u,u)
bfs(Dep_v,v)

ans = 0###0から

for i in range(n):
    if Dep_v[i]>Dep_u[i]:
        ans = max(ans,Dep_v[i]-1)###v
print(ans)

Submission status: Accepted

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

import heapq

def dijkstra(s):
    d = [10**6]*N
    used = [True]*N
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in E[s]:
        heapq.heappush(edgelist, [1, e])
    while edgelist:
        t = heapq.heappop(edgelist)
        if not used[t[1]]:
            continue
        used[t[1]] = False
        d[t[1]] = t[0]
        for e in E[t[1]]:
            if used[e]:
                heapq.heappush(edgelist, [t[0]+1, e])
                
    return d

T = dijkstra(u-1)
A = dijkstra(v-1)

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
n,u,v = map(int,input().split())
u-=1
v-=1
ki = [[]for i in range(n)]
distt = [0]*n
dista = [0]*n
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    ki[a].append(b)
    ki[b].append(a)
def dfst(now,last = -1):
    for next in ki[now]:
        if next == last:continue
        distt[next] = distt[now]+1
        dfst(next,now)
def dfsa(now,last = -1):
    for next in ki[now]:
        if next == last:continue
        dista[next] = dista[now]+1
        dfsa(next,now)
    
dfst(u)
dfsa(v)
ans = 0
for i in range(n):
    if dista[i]<=distt[i]:continue
    ans = max(ans,dista[i]-1)
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(200000)

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

# nodeの値を-1しておく
u = u-1
v = v-1

# Making Adjacency list
Adj_dict = {}
for i in range(n):
    new = {i: []}
    Adj_dict.update(new)

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

def tree_distance(Adj_dict, start, Visited, distance, Dist_list):
    
    # 現在いる位置を Visited = True に変更する
    Visited[start] = True

    # 該当するnodeの距離を記録して、distanceを1加算する
    Dist_list[start] = distance
    distance += 1

    # 訪れていないnodeに対して、dfs
    for node in Adj_dict[start]:
        if Visited[node] == False:
            tree_distance(Adj_dict, node, Visited, distance, Dist_list)
    
    return


Dist_list = [0 for _ in range(n)]
Visited = [False for _ in range(n)]
distance = 0
tree_distance(Adj_dict, u, Visited, distance, Dist_list)
Taka = Dist_list

Dist_list = [0 for _ in range(n)]
Visited = [False for _ in range(n)]
distance = 0
tree_distance(Adj_dict, v, Visited, distance, Dist_list)
Aoki = Dist_list

Taka_num = 0
node = 0
ans = 0
for i in range(n):
    if Aoki[i] > Taka[i]:
        ans = max(ans, Aoki[i]-1)


print(ans)

Submission status: Accepted

Solution code:
INF = float('inf')

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

def bfsMinCosts(adjList, vSt, INF):
    numV = len(adjList)
    costs = [INF] * numV
    costs[vSt] = cost = 0
    vs = [vSt]
    while vs:
        cost += 1
        v2s = []
        for v in vs:
            for v2 in adjList[v]:
                if costs[v2] == INF:
                    costs[v2] = cost
                    v2s.append(v2)
        vs = v2s
    return costs

costUs = bfsMinCosts(adjL, u, INF)
costVs = bfsMinCosts(adjL, v, INF)

maxC = -1
vMaxC = -1
for v, (costU, costV) in enumerate(zip(costUs, costVs)):
    if costU >= costV: continue
    if costV > maxC:
        maxC = costV
        vMaxC = v

print(maxC-1)

Submission status: Accepted

Solution code:
#!python3

def resolve():
    N, u, v = map(int, input().rstrip().split())
    N1 = N + 1

    d = [[] for _ in range(0, N1)]
    for i in range(1, N):
        a, b = map(int, input().rstrip().split())

        d[a].append(b)
        d[b].append(a)

    from collections import deque

    def f(x):
        q = deque()
        q.append(x)
        X = [-1] * N1

        X[x] = 0
        while q:
            x = q.popleft()
            for i in d[x]:
                if X[i] == -1:
                    X[i] = X[x] + 1
                    q.append(i)
        return X

    U = f(u)
    V = f(v)

    m = 0
    for uu, vv in zip(U, V):
        if uu < vv:
            if vv > m:
                m = vv
    print(m-1)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from collections import deque

N,u,v = map(int,input().split())
u-=1
v-=1
points = [set() for x in range(N)]
for i in range(N-1):
    A,B = map(int,input().split())
    A-=1
    B-=1
    points[A].add(B)
    points[B].add(A)

def distance_array(x):
    arr = [-1] * N
    scanned = set()
    q = deque()
    q.append((x,-1))
    for i in range(N):
        po,root_d = q.pop()
        scanned.add(po)
        this_d = root_d + 1
        arr[po] = this_d
        for ii in points[po]:
            if ii in scanned:
                continue
            q.append((ii,this_d))
    return arr

leaves = filter(lambda x: len(points[x])==1,range(N))
du = distance_array(u)
dv = distance_array(v)
# 目指す点までの距離 du, dv
# まず2duターンかかって 0, (dv-du)になる

# (dv-du) + 1 = 2n
# (dv-du)     = 2n

# 4n  ターン目に高橋が動いて1, (dv-du)-2n+2
# # 成立していたら終了 求める答えは 2du + 2n
# 4n+1ターン目に青木が動いて1, (dv-du)-2n+1
# # 成立していたら終了 求める答えは 2du + 2n + 1
# 4n+2ターン目に高橋が動いて0, (dv-du)-2n+1
# # 成立していたら終了 求める答えは 2du + 2n + 1
# 4n+3ターン目に青木が動いて0, (dv-du)-2n
# # 成立していたら終了 求める答えは 2du + 2n + 2

b = filter(lambda x: dv[x]-du[x] > 0,leaves)
c = max(b,key=lambda x: dv[x])

def aa():
    s = 0
    ddu = du[c]
    ddv = dv[c]
    while True:
        if ddu == ddv:
            return s
        ddu = abs(ddu - 1)
        if ddu == ddv:
            return s
        ddv -= 1
        s += 1

print(aa())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100010)

n,u,v = [int(i)-1 for i in input().split()]
n+=1
AB = [[int(i)-1 for i in input().split()] for _ in range(n-1)]

nodes = [[] for _ in range(n)]
for ab in AB:
    nodes[ab[1]].append(ab[0])
    nodes[ab[0]].append(ab[1])

route = []
def search(p,before=-1):
    if len(nodes[p])==1 and p!=u:
        return False
    for node in nodes[p]:
        if node == before:
            continue
        if search(node,p) or node==v:
            route.append(p)
            return True
    return False
search(u)
route.reverse()
key = route[(len(route)-1)//2]
if len(route) == 1:
    nodes[key].remove(v)
else:
    nodes[key].remove(route[(len(route)-1)//2+1])

que = [key]
time = -1
while len(que)>0:
    time+=1
    newque = []
    while len(que)>0:
        p = que.pop()
        for q in nodes[p]:
            nodes[q].remove(p)
            newque.append(q)
    que=newque

tokey = len(route)//2+1
if time == 0:
    tokey -= 1

time = max(1,time)
print( tokey + time-1 )

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n, u, v = LI_()
    n += 1
    edg = [[] for i in range(n)]
    for _ in range(n-1):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    dist_u = [-1] * n
    dist_u[u] = 0
    dist_v = [-1] * n
    dist_v[v] = 0
    q = deque([u])
    while q:
        p = q.pop()
        dp = dist_u[p]
        for e in edg[p]:
            if dist_u[e] < 0:
                dist_u[e] = dp + 1
                q.append(e)
    q = deque([v])
    while q:
        p = q.pop()
        dp = dist_v[p]
        for e in edg[p]:
            if dist_v[e] < 0:
                dist_v[e] = dp + 1
                q.append(e)
    ans = 0
    while dist_u[v] - dist_u[u] > 2:
        for e in edg[u]:
            if dist_v[e] < dist_v[u]:
                u = e
                continue
        for e in edg[v]:
            if dist_u[v] > dist_u[e]:
                v = e
                continue
        ans += 1
    f = dist_u[v]-dist_u[u] == 2
    ans += f
    q = deque([u])
    dist_u = [-1] * n
    for e in edg[v]:
        dist_u[e] = 1
    dist_u[u] = 0
    while q:
        u = q.pop()
        dp = dist_u[u]
        for e in edg[u]:
            if dist_u[e] < 0 and v != e:
                dist_u[e] = dp + 1
                q.append(e)
    if f and max(dist_u) == 1:
        ans -= 1
    print(max(dist_u)+ ans)

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/python3
import sys

sys.setrecursionlimit(10 ** 5)

def search(n, total, dic):
    if dic[n] >= 0:
        return
    else:
        dic[n] = total
    for i in br[n]:
        search(i, total + 1, dic)

n, u, v = map(int, input().split())
br = {}
disu = {}
disv = {}
for i in range(n):
    br[i + 1] = []
    disu[i + 1] = -1
    disv[i + 1] = -1
for i in range(n - 1):
    a, b = map(int, input().split())
    br[a].append(b)
    br[b].append(a)

search(u, 0, disu)
search(v, 0, disv)
far = 0
for i in range(1, n + 1):
    if disv[i] < disu[i]:
        continue
    else:
        far = max(far, disv[i])

print(far - 1)

Submission status: Accepted

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

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

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

visit1 = [False] * n
visit2 = [False] * n
visit1[u-1] = True
visit2[v-1] = True

dis1 = [-1] * n
dis2 = [-1] * n
dis1[u-1] = 0
dis2[v-1] = 0

stack1 = [u-1]
stack2 = [v-1]

while stack1:
    l = stack1.pop(-1)
    for i in edges[l]:
        if visit1[i] == False:
            visit1[i] = True
            dis1[i] = dis1[l] + 1
            stack1.append(i)

while stack2:
    l = stack2.pop(-1)
    for i in edges[l]:
        if visit2[i] == False:
            visit2[i] = True
            dis2[i] = dis2[l] + 1
            stack2.append(i)

ans = 0

for i in range(n):
    if dis1[i] < dis2[i]:
        ans = max(ans, dis2[i])

print(ans-1)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, u, v = inpl()
u -= 1
v -= 1
edges = [set() for _ in range(N)]
AB = []
for i in range(N-1):
    A, B = inpl()
    edges[A-1].add(B-1)
    edges[B-1].add(A-1)

parent = [None]*N
position = [0]*N
depth = [0]*N
head, tail = 0, 1
pool = [(v, None, 0, head)]
while pool:
    n, p, d, pos = pool.pop()
    if pos == head:
        pool.append((n, p, d, tail))
        for c in edges[n]:
            if c == p:
                continue
            parent[c] = n
            position[c] = d+1
            pool.append((c, n, d+1, head))
    else:
        if p is not None:
            depth[p] = max(depth[n]+1, depth[p])

turn_d = position[u]//2 + 1
turn_node = u
for i in range(turn_d, position[u]):
    turn_node = parent[turn_node]

print(turn_d + depth[turn_node] - 1)

Submission status: Accepted

Solution code:
from collections import deque
N, ta, ao = map(int, input().split())  # N頂点, 逃げ役の初期値u, 鬼役の初期値v
ta -= 1
ao -= 1
tree = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    tree[a].append(b)
    tree[b].append(a)
# これで木の構造が定義できた
takahashi_distant = [10**9] * N
aoki_distant = [10**9] * N

# 逃げ役の方 (高橋くん) から先に計算する
q = deque([ta])
takahashi_distant[ta] = 0
visited = [False] * N
visited[ta] = True
while len(q):
    v = q.pop()
    for e in tree[v]:
        if visited[e]:
            continue
        visited[e] = True
        takahashi_distant[e] = takahashi_distant[v] + 1
        q.append(e)

# 鬼役の方 (青木くんくん) の計算する
q = deque([ao])
aoki_distant[ao] = 0
visited = [False] * N
visited[ao] = True
while len(q):
    v = q.pop()
    for e in tree[v]:
        if visited[e]:
            continue
        visited[e] = True
        aoki_distant[e] = aoki_distant[v] + 1
        q.append(e)

# print(takahashi_distant)
# print(aoki_distant)
# aoki_distant[i] > takahashi_distant[i]を満たす時のaoki_distantの最大値-1
ans = 0
for i in range(N):
    if aoki_distant[i] > takahashi_distant[i]:
        ans = max(ans, aoki_distant[i])
print(ans-1)

Submission status: Accepted

Solution code:
from collections import deque

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

def bfs(x):
    dist = [-1]*n
    dist[x] = 0
    que = deque([x])
    while que:
        now = que.pop()
        for nex in G[now]:
            if dist[nex] != -1:continue
            dist[nex] = dist[now] + 1
            que.appendleft(nex)
    return dist

dist_u = bfs(u)
dist_v = bfs(v)

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

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,u,v=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  a-=1;b-=1
  graph[a].append(b)
  graph[b].append(a)
Q=deque([v-1])
Vert=[[0,0] for i in range(n)]
visited=[False]*n
visited[v-1]=True
while Q:
  V=Q.popleft()
  visited[V]=True
  for i in graph[V]:
    if visited[i]:continue
    if i == V:continue
    Vert[i][0]=Vert[V][0]+1
    Q.append(i)
visited=[False]*n
visited[u-1]=True
Q.append(u-1)
while Q:
  V=Q.popleft()
  visited[V]=True
  for i in graph[V]:
    if visited[i]:continue
    if i == V:continue
    Vert[i][1]=Vert[V][1]+1
    Q.append(i)
ans=0
for i in Vert:
  if i[0]>i[1]:
    if i[0]>ans:
      ans=i[0]
print(ans-1)