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:
def main():
    from collections import deque
    import sys

    input = sys.stdin.readline

    sys.setrecursionlimit(10 ** 7)

    def dfs(v, dist):
        for u in g[v]:
            if dist[u] == -1:
                dist[u] = dist[v] + 1
                dfs(u, dist)

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

    g = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        g[a].add(b)
        g[b].add(a)

    dist_from_a = [-1] * N
    dist_from_a[v] = 0
    dfs(v, dist_from_a)

    dist_from_t = [-1] * N
    dist_from_t[u] = 0
    dfs(u, dist_from_t)

    d_to_x = dist_from_a[u] // 2
    for j in range(N):
        if (dist_from_a[j] == d_to_x and dist_from_t[j] == d_to_x) or (dist_from_a[j] - dist_from_t[j] == 1):
            x = j
            for w in g[j]:
                if dist_from_a[j] == d_to_x - 1 and dist_from_t[j] == d_to_x + 1:
                    g[j].remove(w)
                    g[w].remove(j)
                    break
            break

    dist_from_x = [-1] * N
    dist_from_x[x] = 0

    dfs(x, dist_from_x)
    d = max(dist_from_x)
    print(d + d_to_x)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,u,v = inpl()
u -= 1
v -= 1
g = [[] for i in range(n)]
for i in range(n-1):
    a,b = inpl()
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
ucost = [INF] * n
vcost = [INF] * n

def udfs(node,c):
    for next in g[node]:
        if ucost[next] == INF:
            ucost[next] = c + 1
            udfs(next,ucost[next])
 
udfs(u,0)
def vdfs(node,c):
    for next in g[node]:
        if vcost[next] == INF:
            vcost[next] = c + 1
            vdfs(next,vcost[next])
vdfs(v,0)
# print(ucost,vcost)
res = 0
seen = [-INF] * n
seen[u] = ucost[v]
def dfs(node,nsa):
    for new in g[node]:
        if seen[new] != -INF:
            continue
        tmp = nsa
        if vcost[new] < vcost[node]:
            tmp -= 2
        if tmp <= 1:
            continue
        seen[new] = tmp
        dfs(new,tmp) 
dfs(u,ucost[v])
res = -INF
for i in range(n):
    res = max(res,seen[i] + ucost[i])
print(max(0,res-3))

Submission status: Wrong Answer

Solution code:
N, u, v = map(int, input().split())
u, v = u-1, v-1
adjL = [[] for _ in range(N)]
for _ in range(N-1):
    A, B = map(int, input().split())
    A, B = A-1, B-1
    adjL[A].append(B)
    adjL[B].append(A)

def getDist(adjList, vSt, vEn):
    numV = len(adjList)
    costs = [-1] * numV
    costs[vSt] = cost = 0
    vs = [vSt]
    while vs:
        cost += 1
        v2s = []
        for v in vs:
            for v2 in adjList[v]:
                if costs[v2] == -1:
                    costs[v2] = cost
                    v2s.append(v2)
        vs = v2s
    return costs[vEn]

# 初期状態での2人の距離
dist0 = getDist(adjL, u, v)
ans1 = dist0 - 1

def setIsOKs(adjList, vSt, dist):
    numV = len(adjList)
    costs = [-1] * numV
    costs[vSt] = cost = 0
    vs = [vSt]
    isOKs[vSt] = False
    while vs:
        cost += 1
        v2s = []
        for v in vs:
            for v2 in adjList[v]:
                if costs[v2] == -1:
                    costs[v2] = cost
                    isOKs[v2] = False
                    v2s.append(v2)
        vs = v2s
        if cost >= dist:
            break
    return

isOKs = [True] * N
if dist0 == 1:
    isOKs[v] = False
