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 copy
from collections import deque

n, st, sa = map(int,input().split())
st -= 1
sa -= 1

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

visited = [False] * n
visited[st] = True
d = deque()
d.append([st, 0])
tx = {}
if len(e[st]) == 1:
    tx[st] = 0
cnt = 0
while d:
    f, cnt = d.popleft()
    flg = True
    for t in e[f]:
        if not visited[t]:
            flg = False
            d.append([t, cnt+1])
            visited[t] = True
    if flg:
        tx[f] = cnt

visited = [False] * n
visited[sa] = True
d = deque()
d.append([sa, 0])
ax = {}
if len(e[sa]) == 1:
    ax[sa] = 0
cnt = 0
while d:
    f, cnt = d.popleft()
    flg = True
    for t in e[f]:
        if not visited[t]:
            flg = False
            d.append([t, cnt+1])
            visited[t] = True
    if flg:
        ax[f] = cnt

ax = sorted(ax.items(), key=lambda x:x[1], reverse=True)
for i in range(len(ax)):
    x, d = ax[i][0], ax[i][1]
    if d > tx[x]:
        ans = d - 1
        break

print(ans)

Submission status: Accepted

Solution code:
import os
import sys
import numpy as np

def solve(N, U, V, AB):
    G = [[0]*0 for _ in range(N+1)]
    for idx_ab in range(len(AB)):
        a, b = AB[idx_ab]
        G[a].append(b)
        G[b].append(a)
    P1 = np.zeros(N+1, dtype=np.int64)
    def dfs1(u):
        st = [u]
        while st:
            v = st.pop()
            p = P1[v]
            for u in G[v]:
                if p != u:
                    st.append(u)
                    P1[u] = v
    dfs1(U)
    path_u2v = [U]
    v = V
    while v != U:
        v = P1[v]
        path_u2v.append(v)
    path_u2v.reverse()
    l = len(path_u2v)
    half = (l-2) // 2
    c = path_u2v[half]
    ng = path_u2v[half+1]
    Depth = np.zeros(N+1, dtype=np.int64)
    def dfs2(c):
        st = [c]
        P = np.zeros(N+1, dtype=np.int64)
        while st:
            v = st.pop()
            p = P[v]
            d = Depth[v]
            for u in G[v]:
                if p != u and u != ng:
                    st.append(u)
                    P[u] = v
                    Depth[u] = d + 1
    dfs2(c)
    c_ = path_u2v[l-1-half]
    v = c_
    while v != c:
        Depth[v] = 0
        v = P1[v]
    d = l%2
    ans = max(Depth) + half + d
    return ans


# >>> numba compile >>>
numba_config = [
    [solve, "i8(i8,i8,i8,i8[:,:])"],
]
if sys.argv[-1] == "ONLINE_JUDGE":
    from numba import njit
    from numba.pycc import CC
    cc = CC("my_module")
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature)(func)
        cc.export(func.__name__, signature)(func)
    cc.compile()
    exit()
elif os.name == "posix":
    exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
else:
    from numba import njit
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature, cache=True)(func)
    print("compiled!", file=sys.stderr)
# <<< numba compile <<<


def main():
    N, u, v = map(int, input().split())
    if N==2:
        print(0)
        return
    AB = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(N-1, 2)
    ans = solve(N, u, v, AB)
    print(ans)

main()

Submission status: Accepted

Solution code:
import os
import sys
import numpy as np

