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:
class LCA(object):
    def __init__(self, n, root, edges, decrement=True):
        """
        :param n: 頂点数
        :param root: 木の根
        :param edges: 辺のリスト
        :param decrement:

        :param self.depth: rootを根とした時の各頂点の深さ
        """
        self.n = n
        self.decrement = decrement
        self.root = root - self.decrement
        self.edges = [set() for _ in range(self.n)]
        for x, y in edges:
            self.add_edge(x,y)
        self.k_max = (self.n - 1).bit_length()
        self.depth = [-1 if i != self.root else 0 for i in range(self.n)]
        self.doubling = [[-1] * self.n for _ in range(self.k_max)]
        self.parent = [-1]*self.n
        self.dfs()
        for i in range(1, self.k_max):
            for k in range(self.n):
                if self.doubling[i - 1][k] != -1:
                    self.doubling[i][k] = self.doubling[i - 1][self.doubling[i - 1][k]]

    def add_edge(self, x, y):
        """
        後から追加した場合は update() をする
        """
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        self.edges[y].add(x)

    def update(self):
        self.depth = [-1 if i != self.root else 0 for i in range(self.n)]
        self.doubling = [[-1] * self.n for _ in range(self.k_max)]
        self.dfs()
        for i in range(1, self.k_max):
            for k in range(self.n):
                if self.doubling[i - 1][k] != -1:
                    self.doubling[i][k] = self.doubling[i - 1][self.doubling[i - 1][k]]


    def dfs(self):
        next_set = [self.root]
        while next_set:
            p = next_set.pop()
            for q in self.edges[p]:
                if self.depth[q] == -1:
                    self.depth[q] = self.depth[p] + 1
                    self.doubling[0][q] = p
                    next_set += [q]

    def get(self, u, v):
        """
        :return: u と v の最近共通祖先の頂点番号を返す
        """
        if self.decrement:
            u -= 1
            v -= 1
        if self.depth[v] < self.depth[u]:
            u, v = v, u

        for i in range(self.k_max):
            """ v を u の位置まで遡らせる """
            if (self.depth[v] - self.depth[u]) >> i & 1:
                v = self.doubling[i][v]
        if v == u:
            """ v の祖先が u だった場合"""
            return u + self.decrement

        for i in range(self.k_max-1, -1, -1):
            """ k = 2**(k_max-1), ..., 2**0 について、 
            「k個先を確認して共通祖先でないなら u1,v1 をk個先に移動」ということを繰り返す"""
            parent_u, parent_v = self.doubling[i][u], self.doubling[i][v]
            if parent_u != parent_v:
                u, v = parent_u, parent_v
        return self.doubling[0][u] + self.decrement

    def distance(self, u, v):
        """
        :return: u と v の最短距離を求める
        備考: 経路復元をしようとすると O(E)かかるので、経路復元が必要な場合は dfs を用いるとよい
        """
        lca_at = self.get(u,v)
        if self.decrement:
            u -= 1
            v -= 1
            lca_at -= 1
        return self.depth[u] + self.depth[v] - 2*self.depth[lca_at]

    def distance_list(self, start=1, save=False):
        """
        :param start: スタート地点
        :return: スタート地点から各点への距離のリスト
        """
        dist = [-1]*self.n
        if self.decrement:
            start -= 1
        if not save:
            self.parent = [-1] * self.n
        p, t = start, 0
        self.parent[p] = -2
        dist[p] = 0
        next_set = deque([(p, t)])

        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                if self.parent[q] != -1:
                    continue
                if q == x-1:
                    continue
                dist[q] = t + 1
                self.parent[q] = p
                next_set.append((q, t + 1))
        return dist

    def most_distant_point(self, start=1, save=False):
        """
        計算量　O(N)
        :return: (start から最も遠い頂点, 距離)
        """
        res = (start - self.decrement, 0)
        temp = 0
        for i, dist in enumerate(self.distance_list(start, save=save)):
            if dist > temp:
                temp = dist
                res = (i + self.decrement, dist)
        return res

#################################################################################################
import sys
from collections import deque
input = sys.stdin.readline

N, u, v = map(int, input().split())
edges = []
for _ in range(N-1):
    x, y = map(int, input().split())
    edges.append((x,y))

lca = LCA(N, 1, edges, decrement=True)
p = lca.get(u,v)
lu, lv = lca.depth[u-1] - lca.depth[p-1], lca.depth[v-1] - lca.depth[p-1]
if lu < lv:
    q, _ = lca.most_distant_point(v)
    print(lca.distance(q,v)-1)
    exit()
