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:
N, u, v = map(int, input().split())
edge = [set() for i in range(N)]

u -= 1
v -= 1

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

def calcDepth(root):
  depth = [-1] * N
  stack = [(root, 0)]

  while stack:
    cur, curD = stack.pop()
    depth[cur] = curD
    for c in edge[cur]:
      if depth[c] != -1: continue
      stack.append((c, curD+1))
  
  return depth

Adepth = calcDepth(v)

print(max(max(Adepth), Adepth[u])-1)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,U,V = map(int,readline().split())
m = map(int,read().split())
AB = zip(m,m)

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

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

DU = dfs(U)
DV = dfs(V)

du = 0
dv = 0
for x,y in zip(DU[1:],DV[1:]):
    if x >= y:
        # 到達不可
        continue
    if du <= x:
        du = x
        dv = y

answer = dv - 1
print(answer)

Submission status: Wrong Answer

Solution code:
N, u, v = map(int, input().split())
graph = [[] for _ in range(N+1)]

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

A = [-1] * (N + 1)
T = [-1] * (N + 1)

stack = [u]
T[u] = 0
while stack:
  s = stack.pop()
  for g in graph[s]:
    if T[g] == -1:
      T[g] = T[s] + 1
      stack.append(g)
#print("T:", T)

stack = [v]
A[v] = 0
while stack:
  s = stack.pop()
  for g in graph[s]:
    if A[g] == -1:
      A[g] = A[s] + 1
      stack.append(g)
#print("A:", A)

