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 sys,collections,math,random;sys.setrecursionlimit(10**7)
from fractions import gcd
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

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

md_u, md_v = [-1]*n, [-1]*n
qs = [[u-1,0]], [[v-1,0]]
for md,q in zip([md_u,md_v],qs):
    while q:
        n,d = q.pop()
        md[n] = d
        for e in tree[n]:
            if md[e] == -1:
                q.append([e,d+1])
#print(md_u,md_v)
ans = -2
for a,b in zip(md_u,md_v):
    if a < b:
        ans = max(b,ans)
print(ans-1)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

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

        return D[1:]

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

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

main()

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

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

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

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

print(max_dist - 1)

Submission status: Accepted

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

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

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

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

print(max(0, ans-1))

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

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

    return D[1:]

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

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

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

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

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

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

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

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

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

    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

    # 両者について、最初にいる場所から他の頂点への移動回数を求める
    dist_aoki = [0] * N
    bfs(tree, dist_aoki, V - 1)
    dist_takahashi = [0] * N
    bfs(tree, dist_takahashi, U - 1)

    ans = 0
    for aoki, takahashi in zip(dist_aoki, dist_takahashi):
        # 注目した頂点 v には高橋くんの方が先に到達できる
        if aoki > takahashi:
            # 青木くんは v の親で高橋くんを捕まえることになるので、
            # v までの距離 - 1 が解となりうる
            ans = max(ans, aoki - 1)
    return ans

print(f_playing_tag_on_tree())

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

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

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

print(ma - 1)

Submission status: Accepted

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

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

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


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

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

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

Submission status: Accepted

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

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

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

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(700000)

from collections import deque

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

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

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

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

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

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

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

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

# 追われる側、追う側それぞれからの最短距離
res1 = dfs(x)
res2 = dfs(y)

mx = -INF
for i in range(N):
    # 追われる側のが先に着く場所は逃げ込む候補になりうる
    if res1[i] <= res2[i]:
        # その中で一番追う側から遠い場所
        mx = max(mx, res2[i])
# 最終的に1歩手前で捕まるので-1
print(mx - 1)

Submission status: Accepted

Solution code:
#メモ，葉の一つ手前でぶつかるはず？
#uの位置を無視していたけど，例えばuが葉，vがその一つ手前にいる場合に他の葉の深さが関係なくなる，やはり根付きとかにする？
import heapq
class Dijkstra():
    """
    ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
    ・負のコストがない場合のみ
    ・計算量はO(E log|V|)　
    ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
    """
    
    #最短のpathをたす
    
    
    class Edge():
        #重み付き有向辺
        
        def __init__(self, _to, _cost):
            self.to =_to
            self.cost = _cost
    
    def __init__(self, V):
        #引数Vは頂点数
        self.G = [[] for _ in range(V)] #隣接リストG[u][i]が頂点uのi番目の辺
        self. _E = 0 #辺の数
        self._V = V #頂点数
    
    #proparty - 辺の数
    def E(self):
        return self._E
    
    #proparty - 頂点数
    def V(self):
        return self._V
    
    def add(self, _from, _to, _cost):
        #2頂点と辺のコストを追加
        self.G[_from].append(self.Edge(_to,_cost))
        self._E +=1
        
    def add2(self, _from, _to, _cost):
        #2頂点と辺のコスト（無向）を追加
        self.G[_from].append(self.Edge(_to, _cost))
        self.G[_to].append(self.Edge(_from, _cost))
        self._E +=1
        
    def shortest_path(self,s):
        #始点sから頂点iまでの最短経路長のリストを返す
        
        que = [] #priority queue
        d = [float("inf")] * self.V()
        prev = [None]*self.V() #prev[j]は，sからjへ最短経路で行くときのjの一つ前の場所
        d[s] = 0
        heapq.heappush(que,(0,s)) #始点の距離と頂点番号をヒープに追加
        
        while len(que)!=0:
            #キューに格納されてある中で一番コストが小さい頂点を取り出す
            cost,v = heapq.heappop(que)
            
            #キューに格納された最短経路長候補がdの距離よりも大きい場合に処理をスキップ
            if d[v] < cost:
                continue
                
            #頂点vに隣接する各頂点iに対して，vを経由した場合の距離を計算して，これがd[i]よりも小さい場合に更新
            for i in range(len(self.G[v])):
                e = self.G[v][i] #vのi個目の隣接辺
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost #更新
                    prev[e.to] = v
                    heapq.heappush(que,(d[e.to],e.to)) #queに新たな最短経路長候補を追加
                    
        return d