else:
    setIsOKs(adjL, v, dist0//2)

def getDist2(adjList, vSt):
    numV = len(adjList)
    costs = [-1] * numV
    costs[vSt] = cost = 0
    vs = [vSt]
    while vs:
        cost += 1
        v2s = []
        for v in vs:
            for v2 in adjList[v]:
                if not isOKs[v2]: continue
                if costs[v2] == -1:
                    costs[v2] = cost
                    v2s.append(v2)
        vs = v2s

    maxC = cost-1
    vMaxC = costs.index(maxC)
    return vMaxC, maxC

# 最も遠い頂点への高橋くんからの距離
vMaxC, distT = getDist2(adjL, u)

# 最も遠い頂点への青木くんからの距離
distA = getDist(adjL, v, vMaxC)

if distT == 0:
    ans2 = 0
else:
    ans2 = distT + distA-distT-1

print(max(ans1, ans2))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import copy
N,u,v=map(int,input().split())
l=[set()for i in range(N)]
info=[[-1,-1,-1,-1]for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    l[a-1].add(b-1)
    l[b-1].add(a-1)
terminal=set()

s={u-1}
info[u-1][0]=0
info[u-1][1]=0
k=1
while len(s)>0:
    new_s=set()
    for t in s:
        for t2 in l[t]:
            if info[t2][0]==-1:
                info[t2][0]=t
                info[t2][1]=k
                new_s.add(t2)
    s=new_s
    k+=1

s={v-1}
info[v-1][2]=0
info[v-1][3]=0
k=1
while len(s)>0:
    new_s=set()
    for t in s:
        for t2 in l[t]:
            if  info[t2][2]==-1:
                info[t2][2]=t
                info[t2][3]=k
                new_s.add(t2)
    s=new_s
    k+=1
ans=-1
d=0
print(l)
print(info)
for i in range(N):
    if not len(l[i])==1:continue
    if info[i][1]<info[i][3]:
        if d<info[i][3]:
            d=info[i][3]
print(d-1)

Submission status: Wrong Answer

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

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

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


def dfs(graph, start):
    visited = [0]*n
    stack = deque([start])
    distance = [-1]*n
    dis = 0
    while stack:
        node = stack.pop()
        visited[node] = 1
        if len(graph[node]) == 1:
            if node == start:
                distance[node] = 0
            else:
                distance[node] = dis
                dis -= 1
        for child in graph[node]:
            if visited[child] == 1:
                continue
            stack.append(child)
        dis += 1
    return distance

distance1 = np.array(dfs(graph, u-1))
distance2 = np.array(dfs(graph, v-1))
distance = distance2-distance1
dis = max(distance) 
# print(distance1, distance2)
if dis%2 == 0:
    dis -= 1
else:
    dis -= 2
if dis < 0:
    print(0)
else:
    print(dis)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True
#for i in range(n):

ans=0

n,t,a=LI_()
n+=1
g,c=GI(n,n-1)

#for i in range(1,30):


#vにはdepthをセット & -1 で未訪問フラグ

v=[-1]*(n)

def bfs(x):  # x スタート
    p=deque()
    p.append(x)
    v[x]=0
    while p:
        c=p.popleft()
        for i in g[c]:
            if v[i]==-1:
                p.append(i)
                v[i]=v[c]+1
    return

w=[-1]*(n)

def t_bfs(x):  # x スタート
    ans=0
    p=deque()
    p.append(x)
    w[x]=0
    while p:
        c=p.popleft()
        for i in g[c]:
            if w[i]==-1:
                p.append(i)
                #w[i]=w[c]+1
                if w[c]+1==v[i]:
                    ans=max(ans,v[i])
                if w[c]+1>=v[i]:
                #if w[c]+1>v[i]:
                    
                    w[i]=-inf
                else:
                    w[i]=w[c]+1
                    #ans=max(ans,v[i]-(1 if (v[i]-w[i])%2==0 else 0))
                if (w[c]+1-v[i])==1:
                    ans=max(ans,v[i])
                else:
                    ans=max(ans,v[i]-1)
                
    return ans


bfs(a)
ans=t_bfs(t)

#print(max(0,ans-1))
print(ans)

Submission status: Wrong Answer

Solution code:
N,u,v = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N-1)]
    
