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:
import heapq
import sys

input = sys.stdin.readline

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

def main():
    N, u, v = map(int, input().split())
    u -= 1
    v -= 1
    edge = [[] for i in range(N)]
    for _ in range(N-1):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        edge[A].append([1,B])
        edge[B].append([1,A])
    
    d1 = dijkstra_heap(u,edge, N)
    d2 = dijkstra_heap(v,edge, N)
    ans = 0
    for i in range(N):
        if d1[i] < d2[i]:
            ans = max(ans, d2[i]-1)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque


def main():
    N, u, v = map(int, input().split())
    adj = [set() for _ in range(N)]
    for _ in range(N-1):
        A, B = map(int, input().split())
        adj[A-1].add(B-1)
        adj[B-1].add(A-1)
    move = [-1] * N
    q = deque([(v-1, 0)])
    while len(q):
        cur, c = q.popleft()
        move[cur] = c
        for nxt in adj[cur]:
            if move[nxt] == -1:
                q.append((nxt, c+1))
    reachable = [False] * N
    q = deque([(u-1, 0)])
    while len(q):
        cur, c = q.popleft()
        reachable[cur] = True
        for nxt in adj[cur]:
            if c+1 <= move[nxt] and not reachable[nxt]:
                q.append((nxt, c+1))
    ans = 0
    for i in range(N):
        if reachable[i] and len(adj[i]) >= 2:
            ans = max(ans, move[i])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7


N, u, v = MI()
nl = [list() for _ in range(N)]
for _ in range(N - 1):
    a, b = MI()
    nl[a - 1].append(b - 1)
    nl[b - 1].append(a - 1)


def distance(v0):
    dist = [0] * N
    q = deque([(v0, -1, 0)])
    while len(q) > 0:
        v, p, d = q.popleft()
        dist[v] = d
        for next_v in nl[v]:
            if next_v != p:
                q.append((next_v, v, d + 1))
    return dist


t = distance(u - 1)
a = distance(v - 1)
initial_dist = t[v - 1]

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,u,v = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)

from collections import deque
Q = deque()
Q.append([v-1,0])
visited=[-1]*n
visited[v-1]=0
while Q:
    now,cnt = Q.popleft()
    for nxt in link[now]:
        if visited[nxt]!=-1:
            continue
        visited[nxt]=cnt+1
        Q.append([nxt,cnt+1])
Q = deque()
Q.append([u-1,0])
v_taka=[-1]*n
v_taka[u-1]=0
while Q:
    now,cnt = Q.popleft()
    for nxt in link[now]:
        if v_taka[nxt]!=-1:
            continue
        if visited[nxt] <= cnt+1:
            continue
        v_taka[nxt]=cnt+1
        Q.append([nxt,cnt+1])
ans=-1
for i in range(n):
    if v_taka[i] == -1:
        continue
    if ans < visited[i]:
        ans=visited[i]
