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: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

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())
    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: Wrong Answer

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)

    while dis[taka] > 2:
        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: Wrong Answer

Solution code:
from heapq import heappop, heappush
from collections import deque
n , U , V = map(int,input().split())
U -= 1
V -= 1
mp2 = []
route = [[] for i in range(n)]
for i in range(n-1):
    a , b = map(lambda x:int(x)-1,input().split())
    mp2.append((a,b,1))
    mp2.append((b,a,1))
    route[a].append(b)
    route[b].append(a)
inf=float('inf')
d=[inf for i in range(n)]
d[V] = 0
prev=[None]*n
p=dict()
for i,j,k in mp2: p[i]=p.get(i,[])+[(j,k)]

q=[]
heappush(q,(d[V],V))
while q:
    du, u = heappop(q)
    if d[u]<du: continue
    for v,weight in p.get(u,[]):
        alt=du+weight
        if d[v]>alt:
            d[v]=alt
            prev[v]=u
            heappush(q, (alt,v))
p=[U]
while prev[p[-1]]!=None: p.append(prev[p[-1]])
aida = -(-len(p)//2)-1
t = p[-(-len(p)//2)]

d = deque()
d.append(t)
visit = [0 for i in range(n)]
for i in range(len(p)):
    if p[i] == t:
        break
    visit[p[i]] = -inf
visit[t] = 0

while d:
    now = d.popleft()
    for i in route[now]:
        if visit[i] == 0:
            visit[i] = visit[now] + 1
            d.append(i)
nige = max(visit)
if nige == 0:
    print(len(p)-2)
else:
    print(aida+nige-1)

Submission status: Wrong Answer

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)

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

if span[u] < 2:
  print(0)
else:
  print(max(span)-1)

Submission status: Wrong Answer

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)

res = 10 ** 6
ans = 0
for i, (a, b) in enumerate(zip(to, ot)):
    if a < b and res > a:
        ans = i
print(ot[ans] - 1)

Submission status: Wrong Answer

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():
    n, T, A = 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)

    dist = [f_inf] * n
    dist[A - 1] = 0
    que = deque([A - 1])
    while que:
        v = que.popleft()
        for u in edge[v]:
            if dist[u] == f_inf:
                dist[u] = dist[v] + 1
                que.append(u)

    half_dist = dist[T - 1] // 2
    visited_A = [False] * n
    visited_A[A - 1] = True
    que = deque([A - 1])
    while que:
        v = que.popleft()
        for u in edge[v]:
            if dist[u] <= half_dist and not visited_A[u]:
                visited_A[u] = True
                que.append(u)

    dist2 = [f_inf] * n
    dist2[T - 1] = 0
    que = deque([T - 1])
    while que:
        v = que.popleft()
        for u in edge[v]:
            if dist2[u] == f_inf and not visited_A[u]:
                dist2[u] = dist2[v] + 1
                que.append(u)

    target = -1
    max_dist = -1
    for i in range(n):
        if dist2[i] != f_inf:
            if max_dist < dist2[i]:
                max_dist = dist2[i]
                target = i

    res = dist[target] - 1
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

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():
    n, T, A = 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)

    dist = [f_inf] * n
    dist[A - 1] = 0
    que = deque([A - 1])
    while que:
        v = que.popleft()
        for u in edge[v]:
            if dist[u] == f_inf:
                dist[u] = dist[v] + 1
                que.append(u)

    half_dist = dist[T - 1] // 2
    visited_A = [False] * n
    visited_A[A - 1] = True
    que = deque([A - 1])
    while que:
        v = que.popleft()
        for u in edge[v]:
            if dist[u] <= half_dist and not visited_A[u]:
                visited_A[u] = True
                que.append(u)

    dist2 = [f_inf] * n
    dist2[T - 1] = 0
    que = deque([T - 1])
    while que:
        v = que.popleft()
        for u in edge[v]:
            if dist2[u] == f_inf and not visited_A[u]:
                dist2[u] = dist2[v] + 1
                que.append(u)

    target = -1
    max_dist = -1
    for i in range(n):
        if dist2[i] != f_inf:
            if max_dist < dist2[i]:
                max_dist = dist2[i]
                target = i

    res = dist2[target] + (dist[target] - dist2[target]) // 2
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

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(min(ans-1,ans2))

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: Wrong Answer

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):
    k = adist[i] - tdist[i]
    ans = max(ans,tdist[i] + k-1)
print(ans)

Submission status: Wrong Answer

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):
    if tdist[i] > adist[i]:
        k = tdist[i] - adist[i]
        ans = max(ans,k-1)
print(ans)