x = [[] for _ in range(N)]
for ab in AB:
  a = ab[0]
  b = ab[1]
  x[a-1].append(b-1)
  x[b-1].append(a-1)
  
flag1 = [False]*N
flag2 = [False]*N
length1 = [0]*N
length2 = [0]*N
go = [v-1]
while go!=[]:
  a = go.pop()
  if flag1[a]:
    continue
  else:
    flag1[a]=True
    for i in x[a]:
      if flag1[i]:
        continue
      else:
        length1[i]=length1[a]+1
        go.append(i)

go = [u-1]
while go!=[]:
  a = go.pop()
  if flag2[a]:
    continue
  else:
    flag2[a]=True
    for i in x[a]:
      if flag2[i]:
        continue
      else:
        length2[i]=length2[a]+1
        go.append(i)
        
print(max(length1))

Submission status: Wrong Answer

Solution code:
import sys
import itertools
input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def dfs(N, L, s):
    depth = [-1] * N

    stack = [(0, s)]
    while stack:
        d, p = stack.pop()
        depth[p] = d

        for q in L[p]:
            if depth[q] != -1:
                continue
            stack.append((d + 1, q))
    return depth

    
def main():
    N, u, v = read_values()
    u -= 1
    v -= 1
    L = [set() for _ in range(N)]
    for _ in range(N - 1):
        A, B = read_values()
        A -= 1
        B -= 1
        L[A].add(B)
        L[B].add(A)
    
    depth_A = dfs(N, L, v)

    depth_T = [-1] * N 
    stack = [(0, u)]
    while stack:
        d, p = stack.pop()
        if d == depth_A[p]:
            depth_T[p] = d
            continue

        if len(L[p]) == 1:
            q = list(L[p])[0]
            if depth_T[q] != -1:
                depth_T[p] = depth_A[q]
                depth_T[q] = depth_A[q]
                continue

        for q in L[p]:
            if depth_T[q] != -1:
                continue

            if depth_A[q] == d:
                depth_T[q] = d
                continue
            
            stack.append((d + 1, q))

    print(max(depth_T))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#%%
n, u, v = map(int, input().split())
u, v = u-1, v-1
a, b = [0] * (n-1), [0] * (n-1)
reach = [[] for _ in range(n)]
for i in range(n-1):
    a[i], b[i] = map(lambda x: int(x)-1, input().split())
    reach[a[i]].append(b[i])
    reach[b[i]].append(a[i])

##############################################################
#①aoki_route
#深さ、前のてんの情報
a_route = [[-1, -1] for _ in range(n)]
check = [0] * n
stack = [v]
check[v] = 1
a_route[v] = [-1, 0]

while len(stack) > 0:
    tmp = stack.pop(-1)
    tmp_list = reach[tmp]
    for i in tmp_list:
        if check[i] == 1:
            pass
        else:
            stack.append(i)
            check[i] = 1
            a_route[i] = [tmp, a_route[tmp][1]+1]

tmp = -1
for i in range(len(a_route)):
    if a_route[i][1] > tmp:
        tmp = a_route[i][1]
        AA = i

aoki_A = [AA]
tmp = AA
while True:
    tmp = a_route[tmp][0]
    if tmp == -1:
        break
    aoki_A.append(tmp)
"""
print('aoki')
print(a_route)
print('AA', AA)
print(aoki_A)
print('------------------')
"""

#########################################################################
#t_route
#前のてんの情報、深さ
t_route = [[-1, -1] for _ in range(n)]
check = [0] * n
stack = [u]
check[u] = 1
t_route[u] = [-1, 0]

while len(stack) > 0:
    tmp = stack.pop(-1)
    tmp_list = reach[tmp]
    for i in tmp_list:
        if check[i] == 1:
            pass
        else:
            stack.append(i)
            check[i] = 1
            t_route[i] = [tmp, t_route[tmp][1]+1]