else:
    L = (lu+lv)//2
    a, x, cnt = u-1, -2, 0
    lca.distance_list()
    while cnt < L+1:
        a = lca.parent[a]
        cnt += 1
    x = a+1
    q, _ = lca.most_distant_point(u)
    print(lca.distance(q,v)-1)
    exit()

Submission status: Wrong Answer

Solution code:
from collections import*
n,u,v=map(int,input().split())
e=[[]for _ in range(n+1)]
INF=10**18
d=[INF]*(n+1)
for _ in range(n-1):
  a,b=map(int,input().split())
  e[a]+=[b]
  e[b]+=[a]
q=deque([(v,0)])
while q:
  now,c=q.popleft()
  d[now]=c
  for to in e[now]:
    if d[to]!=INF:continue
    q.append((to,c+1))
q=[(u,0)]
ans=0
vis=[1]*(n+1)
while q:
  now,c=q.pop()
  vis[now]=0
  f=1
  for to in e[now]:
    if vis[to]:
      f=0
      if d[to]>c+1:q+=[(to,c+1)]
      if d[to]==c+1:ans=max(c+1,ans)
      else:ans=max(c,ans)
  if f:ans=max(d[to],ans)
print(ans)

Submission status: Wrong Answer

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

def main():
    N, u, v = map(int, input().split())
    s = u-1
    t = v-1
    adj = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(lambda x: int(x)-1, input().split())
        adj[a].append(b)
        adj[b].append(a)
    
    # aoki BFS
    queue = deque([t])
    visit = [-1] * N
    # parent = [-1] * N
    visit[t] = 0
    
    while queue:
        now = queue.popleft()
        for u in adj[now]:
            if visit[u] < 0:
                queue.append(u)
                visit[u] = visit[now] + 1
                # parent[u] = now

    # takahashi BFS
    queue = deque([s])
    visit2 = [-1] * N
    # parent = [-1] * N
    visit2[s] = 0
    
    while queue:
        now = queue.popleft()
        for u in adj[now]:
            if visit2[u] < 0:
                queue.append(u)
                visit2[u] = visit2[now] + 1
                # parent[u] = now

    ans = [-1,-1]

    # print(visit, visit2)
    for i in range(N):
        if visit[i] - visit2[i] <= 1 and visit[i] > ans[0]:
            ans = [visit[i], i]
    
    print(visit2[ans[1]]) if visit[ans[1]] - visit2[ans[1]] == 1 else print(visit2[ans[1]]-1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

from collections import deque
def dfs(start):
    Q = deque([start])
    dist = [10**18]*N
    dist[start] = 0
    while Q:
        now = Q.pop()
        for nx in query[now]:
            if dist[nx]>=10**18:
                dist[nx] = dist[now] + 1
                Q.append(nx)
    return dist

taka = dfs(u-1)
aoki = dfs(v-1)
ans = 0

for i in range(N):
    t, a = taka[i], aoki[i]
    if t<=a:
        plus = 1 if (t-a)%2==1 else 0
        ans = max(ans, a-plus)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

from collections import deque
def dfs(start):
    Q = deque([start])
    dist = [10**18]*N
    dist[start] = 0
    while Q:
        now = Q.pop()
        for nx in query[now]:
            if dist[nx]>=10**18:
                dist[nx] = dist[now] + 1
                Q.append(nx)
    return dist

taka = dfs(u-1)
aoki = dfs(v-1)
ans = 0

for i in range(N):
    t, a = taka[i], aoki[i]
    if t<=a:
        plus = 1 if (t-a)%2==0 else 0
        ans = max(ans, t+plus)
print(ans)

Submission status: Wrong Answer

Solution code:
n,u,v=map(int,input().split())
u-=1;v-=1
edge=[[]*n for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  a-=1;b-=1
  edge[a].append(b)
  edge[b].append(a)
  
  
# from u 逃げる
# uはvからみた距離が大きい方に進むのかな
# from v 追う
# v始点でBFSして各頂点への距離を持つ
dist=[-1]*n

from collections import deque
q=deque()
q.append(v)
dist[v]=0
while q:
  p=q.popleft()
  d=dist[p]
  for i in edge[p]:
    if dist[i]==-1:
      dist[i]=d+1
      q.append(i)
#print(dist)

far=[-1]*n
q=deque()
q.append(u)
far[u]=0
while q:
  p=q.popleft()
  d=far[p]
  for i in edge[p]:
    if far[i]==-1:
      if dist[i]>d+1:
        far[i]=d+1
        q.append(i)
#print(far)
  

far_mx=max(far)
if far_mx==-1:
  print(0)
  exit()
ind=[i for i,v in enumerate(far) if v==far_mx]

to=max(dist[i] for i in ind)
ans=(to-1)
print(ans)

Submission status: Wrong Answer

Solution code:
n,u,v=map(int,input().split())
u-=1;v-=1
edge=[[]*n for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  a-=1;b-=1
  edge[a].append(b)
  edge[b].append(a)
  
  
# from u 逃げる
# uはvからみた距離が大きい方に進むのかな
# from v 追う
# v始点でBFSして各頂点への距離を持つ
dist=[-1]*n

from collections import deque
q=deque()
q.append(v)
dist[v]=0
while q:
  p=q.popleft()
  d=dist[p]
  for i in edge[p]:
    if dist[i]==-1:
      dist[i]=d+1
      q.append(i)
#print(dist)

far=[-1]*n
q=deque()
q.append(u)
far[u]=0
while q:
  p=q.popleft()
  d=far[p]
  for i in edge[p]:
    if far[i]==-1:
      if dist[i]>d+1:
        far[i]=d+1
        q.append(i)
#print(far)
  
far_mx=max(far)
ind=[i for i,v in enumerate(far) if v==far_mx]

to=max(dist[i] for i in ind)
ans=(to-1)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N,u,v = MI()
Graph = [[] for _ in range(N+1)]

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

dist_T = [-1]*(N+1)
dist_A = [-1]*(N+1)
dist_T[u] = 0
dist_A[v] = 0

from collections import deque
q1 = deque([u])
q2 = deque([v])
while q1:
    n = q1.pop()
    for d in Graph[n]:
        if dist_T[d] == -1:
            dist_T[d] = dist_T[n] + 1
            q1.appendleft(d)
while q2:
    n = q2.pop()
    for d in Graph[n]:
        if dist_A[d] == -1:
            dist_A[d] = dist_A[n] + 1
            q2.appendleft(d)

ans = 0
for i in range(1,N+1):
    if dist_T[i] < dist_A[i]:
        ans = max(ans,dist_T[i] + (dist_A[i] - dist_T[i])//2)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
sys.setrecursionlimit(1000000)

class LCA():
    def __init__(self, tree, N):
        self.tree = tree
        self.N = N
        self.dist = [-1]*(self.N)   # distance from root
    
        self.K = 1
        while (1 << self.K) < self.N:
            self.K += 1
        self.parents = [[-1]*(self.N) for i in range(self.K)]    # parents[k][u]: 2^k-th parent of u

        self.dfs(0, 0, -1)

        for k in range(self.K - 1):
            for v in range(self.N):
                if self.parents[k][v] < 0:
                    self.parents[k + 1][v] = -1
                else:
                    self.parents[k + 1][v] = self.parents[k][self.parents[k][v]]

    def dfs(self, v, d, p):
        self.dist[v] = d
        self.parents[0][v] = p
        for child in self.tree[v]:
            if self.dist[child] < 0:
                self.dfs(child, d + 1, v)
    
    def query(self, u, v):
        if self.dist[u] < self.dist[v]:
            u, v = v, u
        
        for k in range(self.K):
            if (self.dist[u] - self.dist[v]) >> k & 1:
                u = self.parents[k][u]
        
        if u == v:
            return u
        for k in range(self.K - 1, -1, -1):
            if self.parents[k][u] != self.parents[k][v]:
                u = self.parents[k][u]
                v = self.parents[k][v]
        
        return self.parents[0][u]
    
    def distBetween(self, u, v):
        return self.dist[u] + self.dist[v] - 2 * self.query(u, v)

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

u -= 1
v -= 1

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

lca = LCA(tree, N)

dist_max = 0
v_end = 0
for i in range(N):
    if lca.distBetween(u, i) < lca.distBetween(v, i):
        if dist_max <= lca.distBetween(v, i):
            dist_max = lca.distBetween(v, i)
            v_end = i

print(lca.distBetween(v, v_end) - 1)

Submission status: Wrong Answer

Solution code:
n,u,v = map(int,input().split())
g = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
seen = [False]*n
import collections
dic = collections.defaultdict(int)

q = collections.deque([])
q.append((u,0,[u],False))
tmp =[]
while q:
    s,cnt,li,f = q.popleft()
    seen[s] = True
    dic[s] = cnt
    for e in g[s]:
        if not seen[e]:
            if f:
                tmp.append(e)
            if e ==v:
                tmp += li+[e]
                f = True
            q.append((e,cnt+1,li+[e],f))
set_ = set(tmp)
ans = 0
for i in range(n):
    if i not in set_:
        ans = max(ans,dic[i])
val = dic[v]-dic[u]
if val<=ans:
    if val%2==0:
        print(ans + val-1)
    else:
        print(ans + val-1)
else:
    if val%2==0:
        print(ans+val)
    else:
        print(ans + val-1)

Submission status: Wrong Answer

Solution code:
n,u,v = map(int,input().split())
g = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
seen = [False]*n
import collections
dic = collections.defaultdict(int)

q = collections.deque([])
q.append((u,0,[u],False))
tmp =[]
while q:
    s,cnt,li,f = q.popleft()
    seen[s] = True
    dic[s] = cnt
    for e in g[s]:
        if not seen[e]:
            if f:
                tmp.append(e)
            if e ==v:
                tmp += li+[e]
                f = True
            q.append((e,cnt+1,li+[e],f))
set_ = set(tmp)
ans = 0
for i in range(n):
    if i not in set_:
        ans = max(ans,dic[i])
val = dic[v]-dic[u]
if val<=ans:
    if val%2==0:
        print(ans + val)
    else:
        print(ans + val-1)
else:
    if val%2==0:
        print(ans+val)
    else:
        print(ans + val-1)

Submission status: Wrong Answer

Solution code:
class Tree():
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - indexed].append(e[1] - indexed)
            self.tree[e[1] - indexed].append(e[0] - indexed)

    def setroot(self, root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.order = []
        self.order.append(root)
        self.size = [1 for _ in range(self.n)]
        stack = [root]
        while stack:
            node = stack.pop()
            for adj in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node] + 1
                    self.order.append(adj)
                    stack.append(adj)
        for node in self.order[::-1]:
            for adj in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                self.size[node] += self.size[adj]

    def heavylight_decomposition(self):
        self.order = [None for _ in range(self.n)]
        self.head = [None for _ in range(self.n)]
        self.head[self.root] = self.root
        self.next = [None for _ in range(self.n)]
        stack = [self.root]
        order = 0
        while stack:
            node = stack.pop()
            self.order[node] = order
            order += 1
            maxsize = 0
            for adj in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                if maxsize < self.size[adj]:
                    maxsize = self.size[adj]
                    self.next[node] = adj
            for adj in self.tree[node]:
                if self.parent[node] == adj or self.next[node] == adj:
                    continue
                self.head[adj] = adj
                stack.append(adj)
            if self.next[node] is not None:
                self.head[self.next[node]] = self.head[node]
                stack.append(self.next[node])

    def range_hld(self, u, v, edge=False):
        res = []
        while True:
            if self.order[u] > self.order[v]: u, v = v, u
            if self.head[u] != self.head[v]:
                res.append((self.order[self.head[v]], self.order[v] + 1))
                v = self.parent[self.head[v]]
            else:
                res.append((self.order[u] + edge, self.order[v] + 1))
                return res

    def subtree_hld(self, u):
        return self.order[u], self.order[u] + self.size[u]

    def lca_hld(self, u, v):
        while True:
            if self.order[u] > self.order[v]: u, v = v, u
            if self.head[u] != self.head[v]:
                v = self.parent[self.head[v]]
            else:
                return u

class SegmentTree():
    def __init__(self, arr, func=min, ie=2**63):
        self.h = (len(arr) - 1).bit_length()
        self.n = 2**self.h
        self.ie = ie
        self.func = func
        self.tree = [ie for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.tree[self.n + i] = arr[i]
        for i in range(1, self.n)[::-1]:
            self.tree[i] = func(self.tree[2 * i], self.tree[2 * i + 1])

    def set(self, idx, x):
        idx += self.n
        self.tree[idx] = x
        while idx:
            idx >>= 1
            self.tree[idx] = self.func(self.tree[2 * idx], self.tree[2 * idx + 1])

    def query(self, lt, rt):
        lt += self.n
        rt += self.n
        vl = vr = self.ie
        while rt - lt > 0:
            if lt & 1:
                vl = self.func(vl, self.tree[lt])
                lt += 1
            if rt & 1:
                rt -= 1
                vr = self.func(self.tree[rt], vr)
            lt >>= 1
            rt >>= 1
        return self.func(vl, vr)

import sys
input = sys.stdin.readline

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

t = Tree(N, E)
t.setroot(v)
t.heavylight_decomposition()

d = t.depth[u]
k = (d + 1) // 2 - 1

for _ in range(k):
    u = t.parent[u]

arr = [t.depth[t.order[i]] for i in range(N)]

st = SegmentTree(arr, max, 0)
lt, rt = t.subtree_hld(u)
maxdep = st.query(lt, rt)

print(maxdep - 1)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]
def adjacency_list(N, edges):
    g = make_list(N, 0)
    for a, b in edges: g[a].append(b), g[b].append(a)
    return g
def tree_utils(start, g):
    parent, children, depth, q = [-1]*len(g), make_list(len(g), 0), [-1]*len(g), deque([start]); depth[start] = 0
    while q:
        i = q.popleft()
        for j in g[i]:
            if depth[j] != -1: parent[i] = j
            else: depth[j] = depth[i] + 1; children[i].append(j), q.append(j)
    return parent, children, depth
def graph_distance(start, g):
    dist, q = [-1] * len(g), deque([start]); dist[start] = 0
    while q:
        i = q.popleft()
        for j in g[i]:
            if dist[j] == -1: dist[j] = dist[i] + 1; q.append(j)
    return dist

sys.setrecursionlimit(1000000)
dire, dire8 = [[1, 0], [0, 1], [-1, 0], [0, -1]], [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets, ALPHABETS = "abcdefghijklmnopqrstuvwxyz", "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD, INF = 1000000007, float("inf")

def main():
    N, u, v = LI()
    AB = LIR1(N-1)
    max_dist = [None] * N
    g = adjacency_list(N, AB)
    udist = graph_distance(u-1, g)
    vdist = graph_distance(v-1, g)

    visit = [False] * N
    ans = vdist[u-1] - 1
    q = deque([u-1])
    while q:
        i = q.popleft()
        visit[i] = True
        if udist[i] < vdist[i]:
            ans = max(ans, udist[i])
            for j in g[i]:
                if not visit[j]:
                    q.append(j)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]
def adjacency_list(N, edges):
    g = make_list(N, 0)
    for a, b in edges: g[a].append(b), g[b].append(a)
    return g
def tree_utils(start, g):
    parent, children, depth, q = [-1]*len(g), make_list(len(g), 0), [-1]*len(g), deque([start]); depth[start] = 0
    while q:
        i = q.popleft()
        for j in g[i]:
            if depth[j] != -1: parent[i] = j
            else: depth[j] = depth[i] + 1; children[i].append(j), q.append(j)
    return parent, children, depth
def graph_distance(start, g):
    dist, q = [-1] * len(g), deque([start]); dist[start] = 0
    while q:
        i = q.popleft()
        for j in g[i]:
            if dist[j] == -1: dist[j] = dist[i] + 1; q.append(j)
    return dist

sys.setrecursionlimit(1000000)
dire, dire8 = [[1, 0], [0, 1], [-1, 0], [0, -1]], [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets, ALPHABETS = "abcdefghijklmnopqrstuvwxyz", "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD, INF = 1000000007, float("inf")

def main():
    N, u, v = LI()
    AB = LIR1(N-1)
    max_dist = [None] * N
    g = adjacency_list(N, AB)
    udist = graph_distance(u-1, g)
    vdist = graph_distance(v-1, g)


    ans = vdist[u-1] - 1
    for ud, vd in zip(udist, vdist):
        if ud < vd:
            ans = max(ans, ud)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# F - Playing Tag on Tree
# https://atcoder.jp/contests/abc148/tasks/abc148_f

from heapq import heappop, heappush

INF = float("inf")

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    hq = [(0, s)]
    while hq:
        d, v = heappop(hq)
        if dist[v] < d:
            continue
        for child, child_d in G[v]:
            if dist[child] > dist[v] + child_d:
                dist[child] = dist[v] + child_d
                heappush(hq, (dist[child], child))
    return dist

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

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

for a, b in edge:
    graph[a - 1].append((b - 1, 1))
    graph[b - 1].append((a - 1, 1))

from_u = dijkstra(n, graph, u - 1)
from_v = dijkstra(n, graph, v - 1)

# print(from_u)
# print(from_v)

fil = filter(lambda x : x[0] < x[1], [[fu, fv] for fu, fv in zip(from_u, from_v)])
sfil = sorted(list(fil), key=lambda x: [-x[1], -x[0]])  

# print(sfil)

if (sfil[0][1] - sfil[0][0]) % 2 == 1:
  print(sfil[0][1] - 1)
else:
  print(sfil[0][1])

Submission status: Wrong Answer

Solution code:
# F - Playing Tag on Tree
# https://atcoder.jp/contests/abc148/tasks/abc148_f

from heapq import heappop, heappush

INF = float("inf")

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    hq = [(0, s)]
    while hq:
        d, v = heappop(hq)
        if dist[v] < d:
            continue
        for child, child_d in G[v]:
            if dist[child] > dist[v] + child_d:
                dist[child] = dist[v] + child_d
                heappush(hq, (dist[child], child))
    return dist

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

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

for a, b in edge:
    graph[a - 1].append((b - 1, 1))
    graph[b - 1].append((a - 1, 1))

from_u = dijkstra(n, graph, u - 1)
from_v = dijkstra(n, graph, v - 1)

# print(from_u)
# print(from_v)

fil = filter(lambda x : x[0] < x[1], [[fu, fv] for fu, fv in zip(from_u, from_v)])
sfil = sorted(list(fil), key=lambda x: [-x[1], -x[0]])  

# print(sfil)

if (sfil[0][1] - sfil[0][0]) % 2 == 0:
  print(sfil[0][1] - 1)
else:
  print(sfil[0][1])

Submission status: Wrong Answer

Solution code:
# F - Playing Tag on Tree
# https://atcoder.jp/contests/abc148/tasks/abc148_f

from heapq import heappop, heappush

INF = float("inf")

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    hq = [(0, s)]
    while hq:
        d, v = heappop(hq)
        if dist[v] < d:
            continue
        for child, child_d in G[v]:
            if dist[child] > dist[v] + child_d:
                dist[child] = dist[v] + child_d
                heappush(hq, (dist[child], child))
    return dist

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

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

for a, b in edge:
    graph[a - 1].append((b - 1, 1))
    graph[b - 1].append((a - 1, 1))

from_u = dijkstra(n, graph, u - 1)
from_v = dijkstra(n, graph, v - 1)

# print(from_u)
# print(from_v)

fil = filter(lambda x : x[0] < x[1], [[fu, fv] for fu, fv in zip(from_u, from_v)])
sfil = sorted(list(fil), key=lambda x: [-x[1], -x[0]])  

# print(sfil)

if (sfil[0][1] - sfil[0][0]) % 2 == 0:
  print(sfil[0][0] + 1)
else:
  print(sfil[0][0])

Submission status: Wrong Answer

Solution code:
# F - Playing Tag on Tree
# https://atcoder.jp/contests/abc148/tasks/abc148_f

from heapq import heappop, heappush

INF = float("inf")

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    hq = [(0, s)]
    while hq:
        d, v = heappop(hq)
        if dist[v] < d:
            continue
        for child, child_d in G[v]:
            if dist[child] > dist[v] + child_d:
                dist[child] = dist[v] + child_d
                heappush(hq, (dist[child], child))
    return dist

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

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

for a, b in edge:
    graph[a - 1].append((b - 1, 1))
    graph[b - 1].append((a - 1, 1))

from_u = dijkstra(n, graph, u - 1)
from_v = dijkstra(n, graph, v - 1)

# print(from_u)
# print(from_v)

fil = filter(lambda x : x[0] < x[1], [[fu, fv] for fu, fv in zip(from_u, from_v)])
sfil = sorted(list(fil), key=lambda x: -x[1])  

if (sfil[0][0] - sfil[0][0]) % 2 == 0:
  print(sfil[0][0] + 1)
else:
  print(sfil[0][0])

Submission status: Wrong Answer

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

from collections import deque
def shortest(tree,start):
    from_start=[0]*N
    q = deque([(-1,start,0)])
    while q:
        parent,x,time = q.popleft()
        for y in tree[x]:
            if y == parent:
                continue
            q.append((x,y,time+1))
        from_start[x]=time
    return from_start

from_u = shortest(tree,U)
from_v = shortest(tree,V)

print(max(uu for uu,vv in zip(from_u,from_v) if uu<vv ) )