Submission status: Wrong Answer

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,distance3[i]+(distance2[i]-distance3[i])//2)

print(ans)

Submission status: Wrong Answer

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)

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

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

print(ans)

Submission status: Wrong Answer

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 = [0] * self.n  # 根からの距離
        self.depth = [0] * self.n  # 根からの深さ(cost=1での距離)
        self.order = []
        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.order.append(root)
        self.root = root
        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(v)
dist = tree.depth[u]
first_move = (dist - 2) // 2
path = tree.get_root_path(u)
v = path[first_move]
u = path[-1 - first_move]

tree.set_root(u)
u_dist = tree.depth

tree.set_root(v)
v_dist = tree.depth

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

print(ans)

Submission status: Wrong Answer

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 = [0] * self.n  # 根からの距離
        self.depth = [0] * self.n  # 根からの深さ(cost=1での距離)
        self.order = []
        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.order.append(root)
        self.root = root
        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(v)
dist = tree.depth[u]
first_move = (dist - 2) // 2
path = tree.get_root_path(u)
v = path[first_move]
u = path[-1 - first_move]

tree.set_root(u)
u_dist = tree.dist

tree.set_root(v)
v_dist = tree.dist

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n,U,V = map(int, input().split())
U -= 1
V -= 1
ns = defaultdict(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)

def bfs(start, ng=None):
    from queue import deque
    q = deque([start])
    seen = [None] * n
    dist = [None] * n
    dist[start] = 0
    seen[start] = -1
    while q:
        u = q.pop()
        d = dist[u]
        for v in ns[u]:
            if seen[v] is None and (ng is None or v!=ng):
                seen[v] = u
                dist[v] = d + 1
                q.appendleft(v)
    return seen, dist
ps, du = bfs(U)
_, dv = bfs(V)
l = []
tmp = V
while tmp!=U:
    l.append(tmp)
    tmp = ps[tmp]
d = len(l)
l = l[::-1]
dist = d//2 if d%2 else d//2-1
ng = l[dist]
start = U if dist==0 else l[dist-1]
_, D = bfs(start, ng=ng)
if max(item for item in D if item is not None)==0:
    ans = dv[start] - 1
else:
    ans = -1
    for i,num in enumerate(D):
        if num is None:
            continue
        val = num + dv[start] - ((dv[num]-du[num])%2==1)
        ans = max(ans, val)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

def find_dist(s):
    dist = [-1] * (N + 1)
    dist[s] = 0
    q = deque()
    q.append(s)
    while q:
        u = q.popleft()
        for v in tree[u]:
            if dist[v] >= 0:
                continue
                
            dist[v] = dist[u] + 1
            q.append(v)
            
    return dist


dist_u = find_dist(U)
dist_v = find_dist(V)

index = 0
for i in range(1, N + 1):
    if dist_u[i] <= dist_v[i]:
        index = i

ans = 0
for j in tree[index]:
    ans = max(ans, dist_v[j])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

def find_dist(s):
    dist = [-1] * (N + 1)
    dist[s] = 0
    q = deque()
    q.append(s)
    while q:
        u = q.popleft()
        for v in tree[u]:
            if dist[v] >= 0:
                continue
                
            dist[v] = dist[u] + 1
            q.append(v)
            
    return dist


dist_u = find_dist(U)
dist_v = find_dist(V)

index = 0
for i in range(1, N + 1):
    if dist_u[i] <= dist_v[i]:
        index = i

ans = 10 ** 9
for j in tree[index]:
    ans = min(ans, dist_v[j])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,U,V = map(int, input().split())
U,V = U-1, V-1
E = [[] for _ in range(N)]

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

def BFS(root):
  D = [ 0 for _ in range(N) ]
  visited = [False for _ in range(N)]
  willSearch = [ False for _ in range(N)]
  Q = deque()
  Q.append(root)
  willSearch[root] = True
  while len(Q) > 0:
    now = Q.pop()
    visited[now] = True
    for nx in E[now]:
      if visited[nx] or willSearch[nx]:
        continue
      willSearch[nx] = True
      D[nx] = D[now] + 1
      Q.append(nx)
  return D

UD = BFS(U)
VD = BFS(V)

#print(UD)
#print(VD)

#初手で青木くんのPOINTにしか行けないケース
if E[U] == [V]:
  print(0)
  exit(0)
  
max_p = -1
max_d = -1
for i in range(N):
  if UD[i] > VD[i]:
    # 青木くんの方が近い点
    continue
  if max_d < UD[i]:
    max_d = UD[i]
    max_p = i

print(VD[max_p] - 1)
#print(UD[max_p], VD[max_p], max_d, max_p)