print(ans-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

n,u,v=map(int,input().split())
Graph=[]
for i in range(n):
    Graph.append([])
for i in range(n-1): #隣接頂点の登録
    a,b=map(int,input().split())
    Graph[a-1].append(b-1)
    Graph[b-1].append(a-1)

def dfs(s,b=-1): #深さ優先探索(子,親(初期値は-1))
    for i in Graph[s]: #隣接点に対して
        if i!=b: #親と一緒じゃないとき
            depth[i]=depth[s]+1 #深さを登録
            dfs(i,s) #親子を更新して再探索

depth=[0]*n
dfs(u-1)
dT=depth

depth=[0]*n
dfs(v-1)
dA=depth

dArrest=0
for i in range(n):
    if dA[i]>dT[i]: #Tが先に着ける点のうち
        dArrest=max(dArrest,dA[i]) #一番Aから遠い点
print(dArrest-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

n,u,v=map(int,input().split())
Graph=[]
for i in range(n):
    Graph.append([])
for i in range(n-1): #隣接頂点の登録
    a,b=map(int,input().split())
    Graph[a-1].append(b-1)
    Graph[b-1].append(a-1)

def dfs(s,b=-1): #深さ優先探索(グラフ,スタート,深さ)
    for i in Graph[s]: #隣接点に対して
        if i!=b: #前の点と一緒じゃないとき
            depth[i]=depth[s]+1
            dfs(i,s) #深さを増やし、スタートを更新して再探索

depth=[0]*n
dfs(u-1)
dT=depth

depth=[0]*n
dfs(v-1)
dA=depth

dArrest=0
for i in range(n):
    if dA[i]>dT[i]: #Tが先に着ける点のうち
        dArrest=max(dArrest,dA[i]) #一番Aから遠い点
print(dArrest-1)

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    sys.setrecursionlimit(100000000)

    n,u,v=map(int,input().split())
    u-=1
    v-=1
    tree=[[] for i in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        a-=1
        b-=1
        tree[a].append(b)
        tree[b].append(a)
    
    depth_u=[0]*n #uからの距離
    depth_v=[0]*n #vからの距離
    
    def dfs1(i,before=-1):
        for e in tree[i]:
            if e!=before:
                depth_u[e]=depth_u[i]+1
                dfs1(e,i)
    
    def dfs2(i,before=-1):
        for e in tree[i]:
            if e!=before:
                depth_v[e]=depth_v[i]+1
                dfs2(e,i)
    
    dfs1(u)
    dfs2(v)

    ans=depth_v[u]-1
    for i in range(n):
        if len(tree[i])==1 and depth_u[i]<depth_v[i]:
                ans=max(ans,depth_v[i]-1)
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from functools import lru_cache
    import sys
    input=sys.stdin.readline
    sys.setrecursionlimit(100000000)

    n,u,v=map(int,input().split())
    u-=1
    v-=1
    tree=[[] for i in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        a-=1
        b-=1
        tree[a].append(b)
        tree[b].append(a)
    
    depth=[0]*n
    depth[v]=0
    def dfs(i,before=-1):
        for e in tree[i]:
            if e!=before:
                depth[e]=depth[i]+1
                dfs(e,i)
    dfs(v)
    #print(depth)
    
    max_depth=[-1]*n
    max_depth[v]=0   
    @lru_cache(maxsize=None)
    def dfs2(i,before=-1):
        t=-1
        for e in tree[i]:
            if e!=before:
                t=max(t,dfs2(e,i))
        if t!=-1:
            max_depth[i]=t
            return max_depth[i]
        else:
            max_depth[i]=depth[i]
            return max_depth[i]
            
    dfs2(v)   
    #print(max_depth)
    
    lim=depth[u]
    i,key=u,u
    while i!=v:
        if 2*depth[i]>lim and max_depth[key] < max_depth[i]:
            key=i
            
        for e in tree[i]:
            if depth[e]<depth[i]:
                i=e
                break
                
    print(max_depth[key]-1) 
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import queue
def dist(graph, start):
    q = queue.Queue()
    rtn = [None]*len(graph)
    q.put(start)
    rtn[start] = 0
    while not q.empty():
        target = q.get()
        for index in graph[target]:
            if rtn[index] is None:
                q.put(index)
                rtn[index] = rtn[target] + 1
    return rtn

def solve(dist_t, dist_a):
    ans = 0
    for i in range(len(dist_t)):
        if dist_t[i] < dist_a[i]:
            if ans < dist_a[i] - 1:
                ans = dist_a[i] - 1
    return ans

def main():
    n, u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)
    dist_t = dist(graph, u)
    dist_a = dist(graph, v)
    print(solve(dist_t, dist_a))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def bfs(u):
    d = [-1]*n
    stack = deque([u])
    d[u] = 0
    while len(stack)!=0:
        s = stack.popleft()
        for t in dist[s]:
            if d[t]==-1:
                d[t] = d[s]+1
                stack.append(t)
    return d

A = bfs(v)
T = bfs(u)
ans=0
for i in range(n):
    if A[i]>T[i]:
        ans = max(A[i]-1, ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(200000)
N,u,v=map(int,input().split())
s=[[]for i in range(N)]
for i in range(N-1):
    A,B=map(lambda x: int(x)-1,input().split())
    s[A].append(B)
    s[B].append(A)
a=[None]*N
t=[None]*N
t[u-1]=0
a[v-1]=0
def hu(n,c):
    for i in s[n]:
        if a[i]==None:
            a[i]=c
            hu(i,c+1)
hu(v-1,1)
A=0
k=a[u-1]
def hu2(n,c):
    global k
    for i in s[n]:
        if t[i]==None and c<a[i]:
            t[i]=c
            if k<a[i]:
                k=a[i]
            hu2(i,c+1)
hu2(u-1,1)
print(k-1)

Submission status: Accepted

Solution code:
from collections import *
import copy
N,v,u=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N-1)]
data=[[] for i in range(N+1)]
for A,B in AB:
    data[A].append(B)
    data[B].append(A)

stack=deque([[v,0]])
visited=set([v])
while stack:
    a,m=stack.popleft()
    for p in data[a]:
        if p==u:
            K=m+1
        if not p in visited:
            visited.add(p)
            stack.append([p,m+1])


for i in range(len(data)):
    if len(data[i])>1:
        visited=set([i])
        stack=deque([i])
        End=set()
        break

if N==2:
    print(0)
    exit()
while stack:
    a=stack.popleft()
    flag=0
    for p in data[a]:
        if not p in visited:
            visited.add(p)
            stack.append(p)
            flag=1
    if flag==0:
        End.add(a)

Uvisited=set([u])
Vvisited=set([])
if not v in End:
    Vvisited.add(v)
Ustack=deque([[u,0]])
Vstack=deque([[v,0]])
ans=[]
M=1

while Ustack:
    while Vstack:
        a,m=Vstack.popleft()
        if m==M:
            Vstack.append([a,m])
            break
        for p in data[a]:
            if not p in End:
                if p in Uvisited:
                    pass
                    #ans.append(m)
                elif not p in Vvisited:
                    Vvisited.add(p)
                    Vstack.append([p,m+1])
    while Ustack:
        a,m=Ustack.popleft()
        if m==M:

            Ustack.append([a,m])
            break
        for p in data[a]:

            if not p in Uvisited:
                if p in Vvisited:
                    ans.append(m+1)
                Uvisited.add(p)
                Ustack.append([p,m+1])
    M+=1
print(max(ans))

Submission status: Accepted

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


def expro(u):
    D=[0]*N
    D[u]=0
    S=[]
    S.append(u)
    L=[]
    q=0
    while(q<N):
        l=S[q]
        for i in range(len(G[l])):
            m=G[l][i]
            if(len(G[l])==1 and l!=u):
                L.append(l)
            if(D[m]==0 and m!=u):
                D[m]=D[l]+1
                S.append(m)
        #S.remove(l)
        q+=1
    return L,D
L,D = expro(u-1)
M,E = expro(v-1)
k=0
ans=0
#print(G)
#print(D)
#print(L)
for i in M:
    if D[i]<E[i]:
        if k<E[i]:
            k=E[i]
            ans=E[i]-1
print(ans)

Submission status: Accepted

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

def dfs(u):
  for v in g[u]:
    if checked[v]==1:
      continue
    else:
      checked[v]=1
      depth2[u]=max(depth2[u],dfs(v)+1)
  return depth2[u]

n,u,v=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
depth=[0]*(n+1)
checked=[0]*(n+1)
checked[v]=1
q=collections.deque()
q.append((v,0))
while 1:
  if len(q)==0:
    break
  tu,d=q.popleft()
  checked[tu]=1
  depth[tu]=d
  for tv in g[tu]:
    if checked[tv]!=1:
      checked[tv]=1
      q.append((tv,d+1))
moves=(depth[u]-1)//2
depth2=[0]*(n+1)
checked=[0]*(n+1)
checked[v]=1
dfs(v)
checked=[0]*(n+1)
checked[u]=1
q=collections.deque()
q.append((u,0))
cand=[]
while 1:
  if len(q)==0:
    break
  tu,d=q.popleft()
  if d==moves:
    cand.append(tu)
  checked[tu]=1
  for tv in g[tu]:
    if checked[tv]!=1:
      checked[tv]=1
      q.append((tv,d+1))
md=0
for i in cand:
  md=max(md,depth2[i])
if depth[u]%2!=0:
  ans=moves+md
else:
  ans=moves+md+1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque


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())
    edge[A - 1].append(B - 1)
    edge[B - 1].append(A - 1)

INF = 10 ** 6
lenA = [INF] * N
q = deque()
q.append((v, 0))
lenA[v] = 0
while len(q) > 0:
    p, step = q.popleft()
    for np in edge[p]:
        if lenA[np] == INF:
            lenA[np] = step + 1
            q.append((np, step + 1))


lenT = [INF] * N
q = deque()
q.append((u, 0))
lenT[u] = 0
ans = 0
while len(q) > 0:
    p, step = q.popleft()
    if len(edge[p]) == 1:
        ans = max(ans, step + (lenA[p] - step) - 1)
    for np in edge[p]:
        if lenT[np] == INF and lenA[np] > step + 1:
            lenT[np] = step + 1
            q.append((np, step + 1))

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque, Counter
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
INF = 10 ** 20

def dfs(graph, root, n):
    dista = [INF for i in range(n)]
    visited = [0 for i in range(n)]
    dista[root - 1] = 0
    visited[root - 1] = 1
    d = deque()
    for edge in graph[root - 1]:
        d.append(edge)
    while(d):
        cur, nxt = d.pop()
        if not visited[nxt]:
            dista[nxt] = dista[cur] + 1
            visited[nxt] = 1
            for edge in graph[nxt]:
                d.append(edge)

    return dista

def dfs2(graph, root, n, dista):
    distb = [INF for i in range(n)]
    visited = [0 for i in range(n)]
    visited[root - 1] = 1
    distb[root-1] = 0
    d = deque()
    ans = dista[root-1]
    dec = 0
    # print(dista, distb)
    for edge in graph[root-1]:
        d.append(edge)
    while(d):
        # print(d)
        # print(distb)
        cur, nxt = d.pop()
        if not visited[nxt]:
            if distb[cur] + 1 <= dista[nxt]:
                if distb[cur] + 1 == dista[nxt]:
                    dec = 1
                visited[nxt] = 1
                distb[nxt] = distb[cur] + 1
                for edge in graph[nxt]:
                    d.append(edge)
                if ans < dista[nxt]:
                    ans = dista[nxt]

            # print(ans, cur, nxt, visited)

    return ans

def main():
    n, u, v = getList()
    graph = [[] for i in range(n)]
    dista = [INF for i in range(n)]
    distb = [INF for i in range(n)]
    for i in range(n-1):
        a,b = getList()
        graph[a-1].append((a-1, b-1))
        graph[b - 1].append((b-1, a - 1))
    # print(graph)
    if n == 3:
        print(1)
        return
    dista = dfs(graph, v, n)
    # print(dista)
    print(dfs2(graph, u, n, dista) - 1)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, r0, g0 = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(n-1)]