def solve(N, U, V, AB):
    G = [[] for _ in range(N+1)]
    for ab in AB:
        a, b = ab
        G[a].append(b)
        G[b].append(a)
    P1 = np.zeros(N+1, dtype=np.int64)
    def dfs1(u):
        st = [u]
        while st:
            v = st.pop()
            p = P1[v]
            for u in G[v]:
                if p != u:
                    st.append(u)
                    P1[u] = v
    dfs1(U)
    path_u2v = [U]
    v = V
    while v != U:
        v = P1[v]
        path_u2v.append(v)
    path_u2v.reverse()
    l = len(path_u2v)
    half = (l-2) // 2
    c = path_u2v[half]
    ng = path_u2v[half+1]
    Depth = np.zeros(N+1, dtype=np.int64)
    def dfs2(c):
        st = [c]
        P = np.zeros(N+1, dtype=np.int64)
        while st:
            v = st.pop()
            p = P[v]
            d = Depth[v]
            for u in G[v]:
                if p != u and u != ng:
                    st.append(u)
                    P[u] = v
                    Depth[u] = d + 1
    dfs2(c)
    c_ = path_u2v[l-1-half]
    v = c_
    while v != c:
        Depth[v] = 0
        v = P1[v]
    d = l%2
    ans = max(Depth) + half + d
    return ans

def main():
    N, u, v = map(int, input().split())
    if N==2:
        print(0)
        return
    AB = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(N-1, 2)
    ans = solve(N, u, v, AB)
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def bfs(N, v0, edge):

    search = [-1] * N
    search[v0] = 0
    q = deque()
    q.append(v0)

    while q:
        v = q.popleft()
        for nv in edge[v]:
            if search[nv] == -1:
                q.append(nv)
                search[nv] = search[v] + 1

    return search


def bfs2(N, v0, edge, dis):

    q = deque()
    q.append(v0)

    max_dis = dis[v0]
    while q:
        v = q.popleft()
        for nv in edge[v]:
            if dis[v] < dis[nv]:
                q.append(nv)
                max_dis = max(max_dis, dis[nv])

    return max_dis


def main():

    N, taka, aoki = in_nn()
    taka, aoki = taka - 1, aoki - 1

    edge = [[] for _ in range(N)]
    for i in range(N - 1):
        x, y = in_nn()
        x, y = x - 1, y - 1
        edge[x].append(y)
        edge[y].append(x)

    dis = bfs(N, aoki, edge)

    if dis[taka] > 2:
        x = (dis[taka] + 1) // 2 - 1
        for _ in range(x):
            for v in edge[taka]:
                if dis[v] < dis[taka]:
                    taka = v
                    break

    ans = bfs2(N, taka, edge, dis) - 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

takyori = [-1 for i in range(n)]
takyori[u] = 0
d = deque()
d.append(u)
while d:
    now = d.popleft()
    for i in route[now]:
        if takyori[i] == -1:
            takyori[i] = takyori[now] + 1
            d.append(i)

aokyori = [-1 for i in range(n)]
aokyori[v] = 0
d = deque()
d.append(v)
while d:
    now = d.popleft()
    for i in route[now]:
        if aokyori[i] == -1:
            aokyori[i] = aokyori[now] + 1
            d.append(i)
ans = 0
for i in range(n):
    if takyori[i] <= aokyori[i]:
        ans = max(ans,aokyori[i]-1)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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


def bfs(v):
  visited = [False] * N
  q = deque([v])
  span = [-1] * N

  s = 0
  while q:
    l = len(q)
    newq = deque([])

    for _ in range(l):
      node = q.popleft()
      visited[node] = True
      span[node] = s

      for nei in adj[node]:
        if not visited[nei]:
          newq.append(nei)

    q = newq
    s += 1

  return span

t = bfs(u)
a = bfs(v)

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

print(ans)

Submission status: Accepted

Solution code:

from collections import deque

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

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


def bfs(s):
    INF = 10 ** 9 + 7
    d = [INF] * (N + 1)
    d[s] = 0
    q = deque([s])
    while q:
        u = q.popleft()
        for v in graph[u]:
            if d[v] > d[u] + 1:
                d[v] = d[u] + 1
                q.append(v)

    return d


to = bfs(u)
ot = bfs(v)

ans = 0
for i, (a, b) in enumerate(zip(to, ot)):
    if a < b:
        ans = max(ans, b)