takahashi_A = [AA]
tmp = AA
while True:
    tmp = t_route[tmp][0]
    if tmp == -1:
        break
    takahashi_A.append(tmp)
"""
print('takahashi')
print(t_route)
print(AA)
print(takahashi_A)
print('---------------')
"""

#####################################################
#3　点Cを求める
tmp = -1
CC = -1
for i in range(min(len(aoki_A), len(takahashi_A))):
    if aoki_A[i] != takahashi_A[i]:
        CC = tmp
        break
    tmp = aoki_A[i]
"""
print('CC', CC)
('----------------------------------')
"""
#####################################################
#4　AA - BB
#前のてんの情報、深さ、お高橋の点を通っているかの情報
x_route = [[-1, -1, -1] for _ in range(n)]
check = [0] * n
stack = [CC]
check[CC] = 1
x_route[CC] = [-1, 0, -1]

while len(stack) > 0:
    tmp = stack.pop(-1)
    tmp_list = reach[tmp]
    for i in tmp_list:
        if check[i] == 1:
            pass
        else:
            stack.append(i)
            check[i] = 1
            x_route[i] = [tmp, x_route[tmp][1]+1, x_route[tmp][2]]
            if i == u:
                x_route[i] = [tmp, x_route[tmp][1]+1, 1]

tmp = -1
for i in range(len(x_route)):
    if x_route[i][1] > tmp and x_route[i][2] == 1:
        tmp = x_route[i][1]
        BB = i
"""
print('CC - BB')
print(x_route)
print('BB', BB)
"""


('#######################')
dai = [AA, BB, CC]
aoki = []
takahashi = []
for i in range(3):
    aoki.append(a_route[dai[i]][1])
    takahashi.append(t_route[dai[i]][1])
"""
print(aoki)
print(takahashi)
"""


if takahashi[2] < aoki[2]:
    print(aoki[0]-1)
else:
    print(max(aoki[2], aoki[1]-1))

Submission status: Wrong Answer

Solution code:
def f():
    n, u, v = [int(s) for s in input().split()]
    u -= 1
    v -= 1
    neibors = [[] for i in range(n)]
    for i in range(n-1):
        a, b = [int(s)-1 for s in input().split()]
        neibors[a].append(b)
        neibors[b].append(a)
    if u == v:
        return 0

    visited = [0]*n
    thisLayer = [u]
    visited[u] = 1
    children = [set() for i in range(n)]
    father = [None]*n

    while thisLayer:
        nextLayer = []
        for node in thisLayer:
            for nb in neibors[node]:
                if not visited[nb]:
                    children[node].add(nb)
                    father[nb] = node
                    nextLayer.append(nb)
                    visited[nb] = 1
        thisLayer = nextLayer
    # print(children)
    # print(father)
    def getHight(root):
        thisLayer = [root]
        h = 0
        while thisLayer:
            h += 1
            nextLayer = []
            for node in thisLayer:
                for child in children[node]:
                    nextLayer.append(child)
            thisLayer = nextLayer
        return h

    node = v
    distance = 0
    while node != u:
        node =father[node]
        distance += 1

    if len(children[u]) <= 1 and distance <=2 :
        return distance-1

    node = v
    step = 0
    half = distance//2
    while step < half:
        node = father[node]
        step += 1
    ans = 0
    while node != u:
        children[father[node]].discard(node) # cutoff
        node = father[node]
        h = getHight(node)
        ans = max(step + h, ans)
        step += 1
    return ans - distance%2

print(f())

Submission status: Wrong Answer

Solution code:
N,u,v = map(int,input().split())
ls = []
for i in range(N-1):
  ls.append(list(map( int,input().split() )))
connected = [[] for i in range(N+1)]
for i in range(N-1):
  a,b = ls[i]
  connected[a].append(b)
  connected[b].append(a)