connects = [[] for i in range(n+1)]
for e in edges:
    connects[e[0]].append(e[1])
    connects[e[1]].append(e[0])    

rL, gL = [-1]*(n+1), [-1]*(n+1)
rL[r0], gL[g0] = 0, 0

from collections import deque
rQ, gQ = deque([r0]), deque([g0])

for L, Q in [(rL, rQ), (gL, gQ)]:
    while Q:
        node = Q.popleft()
        for ni in connects[node]:
            if L[ni] == -1:
                L[ni] = L[node] + 1
                ### print((node, L[node]), (ni, L[ni]))
                Q.append(ni)

print(max(gL[i] for i in range(1, n+1) if rL[i] < gL[i]) - 1)

Submission status: Accepted

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

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

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

#print(data)

stack = [[u,u]]
taka_dis = [0] * N
while stack:
    x = stack.pop()
    #print(x)
    for y in data[x[1]]:
        if y == x[0]:
            continue
        else:
            stack.append([x[1],y])
            taka_dis[y] = taka_dis[x[1]] + 1
    #print(stack)

stack = [[v,v]]
aoki_dis = [0] * N
while stack:
    x = stack.pop()
    for y in data[x[1]]:
        if y == x[0]:
            continue
        else:
            stack.append([x[1],y])
            aoki_dis[y] = aoki_dis[x[1]] + 1
    