print(ans - 1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def bfs(start):
        dist = [f_inf] * n
        dist[start] = 0
        que = deque([start])
        while que:
            v = que.popleft()
            for u in edge[v]:
                if dist[u] == f_inf:
                    dist[u] = dist[v] + 1
                    que.append(u)
        return dist

    n, u, v = map(int, input().split())
    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)

    distT = bfs(u - 1)
    distA = bfs(v - 1)

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def bfs(start):
        dist = [f_inf] * n
        dist[start] = 0
        que = deque([start])
        while que:
            v = que.popleft()
            for u in edge[v]:
                if dist[u] == f_inf:
                    dist[u] = dist[v] + 1
                    que.append(u)
        return dist

    n, u, v = map(int, input().split())
    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)

    distA = bfs(u - 1)
    distT = bfs(v - 1)

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N, U, V = getNM()
U -= 1
V -= 1
# 高橋君はできるだけ遅くゲームが終了するように移動し、青木君はできるだけ早くゲームが終了するように移動します。
# 高橋君は逃げ、青木君は追いかける
dist = [[] for i in range(N)]
for i in range(N - 1):
    a, b = getNM()
    dist[a - 1].append(b - 1)
    dist[b - 1].append(a - 1)

taka_d = [-1] * N
aoki_d = [-1] * N

taka_d[U] = 0
pos = deque([[U, taka_d[U]]])
while len(pos) > 0:
    u, dis = pos.popleft()
    for i in dist[u]:
        if taka_d[i] == -1:
            taka_d[i] = dis + 1
            pos.append([i, taka_d[i]])

aoki_d[V] = 0
pos = deque([[V, aoki_d[V]]])
while len(pos) > 0:
    u, dis = pos.popleft()
    for i in dist[u]:
        if aoki_d[i] == -1:
            aoki_d[i] = dis + 1
            pos.append([i, aoki_d[i]])

ans = 0
for a, b in zip(taka_d, aoki_d):
    if a < b:
        ans = max(ans, b - 1)
print(ans)

Submission status: Accepted

Solution code:
def resolve():
    N, u, v = list(map(int, input().split()))
    u, v = u-1, v-1
    adjs = [ [] for _ in range(N)]
    for _ in range(N-1):
        a, b = list(map(lambda x: int(x)-1, input().split()))
        adjs[a].append(b)
        adjs[b].append(a)
    dist_from_u = [float("inf") for _ in range(N)]
    dist_from_u[u] = 0
    import collections
    q = collections.deque([u])
    while q:
        node = q.pop()
        for adj in adjs[node]:
            if dist_from_u[adj] > dist_from_u[node]+1:
                dist_from_u[adj] = dist_from_u[node]+1
                q.appendleft(adj)
    #print(dist_from_u)
    dist_from_v = [float("inf") for _ in range(N)]
    dist_from_v[v] = 0
    import collections
    q = collections.deque([v])
    while q:
        node = q.pop()
        for adj in adjs[node]:
            if dist_from_v[adj] > dist_from_v[node]+1:
                dist_from_v[adj] = dist_from_v[node]+1
                q.appendleft(adj)
    #print(dist_from_v)
    length = 0
    for i in range(N):
        if dist_from_u[i] < dist_from_v[i] and length < dist_from_v[i]:
            length = dist_from_v[i]
    print(length-1)
    
if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from collections import deque


def nearlist(N, LIST):  # 隣接リスト
    NEAR = [set() for _ in range(N)]
    for a, b in LIST:
        NEAR[a - 1].add(b - 1)
        NEAR[b - 1].add(a - 1)
    return NEAR