#ここまでダイクストラ


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

#a,bなどは1からスタートするので1引いておく
for i in range(N-1):
    a,b  = map(int, input().split())
    list[a-1].append(b-1)
    list[b-1].append(a-1)
    djk.add2(a-1,b-1,1)


#青木くんの位置(v-1)から各葉までの距離を出す
d_v=djk.shortest_path(v-1)
d_u=djk.shortest_path(u-1)

#青木くんより高橋くんが先に到達できる葉でなければならない？
path_to_leaf_v=[]

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


#上記の中で，一番深い葉に高橋くんが逃げ込む
ans = max(path_to_leaf_v)-1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

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

main()

Submission status: Accepted

Solution code:
import sys

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

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


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


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

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

print(answer)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

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

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

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 i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)


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

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

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

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

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

print(max_d - 1)

Submission status: Accepted

Solution code:
from collections import defaultdict


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

edges = defaultdict(list)

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

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


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

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

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


dfs(aoks, edges, aoki_map)


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

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


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

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

res = max(ans)

print(res-1)

Submission status: Accepted

Solution code:
import heapq;

n, u, v = [int(v) for v in input().split()]

vert = []

for i in range(n):
    vert.append([])

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

taka = u-1
aoki = v-1

if taka == aoki:
    print(0)
    exit()

q = [(0, aoki)]
aoki_dist = [-1] * n
aoki_dist[aoki] = 0

index = 0
while index < len(q):
    c0, i = q[index]
    c = c0 + 1
    for l in vert[i]:
        if aoki_dist[l] >= 0:
            continue
        aoki_dist[l] = c
        q.append((c, l))
    index += 1

q = [(0, taka)]
max_dist = aoki_dist[taka]
aoki_dist[taka] = -1

index = 0
while index < len(q):
    c0, i = q[index]
    c = c0 + 1
    for l in vert[i]:
        if aoki_dist[l] < 0:
            continue
        if c >= aoki_dist[l]:
            continue
        if max_dist < aoki_dist[l]:
            max_dist = aoki_dist[l]
        aoki_dist[l] = -1
        q.append((c, l))
    index += 1

print(max_dist - 1)

Submission status: Accepted

Solution code:
import heapq;

n, u, v = [int(v) for v in input().split()]

vert = []

for i in range(n):
    vert.append([])

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

taka = u-1
aoki = v-1

if taka == aoki:
    print(0)
    exit()

def bfs(begin):
    q = [(0, begin)]
    dist = [-1] * n
    dist[begin] = 0

    index = 0
    while index < len(q):
        c0, i = q[index]
        c = c0 + 1
        for l in vert[i]:
            if dist[l] >= 0:
                continue
            dist[l] = c
            q.append((c, l))
        index += 1
    return dist

aoki_dist = bfs(aoki)
taka_dist = bfs(taka)

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

print(ans)

Submission status: Accepted

Solution code:
from queue import Queue

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

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

inf = 1<<30
du = [inf]*N
dv = [inf]*N
du[u-1] = 0
dv[v-1] = 0

visited = [False]*N
visited[u-1] = True

que = Queue()
que.put(u-1)
while not(que.empty()):
    nxt = que.get()    
    for nv in edge[nxt]:
        if not visited[nv]:
            que.put(nv)
            du[nv] = du[nxt]+1
            visited[nv] = True
visited = [False]*N
visited[v-1] = True
del que
que = Queue()
que.put(v-1)
while not(que.empty()):
    nxt = que.get()    
    for nv in edge[nxt]:
        if not visited[nv]:
            que.put(nv)
            dv[nv] = dv[nxt]+1
            visited[nv] = True

idx=0
maxd = 0
for i in range(N):
    if du[i]<dv[i]:
        if maxd<dv[i]:
            maxd=dv[i]
            idx = i

ans = dv[idx]-1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

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

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

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

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

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

Submission status: Accepted