can = [0] * N

for i in range(N):
    if aoki_dis[i] - taka_dis[i] > 0:
        can[i] = aoki_dis[i]
    else:
        can[i] = 0
#print(aoki_dis)
#print(taka_dis)
#print(can)

print(max(can) -1 )

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

def make_adlist(n):
  adlist = [[] for _ in range(n)]
  for _ in range(n-1):
    a, b = map(lambda x:int(x)-1, input().split())
    adlist[a] += [b] 
    adlist[b] += [a]
  return adlist

def dfs(adlist, s, dist, d):
  for nxt in adlist[s]:
    if dist[nxt] == -1:
      dist[nxt] = d
      dfs(adlist, nxt, dist, d+1)

def main():
  n, u, v = map(int, input().split())
  u -= 1
  v -= 1
  adlist = make_adlist(n)
  t_dist = [-1]*n
  t_dist[u] = 0
  dfs(adlist, u, t_dist, 1)
  a_dist = [-1]*n
  a_dist[v] = 0
  dfs(adlist, v, a_dist, 1)
  ans = 0 
  for i in range(n):
    if t_dist[i] < a_dist[i]:
      ans = max(ans, a_dist[i]-1)
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

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

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

dist_v = dfs(v)
dist_u = dfs(u)
ans = 0
for rv, ru in zip(dist_v, dist_u):
    if rv > ru:
        ans = max(ans, rv-1)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,u,v = map(int,input().split())