visited = [0 for i in range(N+1)]
q = [(v,0)]
near = 0
far = 0
while q:
  a,d = q.pop(0)
  visited[a] = 1
  for e in connected[a]:
    if not visited[e]:
      q.append((e,d+1))
  if a == u:
    distance = d
    break
q = [(u,0)]
visited = [0 for i in range(N+1)]
max_tail = 0
while q:
  a,d = q.pop(0)
  visited[a] = 1
  for e in connected[a]:
    if not visited[e] and e!=v:
      max_tail =max(max_tail,d+1)
      q.append((e,d+1))
cnt = 0
while distance>1:
  distance-= 1
  if max_tail>0:
    max_tail-=1
    distance +=1
  else:
    max_tail += 1
    distance -= 1
  cnt +=1
print(cnt)

Submission status: Wrong Answer

Solution code:
import collections
def main():

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

    if N == 2: return 0

    dist1 = [0 for _ in range(N)]
    cur = [v]
    visited = set()
    l = 0
    while cur:
        l += 1
        temp = []
        for a in cur:
            for b in graph[a]:
                if b not in visited:
                    temp.append(b)
                    visited.add(b)
                    dist1[b-1] = l
        cur = temp

    ans = -1
    dist2 = [0 for _ in range(N)]
    cur = [u]
    visited = set()
    l = 0
    while cur:
        l += 1
        temp = []
        for a in cur:
            for b in graph[a]:
                if b not in visited:
                    if l >= dist1[b-1]:
                        d = l + dist1[b-1]-1
                        if d % 2 == 0: d -= 1
                        ans = max(ans, d)
                    else:
                        if l % 2 == 0:
                            ans = max(ans, l-1)
                        else:
                            ans = max(ans, l)
                        temp.append(b)
                        visited.add(b)
                        dist2[b-1] = l
        cur = temp
        # if len(cur) > 0: ans = max(ans, l)

    return ans


if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

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

    

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

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

root_num=0
for i in range(N):
    if len(list[i])>root_num:
        root_num=i

d=djk.shortest_path(u)
path_to_leaf=[]

for i in range(N):
    if len(list[i])==1:
        path_to_leaf.append(d[i])

ans = min(path_to_leaf)-1
print(ans)

Submission status: Wrong Answer

Solution code:
N, u, v = map(int, input().split())
u, v = u -1, v -1
T = [[] for i in range(N)]
E = []
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    T[a].append([b, 1])
    T[b].append([a, 1])
    E.append([a, b, 1])


if (len(T[u])) == 1 and (T[u][0][0] == v):
    print(0)
    exit()


def dijkstra(graph, start, inf=float('inf')):
    import heapq
    n = len(graph)
    distances = [inf] * n
    distances[start] = 0
    visited = [False] * n

    # 距離・頂点
    hq = [(0, start)]
    while hq:
        dist, fr = heapq.heappop(hq)
        visited[fr] = True

        for to, cost in graph[fr]:
            new_dist = distances[fr] + cost
            if (visited[to]) or (distances[to] <= new_dist):
                continue

            distances[to] = new_dist
            heapq.heappush(hq, (new_dist, to))

    return distances


U_dist = dijkstra(T, u)
V_dist = dijkstra(T, v)

Good = set()
for i, ud, vd in zip(range(N), U_dist, V_dist):
    if ud < vd:
        Good.add(i)


T2 = [[] for i in range(N)]
for a, b, d in E:
    if (a in Good) and (b in Good):
        T2[a].append([b, 1])
        T2[b].append([a, 1])

longest = -1
tmp_max = 0
for n, d in enumerate(dijkstra(T2, u)):
    if d != float('inf'):
        if tmp_max < d:
            tmp_max = d
            longest = n

if longest == -1:
    print(1)
    exit()

reach = V_dist[longest]
if abs(tmp_max - reach) % 2 == 1:
    print(tmp_max)
else:
    print(tmp_max - 1)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True
#for i in range(n):

ans=0

n,t,a=LI_()
n+=1
g,c=GI(n,n-1)