def bfs(NEAR, S, N):  # 幅優先探索  # キュー
    dist = [-1 for _ in range(N)]  # 前処理
    dist[S] = 0
    que, frag = deque([S]), set([S])

    while len(que) > 0:
        q = que.popleft()
        for i in NEAR[q]:  # 移動先の候補
            if i in frag:  # 処理済みか否か
                continue
            dist[i] = dist[q] + 1
            que.append(i), frag.add(i)
    return dist


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

near = nearlist(n, ab)
tkdist, akdist = bfs(near, u - 1, n), bfs(near, v - 1, n)

node = [i for i in range(n) if tkdist[i] <= akdist[i]]
ans = max(akdist[i] for i in node)
print(ans - 1)

Submission status: Accepted

Solution code:
from collections import deque


def nearlist(N, LIST):  # 隣接リスト
    NEAR = [set() for _ in range(N)]
    for a, b in LIST:
        NEAR[a - 1].add(b - 1)
        NEAR[b - 1].add(a - 1)
    return NEAR


def bfs(NEAR, S, N):  # 幅優先探索  # キュー
    dist = [-1 for _ in range(N)]  # 前処理
    dist[S] = 0
    que, frag = deque([S]), set([S])

    while len(que) > 0:
        q = que.popleft()
        for i in NEAR[q]:  # 移動先の候補
            if i in frag:  # 処理済みか否か
                continue
            dist[i] = dist[q] + 1
            que.append(i), frag.add(i)
    return dist


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

near = nearlist(n, ab)
tkdist, akdist = bfs(near, u - 1, n), bfs(near, v - 1, n)

node = [i for i in range(n) if tkdist[i] <= akdist[i]]
ans = max((akdist[i], i) for i in node)
print(ans[0] - 1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
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())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
d1 = [None]*n
d2 = [None]*n
def dfs(node, d, p_node=-1):
    for c_node in graph[node]:
        if c_node==p_node:
            continue
        d[c_node] = d[node] + 1
        dfs(c_node, d, node)
d1[u] = 0
d2[v] = 0
dfs(u, d1)
dfs(v, d2)
ans = 0
for i, j in zip(d1, d2):
    if i<j:
        ans = max(ans, j-1)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
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())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
pre = [None]*n
def dfs(node, p_node=-1):
    for c_node in graph[node]:
        if c_node==p_node:
            continue
        pre[c_node] = node
        dfs(c_node, node)
dfs(u)
path = [v]
now = v
while now!=u:
    now = pre[now]
    path.append(now)