l = [[]for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    l[a].append(b)
    l[b].append(a)
rl = [0 for i in range(n+1)]
d = deque()
d.append([l[u],u])
while len(d):
    l0,now = d.popleft()
    for i in l0:
        if i == u:
            continue
        elif rl[i] == 0:
            rl[i] = rl[now] + 1
            d.append([l[i],i])
rl2 = [0 for i in range(n+1)]
d = deque()
d.append([l[v],v])
while len(d):
    l0,now = d.popleft()
    for i in l0:
        if i == v:
            continue
        elif rl2[i] == 0:
            rl2[i] = rl2[now] + 1
            d.append([l[i],i])
dis = rl[v]
nl = []
for i in range(n+1):
    nl.append([rl2[i],i])
nl.sort(key=lambda x:x[0],reverse=True)
for i in range(n+1):
    if nl[i][0] > rl[nl[i][1]]:
        ans = nl[i][0]-1
        break
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n, u, v = list(map(int, input().split()))
a = [[] for _ in range(n+1)]
for _ in range(n-1):
  x, y = map(int, input().split())
  a[x].append(y)
  a[y].append(x)
  
def dis(a,v):
  d = [[1,0] for _ in range(n+1)]
  c = 1
  for i in a[v]:
    d[i][0] = 1
    d[i][1] = c
    c += 1
  b = deque(a[v])
  while b:
    x = b.pop()
    for i in a[x]:
      if d[i][1] == 0:
        d[i][0] = d[x][0] + 1
        d[i][1] = d[x][1]
        b.append(i)
  d[v] = [0,0]
  return d

du = dis(a,u)
dv = dis(a,v)
dis = max([dv[i][0] for i in range(n+1) if dv[i][1]==dv[u][1] and dv[i][0]>du[i][0]])
print(dis-1)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
N, u, v = map(int, input().split())
u -= 1
v -= 1
dic = defaultdict(list)
for i in range(N-1):
  a, b = map(int, input().split())
  dic[a-1] += [b-1]
  dic[b-1] += [a-1]
dist1 = [float('inf')]*N
dist2 = [float('inf')]*N
q1 = deque([u])
q2 = deque([v])
dist1[u] = 0
dist2[v] = 0
while q1:
  e = q1.popleft()
  for p in dic[e]:
    if dist1[p]>dist1[e]+1:
      dist1[p] = dist1[e]+1
      q1 += [p]

while q2:
  e = q2.popleft()
  for p in dic[e]:
    if dist2[p]>dist2[e]+1:
      dist2[p] = dist2[e]+1
      q2 += [p]

ans = -1
j = 0
for i in range(N):
  if ans<dist2[i]-1 and dist1[i]<dist2[i]:
    ans = dist2[i]-1
if u==v:
  ans = 0
print(ans)

Submission status: Accepted

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

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

    aq = deque([v-1])
    adist = [0 for _ in range(N)]
    edge = []
    go = [True for _ in range(N)]
    go[v-1] = False
    while aq:
        now = aq.pop()
        for fol in con[now]:
            if go[fol]:
                adist[fol] = adist[now] + 1
                go[fol] = False
                if con[fol] == [now]:
                    edge.append(fol)
                else:
                    aq.append(fol)
    
    tq = deque([u-1])
    tdist = [0 for _ in range(N)]
    _go = [True for _ in range(N)]
    _go[u-1] = False
    while tq:
        now = tq.pop()
        for fol in con[now]:
            if _go[fol]:
                tdist[fol] = tdist[now] + 1
                _go[fol] = False
                tq.append(fol)

    ans = 0
    for num in edge:
        a,t = adist[num],tdist[num]
        if a <= t:
            continue
        else:
            ans = max(ans,a-1)
                
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, U, V = lr()
edges = [[] for _ in range(N+1)] # 1-indexed
for _ in range(N-1):
    a, b = lr()
    edges[a].append(b)
    edges[b].append(a)

def dfs(v):
    dist = [-1] * (N+1)
    dist[v] = 0
    stack = [v]
    while stack:
        s = stack.pop()
        for x in edges[s]:
            if dist[x] != -1:
                continue
            dist[x] = dist[s] + 1
            stack.append(x)
    return dist

DU, DV = dfs(U), dfs(V)
answer = 0
for u, v in zip(DU[1:], DV[1:]):
    if v > u:
        x = v - 1
        if x > answer:
            answer = x

print(answer)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,ta,ao = inpl()
ta -= 1; ao -= 1
g = [[] for i in range(n)]
for i in range(n-1):
    a,b = inpl()
    g[a-1].append(b-1)
    g[b-1].append(a-1)
ta_dist = [None] * n
ta_dist[ta] = 0
ao_dist = [None] * n
ao_dist[ao] = 0
def ta_dfs(node):
    for v in g[node]:
        if ta_dist[v] != None: continue
        ta_dist[v] = ta_dist[node] + 1
        ta_dfs(v)
def ao_dfs(node):
    for v in g[node]:
        if ao_dist[v] != None: continue
        ao_dist[v] = ao_dist[node] + 1
        ao_dfs(v)
ao_dfs(ao)
ta_dfs(ta)
res = 0
for i in range(n):
    if ta_dist[i] > ao_dist[i]: continue
    res = max(res, ao_dist[i])
print(res-1)

Submission status: Accepted

Solution code:
n,u,v = map(int,input().split())
u -= 1
v -= 1
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  peer[a].append(b)
  peer[b].append(a)
rank = [10**6 for _ in range(n)]
seen = [0 for _ in range(n)]
pre = [10**6 for _ in range(n)]
pst = [[] for _ in range(n)]
seen[v] = 1
rank[v] = 0
now = [v]
while now:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if seen[y] == 0:
        seen[y] += 1
        rank[y] = rank[x] + 1
        now.append(y)
        pre[y] = x
        pst[x].append(y)
#print(rank)
back = (rank[u]-1) // 2
tar = u
for _ in range(back):
  tar = pre[tar]
depth = -1
now = [tar]
while now:
  depth += 1
  last = now
  now = []
  for x in last:
    now += pst[x]
#print(tar,depth,last)
if rank[u] % 2 == 1:
  print(back + depth)
else:
  print(back + depth + 1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque

N,u,v=map(int, sys.stdin.readline().split())

al=[ [] for i in range(N+1) ]	#隣接リスト

for _ in range(N-1):
    a,b=map(int, sys.stdin.readline().split())
    al[a].append(b)
    al[b].append(a)

dist_t=[ 0 for _ in range(N+1) ] #高橋君のスタート地点からの各頂点までの距離
dist_a=[ 0 for _ in range(N+1) ] #青木君のスタート地点からの各頂点までの距離

#print "al :: ",al

#高橋君のスタート地点からの各頂点までの距離
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(u)
Visit[u]=1

while q:
    fro=q.popleft()
    for to in al[fro]:
        if Visit[to]==0:
            Visit[to]=1 #訪問済みに1をセット
            dist_t[to]=dist_t[fro]+1 #距離を計算
            q.append(to)

#print "dist_t :: ",dist_t

#青木君のスタート地点からの各頂点までの距離
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(v)
Visit[v]=1

while q:
    fro=q.popleft()
    for to in al[fro]:
        if Visit[to]==0:
            Visit[to]=1 #訪問済みに1をセット
            dist_a[to]=dist_a[fro]+1 #距離を計算
            q.append(to)

#print "dist_a :: ",dist_a

ans=0
max_a=0
for t,a in zip(dist_t,dist_a):
    if t<a:
        ans=max(ans,a)

print ans-1

Submission status: Accepted

Solution code:
n,v,u = map(int,input().split())
dist_taka = [100000 for i in range(n)]
dist_aoki = [100000 for i in range(n)]
dist_taka[v-1] = 0
dist_aoki[u-1] = 0
M = [[] for i in range(n)]
for i in range(n-1):
  a,b = map(int,input().split())
  M[a-1].append(b-1)
  M[b-1].append(a-1)
stack = []
check = [0]*n
for i in range(len(M[v-1])):
  stack.append([v-1,M[v-1][i]])
while len(stack) != 0:
  cur = stack.pop()
  check[cur[0]] = 1
  dist_taka[cur[1]] = dist_taka[cur[0]]+1
  for i in range(len(M[cur[1]])):
    if check[M[cur[1]][i]] == 0:
      stack.append([cur[1],M[cur[1]][i]])

check = [0]*n
for i in range(len(M[u-1])):
  stack.append([u-1,M[u-1][i]])
while len(stack) != 0:
  cur = stack.pop()
  check[cur[0]] = 1
  dist_aoki[cur[1]] = dist_aoki[cur[0]]+1
  for i in range(len(M[cur[1]])):
    if check[M[cur[1]][i]] == 0:
      stack.append([cur[1],M[cur[1]][i]])
ans = 0
for i in range(n):
  if dist_taka[i] < dist_aoki[i]:
    ans = max(ans,dist_aoki[i])
print(max(0,ans-1))

Submission status: Accepted

Solution code:
n,v,u = map(int,input().split())
dist_taka = [100000 for i in range(n)]
dist_aoki = [100000 for i in range(n)]
dist_taka[v-1] = 0
dist_aoki[u-1] = 0
M = [[] for i in range(n)]
for i in range(n-1):
  a,b = map(int,input().split())
  M[a-1].append(b-1)
  M[b-1].append(a-1)
stack = []
check = [0]*n
for i in range(len(M[v-1])):
  stack.append([v-1,M[v-1][i]])
while len(stack) != 0:
  cur = stack.pop()
  check[cur[0]] = 1
  dist_taka[cur[1]] = dist_taka[cur[0]]+1
  for i in range(len(M[cur[1]])):
    if check[M[cur[1]][i]] == 0:
      stack.append([cur[1],M[cur[1]][i]])

check = [0]*n
for i in range(len(M[u-1])):
  stack.append([u-1,M[u-1][i]])
while len(stack) != 0:
  cur = stack.pop()
  check[cur[0]] = 1
  dist_aoki[cur[1]] = dist_aoki[cur[0]]+1
  for i in range(len(M[cur[1]])):
    if check[M[cur[1]][i]] == 0:
      stack.append([cur[1],M[cur[1]][i]])
ans = 0
for i in range(n):
  if dist_taka[i] < dist_aoki[i]:
    ans = max(ans,dist_aoki[i])
print(max(0,ans-1))

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[1:]


print(max(j for i, j in zip(dfs(u), dfs(v)) if i <= j) - 1)