#for i in range(1,30):


#vにはdepthをセット & -1 で未訪問フラグ

v=[-1]*(n)

def bfs(x):  # x スタート
    p=deque()
    p.append(x)
    v[x]=0
    while p:
        c=p.popleft()
        for i in g[c]:
            if v[i]==-1:
                p.append(i)
                v[i]=v[c]+1
    return

w=[-1]*(n)

def t_bfs(x):  # x スタート
    ans=0
    p=deque()
    p.append(x)
    w[x]=0
    while p:
        c=p.popleft()
        for i in g[c]:
            if w[i]==-1:
                p.append(i)
                #w[i]=w[c]+1
                if w[c]+1==v[i]:
                    ans=max(ans,v[i])
                if w[c]+1>=v[i]:
                #if w[c]+1>v[i]:
                    
                    w[i]=-inf
                else:
                    w[i]=w[c]+1
                    #ans=max(ans,v[i]-(1 if (v[i]-w[i])%2==0 else 0))
                if (w[c]+1-v[i])%2==0:
                    ans=max(ans,v[i])
                else:
                    ans=max(ans,v[i]-1)
                
    return ans


bfs(a)
ans=t_bfs(t)

#print(max(0,ans-1))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N,u,v = II()
A,B = Line(N-1,2)

def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if directed==False:
            pt[t[i]-1].append(s[i]-1)
    return pt

def bfs(pt,v):
    n = len(pt)
    d = [-1]*n
    d[v] = 0
    q = [v]
    c = 1
    while q:
        q1 = []
        for i in q:
            for j in pt[i]:
                if d[j]==-1:
                    d[j] = c
                    q1.append(j)
        q = q1
        c += 1
    return d

pt = edges_to_pt(A,B,N)
du = bfs(pt,u-1)
dv = bfs(pt,v-1)

ans = -float('inf')
#print(du)
#print(dv)
for i in range(N):
    if du[i]>=dv[i]:
        continue
    if (du[i]-dv[i])%2==0 and du[i]!=0:
        temp = dv[i]
    else:
        temp = max(0,dv[i]-1)
    print(i,temp)
    ans = max(ans,temp)

print(ans)

Submission status: Wrong Answer

Solution code:
N,u,v = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N-1)]
    
x = [[] for _ in range(N)]
for ab in AB:
  a = ab[0]
  b = ab[1]
  x[a-1].append(b-1)
  x[b-1].append(a-1)
  
flag1 = [False]*N
flag2 = [False]*N
length1 = [0]*N
length2 = [0]*N
go = [v-1]
while go!=[]:
  a = go.pop()
  if flag1[a]:
    continue
  else:
    flag1[a]=True
    for i in x[a]:
      if flag1[i]:
        continue
      else:
        length1[i]=length1[a]+1
        go.append(i)

go = [u-1]
while go!=[]:
  a = go.pop()
  if flag2[a]:
    continue
  else:
    flag2[a]=True
    for i in x[a]:
      if flag2[i]:
        continue
      else:
        length2[i]=length2[a]+1
        go.append(i)
        
print(max(length1)-1)

Submission status: Wrong Answer

Solution code:
def dijkstra(s, n, w, cost):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0

    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True

        for j in range(n):
            d[j] = min(d[j], d[v]+cost[v][j])
    return d


n, u, v = map(int, input().split())
u -= 1
v -= 1
cost = [[float("inf") for i in range(n)] for i in range(n)]

for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    cost[a][b] = 1
    cost[b][a] = 1
d = dijkstra(v, n, n-1, cost)
ans = d[u]

print(ans-1)

Submission status: Wrong Answer

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

import sys

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

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

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

for i in range(N):
    if memo[i] < memo2[i]:
        memo2[i] = -1
mx = mx2 = -1
for u, val in enumerate(memo2):
    if val > mx:
        mx = val
        val2 = memo[u]
        if val2 > mx2:
            mx2 = val2
print(val2 - 1)