Solution code:
n,u,v = map(int,input().split())
u-=1
v-=1
# e={i:[] for i in range(1,n+1)}
# for i in range(n):
#     a,b=map(int,input().split)
#     e[a].append(b)
#     e[b].append(a)
roots=[ [] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    roots[a-1]+=[b-1]
    roots[b-1]+=[a-1]
dist=[-1]*n
stack=[]
stack.append(u)
dist[u]=0
while stack:
    label=stack.pop(-1)
    for i in roots[label]:
        if dist[i]==-1:
            dist[i]=dist[label]+1
            stack+=[i]
dist1=dist
dist=[-1]*n
stack=[]
stack.append(v)
dist[v]=0
while stack:
    label=stack.pop(-1)
    for i in roots[label]:
        if dist[i]==-1:
            dist[i]=dist[label]+1
            stack+=[i]
dist2=dist
goal = -1
d = 0
for i in range(n):
    if dist1[i]<dist2[i] and d < dist2[i]:
        d = dist2[i]
        goal = i
else:
    print(dist2[goal]-1)

Submission status: Accepted

Solution code:
import os
import sys

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

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

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

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

# 深い方に逃げるべき
# 子どものうち一番深い場所の深さ
children_depths = [0] * N
parents = [None] * N

stack = [(U, None)]
vs = []
while stack:
    v, parent = stack.pop()
    parents[v] = parent
    vs.append(v)
    for u in graph[v]:
        if u == parent:
            continue
        stack.append((u, v))
vs.reverse()
for v in vs:
    if parents[v] is not None:
        children_depths[parents[v]] = max(children_depths[parents[v]], children_depths[v] + 1)

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

# 何回親側に上がるか
p_cnt = 0
v = V
ans = 0
while dist > 0:
    ans = max(ans, dist - 1 + children_depths[v] + p_cnt)
    v = parents[v]
    p_cnt += 1
    dist -= 2
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

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

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

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

mx = -INF
for i in range(N):
    if memo[i] >= memo2[i]:
        mx = max(mx, memo[i])
print(mx - 1)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 5)


def dfs(v, parent, depth):
    parents[v] = parent
    self_depths[v] = depth
    sd = 0
    for u in links[v]:
        if u == parent:
            continue
        res = dfs(u, v, depth + 1)
        sd = max(sd, res + 1)

    subtree_depths[v] = sd
    return sd


def solve(u):
    catch = self_depths[u] // 2
    while self_depths[parents[u]] > catch:
        u = parents[u]
    return self_depths[u] + subtree_depths[u] - 1


n, u, v = map(int, input().split())
u -= 1
v -= 1
links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)

parents = [-1] * n
self_depths = [0] * n
subtree_depths = [0] * n
dfs(v, -1, 0)
print(solve(u))

Submission status: Accepted

Solution code:
n,x,y=map(int,input().split())
s=[[]for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    s[a].append(b)
    s[b].append(a)
p=[float("INF")for i in range(n+1)]
q=[float("INF")for i in range(n+1)]
p[x]=0
q[y]=0
c=set([x])
while c:
    d=set()
    for i in c:
        for j in s[i]:
            if p[j]>p[i]+1:
                p[j]=p[i]+1
                d.add(j)
    c=d
c=set([y])
while c:
    d=set()
    for i in c:
        for j in s[i]:
            if q[j]>q[i]+1:
                q[j]=q[i]+1
                d.add(j)
    c=d
a=0
for i in range(1,n+1):
    if p[i]<q[i]:
        a=max(a,q[i]-1)
print(a)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
n,u,v=map(int,input().split())
E=[[] for _ in range(n+1)]
for _ in range(n-1):
    a,b=map(int,input().split())
    E[a].append(b)
    E[b].append(a)
depth=[-1]*(n+1)
dis=[-1]*(n+1)
def dsf_1(p,d):
    depth[p]=d
    for c in E[p]:
        if depth[c]==-1:
            dsf_1(c,d+1)
dsf_1(v,0)
def dsf_2(p,d):
    dis[p]=d
    for c in E[p]:
        if dis[c]==-1:
            dsf_2(c,d+1)
dsf_2(u,0)
ans=0
for i in range(1,n+1):
    if len(E[i])==1 and i!=v:
        if dis[i]<depth[i]:
           ans=max(ans,depth[i]-1)
print(ans)