s1 = path[len(path)//2]
p1 = path[len(path)//2-1]
def dfs2(node, depth, p_node):
    mx = depth
    for c_node in graph[node]:
        if c_node==p_node:
            continue
        mx = max(mx, dfs2(c_node, depth+1, node))
    return mx
print(dfs2(s1, 0, p1)+len(path)//2-1)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys


sys.setrecursionlimit(10 ** 6)


def depth(adj, node, parent=None):
    ret = 0
    for child in adj[node]:
        if child == parent:
            continue
        d = depth(adj, child, node) + 1
        ret = max(ret, d)
    return ret


def main():
    N, U, V = list(map(int, input().split(' ')))
    U -= 1
    V -= 1
    adj = defaultdict(list)
    for _ in range(N - 1):
        A, B = list(map(lambda x: int(x) - 1, input().split(' ')))
        adj[A].append(B)
        adj[B].append(A)

    path = [-1] * N

    def find_path_on_tree(to_node, node, parent=None, d=0):
        if node == to_node:
            path[d] = node
            return True
        for child in adj[node]:
            if child == parent:
                continue
            if not find_path_on_tree(to_node, child, node, d + 1):
                continue
            path[d] = node
            return True
        return False

    find_path_on_tree(U, V)  # to U from V
    path = [node for node in path if node != -1]
    dist = len(path) - 1
    partial_depth = depth(adj, path[(dist // 2) + 1], path[dist // 2])
    print(partial_depth + (dist // 2))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, u, v = map(int, input().split())
edges = [[] for i 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)

aolevel = [-1] * n
aolevel[v - 1] = 0
q = [v - 1]
while len(q) > 0:
    i = q.pop(0)
    for j in edges[i]:
        if aolevel[j] < 0:
            aolevel[j] = aolevel[i] + 1
            q.append(j)

ret = 0
takalevel = [-1] * n
takalevel[u - 1] = 0
q = [u - 1]
while len(q) > 0:
    i = q.pop(0)
    ret = max(ret, aolevel[i] - 1)
    if takalevel[i] < aolevel[i]:
        for j in edges[i]:
            if takalevel[j] < 0:
                takalevel[j] = takalevel[i] + 1
                q.append(j)

print(ret)

Submission status: Accepted

Solution code:
from collections import deque,defaultdict
import copy

def main():
    from collections import defaultdict
    import copy 
    n,u,v = map(int,input().split())
    u -= 1
    v -= 1
    graph = defaultdict(deque)
    for _ in range(n-1):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)

    depth = dfs(graph,u,n)
    # print(depth)
    depth2 = dfs(graph,v,n)
    # print(depth2)
    ans = 0
    ans2 = 10**6
    for i,j in zip(depth,depth2):
        if i < j:
            ans = max(j,ans)
        # elif i == j:
        #     ans2 = min(j,ans2)

    print(ans-1)

def dfs(G,s,n):
    stack = deque([s])
    graph = copy.deepcopy(G)
    depth = [None] * n
    depth[s] = 0
    while stack:
        u = stack[-1]
        if graph[u]:
            v = graph[u].popleft()
            if depth[v] == None:
                depth[v] = depth[u] + 1
                stack.append(v)

        else:
            stack.pop()

    return depth
    

main()

Submission status: Accepted

Solution code:
import sys 
sys.setrecursionlimit(10**6)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N,u,v = map(int,readline().split())
AB = [[] for _ in range(N+1)]
for _ in range(N-1):
    a,b = map(int,readline().split())
    AB[a].append(b)
    AB[b].append(a)
    
tdist = [0]*(N+1)
adist = [0]*(N+1)

def tdfs(x,pre):
    for to in AB[x]: 
        if to == pre:
            continue
        tdist[to] = tdist[x]+1
        tdfs(to,x)

def adfs(x,pre):
    for to in AB[x]: 
        if to == pre:
            continue
        adist[to] = adist[x]+1
        adfs(to,x)

tdfs(u,-1)
adfs(v,-1)

ans = 0
for i in range(1,N+1):
    if tdist[i] < adist[i]:
        k = adist[i] - tdist[i]
        ans = max(ans,tdist[i] + k-1)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n, a, b = map(int, input().split())
D = [[0]*2 for _ in range(101010)]
E = [[] for _ in range(n)]


def dfs(cur, pre, d, id):
    D[cur][id] = d
    for nv in E[cur]:
        if nv != pre:
            dfs(nv, cur, d+1, id)


a -= 1
b -= 1
for i in range(n-1):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    E[x].append(y)
    E[y].append(x)
dfs(a, a, 0, 0)
dfs(b, b, 0, 1)
max_d = 0
for i in range(n):
    if D[i][0] < D[i][1]:
        max_d = max(max_d, D[i][1]-1)
print(max_d)

Submission status: Accepted

Solution code:
import sys

def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N,u,v = LI()
Graph = [[] for i in range(N+1)]

for i in range(N-1):
    a,b = LI()
    Graph[a].append(b)
    Graph[b].append(a)

from collections import deque

q1 = deque([u])
distance1 = [-1]*(N+1)  # uから各頂点への最短距離
distance1[u] = 0

# bfs

while q1:
    n = q1.pop()
    for d in Graph[n]:
        if distance1[d] != -1:
            continue
        else:
            distance1[d] = distance1[n]+1
            q1.appendleft(d)

q2 = deque([v])
distance2 = [-1]*(N+1)  # vから各頂点への最短距離
distance2[v] = 0

# bfs

while q2:
    n = q2.pop()
    for d in Graph[n]:
        if distance2[d] != -1:
            continue
        else:
            distance2[d] = distance2[n]+1
            q2.appendleft(d)

q3 = deque([u])
distance3 = [-1]*(N+1)  # uから各頂点への最短距離、ただし青木君に追いつかれない
distance3[u] = 0

# bfs

while q3:
    n = q3.pop()
    for d in Graph[n]:
        if distance3[d] != -1 or distance1[d] >= distance2[d]:
            continue
        else:
            distance3[d] = distance3[n]+1
            q3.appendleft(d)

# 青木君に追いつかれずに行ける頂点まで行き、うろうろする

ans = max(distance2[i]-1 for i in range(1,N+1) if distance3[i] >= 0)

print(ans)

Submission status: Accepted

Solution code:
import sys

def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N,u,v = LI()
Graph = [[] for i in range(N+1)]

for i in range(N-1):
    a,b = LI()
    Graph[a].append(b)
    Graph[b].append(a)

from collections import deque

q1 = deque([u])
distance1 = [-1]*(N+1)  # uから各頂点への最短距離
distance1[u] = 0

# bfs

while q1:
    n = q1.pop()
    for d in Graph[n]:
        if distance1[d] != -1:
            continue
        else:
            distance1[d] = distance1[n]+1
            q1.appendleft(d)

q2 = deque([v])
distance2 = [-1]*(N+1)  # vから各頂点への最短距離
distance2[v] = 0

# bfs

while q2:
    n = q2.pop()
    for d in Graph[n]:
        if distance2[d] != -1:
            continue
        else:
            distance2[d] = distance2[n]+1
            q2.appendleft(d)

q3 = deque([u])
distance3 = [-1]*(N+1)  # uから各頂点への最短距離、ただし青木君に追いつかれない
distance3[u] = 0

# bfs

while q3:
    n = q3.pop()
    for d in Graph[n]:
        if distance3[d] != -1 or distance1[d] >= distance2[d]:
            continue
        else:
            distance3[d] = distance3[n]+1
            q3.appendleft(d)

# 青木君に追いつかれずに行ける頂点まで行き、うろうろする

ans = 0
for i in range(1,N+1):
    if distance3[i] >= 0:
        ans = max(ans,distance2[i]-1)

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

class Tree:
    def __init__(self, n, edges, weight=False):
        self.n = n
        self.adj = [[] for _ in range(n)]
        self.parent = [-1] * self.n
        self.children = [[] for _ in range(self.n)]
        self.dist = [-1] * self.n  # 根からの距離
        self.depth = [-1] * self.n  # 根からの深さ(cost=1での距離)
        self.weight = defaultdict(lambda: 10**18)
        if weight:
            for u, v, weight in edges:
                self.adj[u].append(v)
                self.adj[v].append(u)
                self.weight[(u, v)] = weight
                self.weight[(v, u)] = weight
        else:
            for u, v in edges:
                self.adj[u].append(v)
                self.adj[v].append(u)
                self.weight[(u, v)] = 1
                self.weight[(v, u)] = 1

    def set_root(self, root):  # O(n)
        self.root = root
        self.order = [root]
        self.dist[root] = 0
        self.depth[root] = 0
        stack = [root]
        while stack:
            v = stack.pop()
            for child in self.adj[v]:
                if child == self.parent[v]:
                    continue
                else:
                    self.parent[child] = v
                    self.children[v].append(child)
                    self.dist[child] = self.dist[v] + self.weight[(v, child)]
                    self.depth[child] = self.depth[v] + 1
                    self.order.append(child)
                    stack.append(child)

    def get_root_path(self, target):
        path = [target]
        v = target
        while v != self.root:
            path.append(self.parent[v])
            v = self.parent[v]
        path.reverse()
        return path

    def get_diameter(self, restore=False):  # double-sweepで求める  O(n)
        u = self.dist.index(max(self.dist))  # 根から一番遠いものを根とし、そこから一番遠いものを見つける
        dist_u = [-1] * self.n
        dist_u[u] = 0
        stack = [u]
        parent_u = [None for _ in range(self.n)]
        while stack:
            v = stack.pop()
            for child in self.adj[v]:
                if dist_u[child] == -1:
                    dist_u[child] = dist_u[v] + self.weight[(v, child)]
                    parent_u[child] = v
                    stack.append(child)
        diameter = max(dist_u)
        v = dist_u.index(diameter)
        if restore:
            path = [v]
            while v != u:
                v = parent_u[v]
                path.append(v)
            path.reverse()  # [u,...,v]
            return diameter, path
        else:
            return diameter, u, v

    # --- Heavy Light Decomposition --- #

    def heavy_light_decompose(self):  # O(n)
        self.subsize = [1] * self.n  # 部分木の要素数(自分含む)
        self.head = [self.root] * self.n  # 分割された各部分木の先頭
        self.tree_order = [0] * self.n

        # 末端の方から各頂点の部分木の要素数(subsize)を計算していって、
        # heavy-nodeがchildren[v][0]に来るようにする
        for v in reversed(self.order):
            v_kids = self.children[v]  # 名前が長いのでalias
            for i, child in enumerate(v_kids):
                self.subsize[v] += self.subsize[child]
                if self.subsize[child] > self.subsize[v_kids[0]]:
                    v_kids[i], v_kids[0] = v_kids[0], v_kids[i]

        # それぞれのnodeについて分割されたchianの先頭(head)を記録
        # また、DFSの行きがけ順をtree_orderとする headの浅い順でchainが入る
        stack = [self.root]
        tree_label = 0
        while stack:
            v = stack.pop()
            self.tree_order[v] = tree_label
            tree_label += 1
            for child in reversed(self.children[v]):  # スタックを使ったdfsのため逆にしておく
                if child == self.children[v][0]:
                    self.head[child] = self.head[v]
                else:
                    self.head[child] = child  # light-nodeは切り離されたsub-treeのheadになる
                stack.append(child)

    def get_hld_chain_paths(self, u, v):  # (u,v)間の経路をchainごとに返す [l,r)
        ret = []
        while True:
            if self.tree_order[u] > self.tree_order[v]:
                u, v = v, u
            if self.head[u] == self.head[v]:
                ret.append((self.tree_order[u], self.tree_order[v] + 1))
                return ret
            else:
                ret.append((self.tree_order[self.head[v]], self.tree_order[v] + 1))
                v = self.parent[self.head[v]]

    def get_hld_lca(self, u, v):  # Lowest Common Ancestor
        while True:  # head[u] = head[v] になるまで遡る
            if self.tree_order[u] > self.tree_order[v]:
                u, v = v, u
            if self.head[u] == self.head[v]:
                return u
            v = self.parent[self.head[v]]

    def get_hld_distance(self, u, v):
        return self.dist[u] + self.dist[v] - (2 * self.dist[self.get_hld_lca(u, v)])

    def exist_on_path_hld(self, u, v, x):  # u,v間の最短経路上にxがあるかどうか
        return self.get_hld_distance(u, x) + self.get_hld_distance(x, v) == self.get_hld_distance(u, v)

# ---------------------- #

n, u, v = (int(x) for x in input().split())
u -= 1
v -= 1
edges = [tuple(int(x) - 1 for x in input().split()) for _ in range(n - 1)]
tree = Tree(n, edges)
tree.set_root(0)
tree.heavy_light_decompose()
ans = 0
for i in range(n):
    if tree.get_hld_distance(i, u) <= tree.get_hld_distance(i, v):
        ans = max(ans, tree.get_hld_distance(i, v) - 1)
print(ans)