answer = []
for i in range(N+1):
  if A[i] > T[i]:
    answer.append(T[i] + (A[i] - T[i]) // 2)
print(max(answer))

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np

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

vds = [-1]*n

qp = deque([])

qp.append(v-1)

vds[v-1] = 0

while qp:
    now = qp.pop()
    for nxt in neighbors[now]:
        if vds[nxt] == -1:
            qp.appendleft(nxt)
            vds[nxt] = vds[now] + 1

uds = [-1]*n

qp.append(u-1)

uds[u-1] = 1

while qp:
    now = qp.pop()
    for nxt in neighbors[now]:
        if uds[nxt] == -1 and nxt != v-1:
            qp.appendleft(nxt)
            uds[nxt] = 1

vds = np.array(vds)
uds = np.array(uds)
anls = vds*uds
            
print(np.amax(anls)-1)

Submission status: Wrong Answer

Solution code:
import sys


def dfs(cur, par, g, d):
    pars[cur] = par
    for to in g[cur]:
        if to == par:
            continue
        d[to] = d[cur]+1
        md[cur] = max(md[cur], dfs(to, cur, g, d)+1)
    return md[cur]


sys.setrecursionlimit(1000000)
n, u, v = map(int, input().split())
u -= 1
v -= 1
g = []
for i in range(n):
    g.append([])
for i in range(n-1):
    a, b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
d = []
md = []
pars = []
f = []
for i in range(n):
    d.append(-1)
    md.append(0)
    pars.append(-1)
    f.append(False)
d[u] = 0
dfs(u, -1, g, d)
cur = v
while cur != u:
    f[cur] = True
    cur = pars[cur]
pars[u] = True
res = d[v]//2
for i in range(n):
    if f[i] and d[i]*2 < d[v]:
        for to in g[i]:
            if to == pars[i] or f[to]:
                continue
            res = max(res, md[to]+1+d[v]-d[i] - 1)
print(res)

Submission status: Wrong Answer

Solution code:
from collections import deque

N,u,v=map(int,input().split()) # u,vから1を引く必要がある
a=[[] for _ in range(N)] # 0-initial
for _ in range(N-1):
    Ai,Bi=map(int,input().split())
    a[Ai-1].append(Bi-1)
    a[Bi-1].append(Ai-1)
T=u-1;A=v-1

# 方針
# Tは，Tからの距離dTがAからの距離dA以上であるような点のうち，最もdAが大きい点を目指す。
dT=[None]*N
qT=deque()
qT.append(T);dT[T]=0
while qT:
    u=qT.popleft()
    for v in a[u]:
        if dT[v] is None:
            dT[v]=dT[u]+1
            qT.append(v)

dA=[None]*N
qA=deque()
qA.append(A);dA[A]=0
while qA:
    u=qA.popleft()
    for v in a[u]:
        if dA[v] is None:
            dA[v]=dA[u]+1
            qA.append(v)   

dis=dA[T]
'''
print(a)
print(dT)
print(dA)
'''
l=[i for i in range(N) if dT[i]<=dA[i]]
MdA=max([dA[i] for i in range(N) if i in l])
g=dA.index(MdA) # Tが目指すべきゴール

kT=dT[g] # Tが到達に要する手数
kA=dA[g] # Aが到達に要する手数
# print(g)
# print(kT,kA)
# print(dis)
if kT==kA and dis//2<=kT:
    ans=dis//2
else:
    ans=kT+max(kA-kT-1,0)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque


def solve(n, u, v, edge_list):
    # graph
    g = [[] for i in range(n)]
    for a, b in edge_list:
        g[a].append(b)
        g[b].append(a)

    # root at v
    parent = [0] * n
    depth = [0] * n
    parent[v] = -1
    queue = deque([v])
    while len(queue) > 0:
        p = queue.popleft()
        for q in g[p]:
            if parent[p] != q:
                parent[q] = p
                depth[q] = depth[p] + 1
                queue.append(q)

    # collect max_depth from leaf
    temp_list = [[i, -depth[i]] for i in range(n)]
    temp_list = list(sorted(temp_list, key=lambda x: x[1]))
    run_list = [temp_list[i][0] for i in range(n)]
    max_children_depth = depth.copy()
    for i in run_list[:-1]:
        max_children_depth[parent[i]] = max(max_children_depth[parent[i]], max_children_depth[i])
    # print(depth)
    # print(max_children_depth)
    du = depth[u]
    up = u
    res = 0
    if du > 2:
        for _ in range(du // 2):
            up = parent[up]
            res += 1
    res += max_children_depth[up] - depth[up]
    if du % 2 == 0:
        res += 1
    return res


def main():
    n, u, v = map(int, input().split())
    edge_list = [[0, 0] for _ in range(n - 1)]
    for i in range(n - 1):
        a, b = map(int, input().split())
        edge_list[i][0] = a - 1
        edge_list[i][1] = b - 1
    u -= 1
    v -= 1
    res = solve(n, u, v, edge_list)
    print(res)


def test():
    assert solve(5, 3, 0, [[0, 1], [1, 2], [2, 3], [2, 4]]) == 2
    assert solve(5, 3, 4, [[0, 1], [0, 2], [0, 3], [0, 4]]) == 1
    assert solve(2, 0, 1, [[0, 1]]) == 0


if __name__ == "__main__":
    test()
    main()

Submission status: Wrong Answer

Solution code:
import sys



def dfs(cur, par, g, d):
    pars[cur] = par
    for to in g[cur]:
        if to == par:
            continue
        d[to] = d[cur]+1
        md[cur] = max(md[cur], dfs(to, cur, g, d)+1)
    return md[cur]


sys.setrecursionlimit(1000000)
n, u, v = map(int, input().split())
u -= 1
v -= 1
g = []
for i in range(n):
    g.append([])
for i in range(n-1):
    a, b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
d = []
md = []
pars = []
f = []
for i in range(n):
    d.append(-1)
    md.append(0)
    pars.append(-1)
    f.append(False)
d[u] = 0
dfs(u, -1, g, d)
cur = v
while cur != u:
    f[cur] = True
    cur = pars[cur]
pars[u] = True
res = d[v]//2
for i in range(n):
    if f[i] and d[i]*2 < d[v]:
        for to in g[i]:
            if to == pars[i] or f[to]:
                continue
            res = max(res, md[to]+1+d[v]-d[i] - 1)
print(0)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
import heapq
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N, u, v = map(int, input().split())
e = dd(list)
for _ in range(N - 1):
  a, b = map(int, input().split())
  e[a].append((b, 1))
  e[b].append((a, 1))
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 6)
      v0 = v // (10 ** 6)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 6) + p[0])
    return d
d = dijkstra(N, e)
p = d.path(v, 0)
pp = d.path(u, 0)
#print(p)
#print(pp)
res = 0
vis = [0] * (N + 1)
def dfs(x):
  global vis
  r = 0
  if p[x] <= pp[x]: return p[x] - ((p[x] - pp[x]) % 2)
  for y in e[x]:
    if vis[y[0]] == 1: continue
    vis[y[0]] = 1
    r = max(r, dfs(y[0]))
  #print(r, x)
  if r: return r
  else: return p[x] - ((p[x] - pp[x]) % 2)
res = dfs(u)
print(res)

Submission status: Wrong Answer

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

class LCA:
    def __init__(self,v,Edges,root=0):
        self.v=v
        self.Edges=Edges
        self.maxLog=18
        self.Parent=[[-1]*v for _ in range(self.maxLog+1)]
        self.Depth=[0]*v
        self.__bfs(root)
        for i in range(self.maxLog):
            for j in range(v):
                if self.Parent[i][j]!=-1:
                    self.Parent[i+1][j]=self.Parent[i][self.Parent[i][j]]
    def __bfs(self,root):
        Visited=[False]*self.v
        Visited[root]=True
        q=deque([root])
        while q:
            fr=q.pop()
            for to in self.Edges[fr]:
                if Visited[to]:
                    continue
                self.Parent[0][to]=fr
                self.Depth[to]=self.Depth[fr]+1
                Visited[to]=True
                q.append(to)
    def lca(self,a,b):
        if self.Depth[a]>self.Depth[b]:
            a,b=b,a
        for i in range(self.maxLog):
            if (self.Depth[b]-self.Depth[a])&(1<<i):
                b=self.Parent[i][b]
        if a==b:
            return b
        for i in reversed(range(self.maxLog-1)):
            if self.Parent[i][a]!=self.Parent[i][b]:
                a=self.Parent[i][a]
                b=self.Parent[i][b]
        return self.Parent[0][a]
    def dist(self,a,b):
        lca=self.lca(a,b)
        return self.Depth[a]+self.Depth[b]-2*self.Depth[lca]

def main():
    n,u,v=map(int,input().split())
    u-=1; v-=1
    Edges=[[] for _ in range(n)]
    for _ in range(n-1):
        x,y=map(lambda i: int(i)-1,input().split())
        Edges[x].append(y)
        Edges[y].append(x)
    L=[]
    for i in range(n):
        if len(Edges[i])==1:
            L.append(i)
    lca=LCA(n,Edges,v)
    dist=lca.dist(u,v)
    ans=dist//2
    for l in L:
        m=lca.lca(u,l)
        if lca.dist(u,m)>=lca.dist(v,m):
            continue
        d_u=lca.dist(u,l)
        d_v=lca.dist(v,l)
        d=d_v-d_u
        cnt=max(0,d//2*2-1)
        ans=max(ans,d_u+cnt)
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

g = [[] for _ in range(n)]

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

if u == v:
    print(0)
    exit()

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

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

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

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



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

if diff == 0:
    print(ans)
    exit()

if diff > 2:
    ans += (diff - 2)
    diff = 1 if diff % 2 == 1 else 2
if diff == 1:
    print(ans)
    exit()
if diff == 2:
    print(ans + 1)

Submission status: Wrong Answer

Solution code:
def dfs(cur, par, g, d):
    pars[cur] = par
    for to in g[cur]:
        if to == par:
            continue
        d[to] = d[cur]+1
        md[cur] = max(md[cur], dfs(to, cur, g, d)+1)
    return md[cur]


n, u, v = map(int, input().split())
u -= 1
v -= 1
g = []
for i in range(n):
    g.append([])
for i in range(n-1):
    a, b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
d = []
md = []
pars = []
f = []
for i in range(n):
    d.append(-1)
    md.append(0)
    pars.append(-1)
    f.append(False)
# d[u] = 0
# dfs(u, -1, g, d)
# cur = v
# while cur != u:
#     f[cur] = True
#     cur = pars[cur]
# pars[u] = True
# res = d[v]//2
# for i in range(n):
#     if f[i] and d[i]*2 < d[v]:
#         for to in g[i]:
#             if to == pars[i] or f[to]:
#                 continue
#             res = max(res, md[to]+1+d[v]-d[i] - 1)
print(0)

Submission status: Wrong Answer

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

def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

x=bfs(u-1)
y=bfs(v-1)
ans=[]
e=[]
ct=0
for i in range(n):
  if x[i]<y[i] and x[i]!=0:
    ct+=1
if ct==0:
  if x[v-1]==1:
    print(0)
  else:
    print(1)
  sys.exit()
for i in range(n):
  if x[i]<y[i]:
    if abs(x[i]-y[i])%2==0:
      if x[i]%2==1:
        ans.append(y[i]-1)
      else:
        ans.append(y[i])
    else:
      ans.append(y[i]-1)
print(max(ans))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N,u,v = inputMap()
	g = Graph()

	for i in range(N-1):
		A,B = inputMap()
		g.add_edge(A, B, 1)
		g.add_edge(B, A, 1)

	d = Dijkstra(g, u)
	tmp = d.shortest_distance(v)

	ans = -(-tmp // 2)
	print(ans)


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np

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

vds = [-1]*n

qp = deque([])

qp.append(v-1)

vds[v-1] = 0

while qp:
    now = qp.pop()
    for nxt in neighbors[now]:
        if vds[nxt] == -1:
            qp.appendleft(nxt)
            vds[nxt] = vds[now] + 1

uds = [-1]*n

qp.append(u-1)

uds[v-1] = 1

while qp:
    now = qp.pop()
    for nxt in neighbors[now]:
        if uds[nxt] == -1 and nxt != v-1:
            qp.appendleft(nxt)
            uds[nxt] = 1

vds = np.array(vds)
uds = np.array(uds)
anls = vds*uds
            
print(np.amax(anls)-1)

Submission status: Wrong Answer

Solution code:
N, u, v = map(int, input().split())
edge = [set() for i in range(N)]

u -= 1
v -= 1

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

def calcDepth(root):
  depth = [-1] * N
  stack = [(root, 0)]

  while stack:
    cur, curD = stack.pop()
    depth[cur] = curD
    for c in edge[cur]:
      if depth[c] != -1: continue
      stack.append((c, curD+1))
  
  return depth

Adepth = calcDepth(v)
Tdepth = calcDepth(u)

print(max(max(Adepth), max(Tdepth))-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

u -= 1
v -= 1

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

lst = []
def calcDist(cur, par, dst):
    global lst
    lst[cur] = dst
    for neighbour in graph[cur]:
        if neighbour == par: continue
        calcDist(neighbour, cur, dst + 1)
        
uDist = [None for i in range(N)]
vDist = [None for i in range(N)]
lst = uDist
calcDist(u, -1, 0)
lst = vDist
calcDist(v, -1, 0)

best = 0
# uDoes hiding, vdoes searching
for node in range(N):
    if uDist[node] < vDist[node]:
        if vDist[node]%2!=uDist[node]%2:
            best = max(best, uDist[node])
        else:
            best = max(best, max(uDist[n] for n in graph[node]))
    if uDist[node] == vDist[node]:
        if any((vDist[n] == uDist[n] and vDist[n] < vDist[node]) for n in graph[node]): continue
print(best)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]
    
N, u, v = map(int, input().split())
g = Graph()
for i in range(N-1):
    a, b = map(int, input().split())
    g.add_edge(a, b, 1)
    g.add_edge(b, a, 1)
d1 = Dijkstra(g, u)
d2 = Dijkstra(g, v)

max_dist = 0
same_dist = 0
for i in range(1,N+1):
    s1 = d1.shortest_distance(i)
    s2 = d2.shortest_distance(i)
    if s1 < s2:
        if s1 > max_dist:
            max_dist = s1

print(max_dist)

Submission status: Wrong Answer

Solution code:
from collections import deque

# append(i), popleft()
N, u, v = map(int, input().split())
u, v = u - 1, v - 1
graph = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    graph[a].append(b)
    graph[b].append(a)
dis = [-1 for i in range(N)]
que = deque()
que.append(v)
dis[v] = 0
while que:
    here = que.popleft()
    for next in graph[here]:
        if dis[next] != -1:
            continue
        dis[next] = dis[here] + 1
        que.append(next)
print(dis[u])

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]


def bfs(s,n,g):
    went = [False]*n
    dis = [0]*n
    que = deque([])
    que.append(s)
    went[s] = True
    while que:
        go = que.pop()
        for i in range(len(g[go])):
            if went[g[go][i]]:
                continue
            dis[g[go][i]] = dis[go] + 1
            went[g[go][i]] = True
            que.append(g[go][i])
    return dis

def main():
    n,u,v = inpm()
    g = [[] for _ in range(n)]
    g1 = [[] for _ in range(n)]
    ab = []
    for _ in range(n-1):
        a,b = inpm()
        a -= 1
        b -= 1
        g[b].append(a)
        g[a].append(b)
        ab.append((a,b))
    dis = bfs(u-1,n,g)
    path = [v-1]
    que = deque([])
    que.append(v-1)
    d = dis[v-1]-1
    while que:
        go = que.pop()
        for i in range(len(g[go])):
            if dis[g[go][i]] == d:
                d -= 1
                path.append(g[go][i])
                que.append(g[go][i])
    ans = int(len(path)/2)-1
    path.reverse()
    for i in range(n-1):
        if (ab[i][0],ab[i][1]) == (path[ans],path[ans+1]) or (ab[i][1],ab[i][0]) == (path[ans],path[ans+1]):
            continue
        g1[ab[i][0]].append(ab[i][1])
        g1[ab[i][1]].append(ab[i][0])
    dis1 = bfs(path[ans],n,g1)
    x = ans+max(dis1)
    if x == 0 and len(path)==3:
        x+=1
    print(x)




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N,u,v = inputMap()
	g = Graph()

	for i in range(N-1):
		A,B = inputMap()
		g.add_edge(A, B, 1)
		g.add_edge(B, A, 1)

	d = Dijkstra(g, u)
	tmp = d.shortest_distance(v)

	ans = tmp//2
	print(ans)


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

N , u,v = map(int,input().split())
u -= 1
v -= 1
lis = [[int(i)-1 for i in input().split()]for _ in range(N-1)]
adj = [[] for i in range(N)]
for (i,j) in lis:
    adj[i].append(j)
    adj[j].append(i)
l = [[v,0,False]]
q = deque(l)
b = [-1]*N
b[v] = 0
ans = 0
m = 0
for _ in range(N-1):
    i, n ,bl = q.popleft()
    print(i,n)
    for j in adj[i]:
        if j == u:
            ans = n+1
            bl = True
        if bl:
            m = n
        if b[j]==-1:
            q.append([j,n+1,bl])
            b[j] = n+1

i,n,bl = q.popleft()
print(n-1)