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 p_f():
    from sys import stdin
    input = stdin.readline
    N, u, v = map(int, input().split())
    edges = [list(map(int, input().split())) for i in range(N - 1)]
    if u == v:
        print(0)
        exit()

    def BFS(K, edges, N):
        roots = [[] for i in range(N)]
        for a, b in edges:
            roots[a - 1] += [(b - 1, 1)]
            roots[b - 1] += [(a - 1, 1)]
        dist = [-1] * N
        stack = []
        stack.append(K)
        dist[K] = 0
        while stack:
            label = stack.pop(-1)
            for i, c in roots[label]:
                if dist[i] == -1:
                    dist[i] = dist[label] + c
                    stack += [i]
        return dist

    dist = BFS(v - 1, edges, N)
    if dist[u - 1] >= max(dist) - dist[u - 1]:
        print(max(dist) - 1)
    else:
        print(dist[u - 1] - 1)


if __name__ == '__main__':
    p_f()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

du = [0] * N
pu = [-1] * N
q = [(u - 1, -1)]
while q :
  cur, pre = q.pop()
  for nex in vec[cur] :
    if nex != pre :
      du[nex] = du[cur] + 1
      pu[nex] = cur
      q.append((nex, cur))

dv = [0] * N
pv = [-1] * N
q = [(v - 1, -1)]
while q :
  cur, pre = q.pop()
  for nex in vec[cur] :
    if nex != pre :
      dv[nex] = dv[cur] + 1
      pv[nex] = cur
      q.append((nex, cur))

# du[u - 1] = 2
# dv[v - 1] = 2

ret = 0
for i, (u, v) in enumerate(zip(du, dv)) :
  if pu[i] == -1 or pv[i] == -1 :
    continue
  # print(i, pu[i], pv[i])
  if u < v or (u == v and pu[i] != pv[i]) :
    if u == v :
      ret = max(ret, u)
    else :
      ret = max(ret, v - 1)
print(ret)

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]:
                    if (w[c]+1-v[i])%2==0:
                        ans=max(ans,v[i])
                    else:
                        ans=max(ans,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))
                    
    return ans


bfs(a)
ans=t_bfs(t)

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

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
def main():
    def dijkstra_search(s):
        d = [INF] * n
        searched = [False] * n
        d[s] = 0
        searched[s] = True
        edge_list = []
        count = 1
        for i in edge[s]:
            heappush(edge_list,i)
        while edge_list:
            min_d,min_v = heappop(edge_list)
            if searched[min_v] or min_d > d[min_v]:
                continue
            v = min_v
            d[v] = min_d
            searched[v] = True
            count += 1
            for i,j in edge[v]:
                next_d = i+d[v]
                if not searched[j]:
                    heappush(edge_list,(next_d,j))
            if count == n:
                break
        return d
    
    def dijkstra_back(s,t):
        prev = [s] * n
        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 i in range(n):
                if d[i] > d[v] + cost[v][i]: 
                    d[i] = d[v] + cost[v][i]
                    prev[i] = v
        path = [t]
        while prev[t] != s:
            path.append(prev[t])
            prev[t] = prev[prev[t]]
        path.append(s)
        path = path[::-1]
        return path
    
    n,tk,ao = map(int,input().split())
    tk = tk-1
    ao = ao-1
    route = [tuple(map(int,input().split())) for _ in range(n-1)]
    INF = float('inf')
    edge = [[] for _ in range(n)]
    for i in route:
        edge[i[0]-1].append((1,i[1]-1))
        edge[i[1]-1].append((1,i[0]-1))
    cost = [[INF for i in range(n)] for i in range(n)] 
    for i in route:
        cost[i[0]-1][i[1]-1] = 1
        cost[i[1]-1][i[0]-1] = 1
    dtk = dijkstra_search(tk)
    dao = dijkstra_search(ao)
    sdao = sorted([(j,i) for i,j in enumerate(dao)],reverse=True)
    ans = INF
    for i in sdao:
        g = i[0]
        rtk = dijkstra_back(tk,g)
        f = False
        for j in rtk:
            if dtk[j] >= dao[j] and dtk[j]%2 == dao[j]%2:
                pass
            else:
                ans = max([dao[j],dtk[j]+1])
                if dao[j]%2 == (dtk[j]+1)%2:
                    ans -= 1
                f = True
                break
        if f:
            print(ans)
            break
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import queue
from collections import defaultdict

input = sys.stdin.readline
sys.setrecursionlimit(20000000)

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

checked = [False] * n
# 深さ優先
s = u - 1
e = v - 1

def dfs(cur, l):
    if cur == e:
        return l + [cur]
    for i in ab[cur]:
        if checked[i]:
            continue
        checked[i] = True
        res = dfs(i, l + [cur])
        if res != None:
            return res
    return None

path = dfs(s, [])
checked = [False] * n
run_p = 0
if len(path) > 2:
    if len(path) % 2 == 0:
        ans = len(path) // 2 - 1
        s = path[len(path)//2 - 1]
        e = path[len(path)//2]
    else:
        ans = len(path) // 2 - 1
        s = path[len(path)//2 - 1]
        e = path[len(path)//2]
        run_p += 1
checked[e] = True


q = queue.Queue()
q.put((s, 0))
checked[s] = True
while not q.empty():
    cur, count = q.get()
    for i in ab[cur]:
        if checked[i]:
            continue
        checked[i] = True
        q.put((i, count+1))
        run_p = max(run_p, count + 1)
print(ans + run_p)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2 * 10 ** 5)

n, u, v = map(int, input().split())
conn = {}
for _ in range(n-1):
    ai, bi = map(int, input().split())
    if conn.get(ai):
        conn.get(ai).add(bi)
    else:
        conn[ai] = {bi}
        
    if conn.get(bi):
        conn.get(bi).add(ai)
    else:
        conn[bi] = {ai}
    
def hoge(start, geta, dist_dict):
    dist_dict[start] = geta
    for i in conn[start]:
        if dist_dict.get(i) == None:
            hoge(i, geta + 1, dist_dict)

    
u_dist = {}
hoge(u, 0, u_dist)
v_dist = {}
hoge(v, 0, v_dist)

safety = [val for k, val in u_dist.items() if val < v_dist[k]]
danger = [val for k, val in u_dist.items() if val == v_dist[k]]
print(max([max(safety or [0]), min(danger or [0]), 1]))

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

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

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

WHITE = 0
GRAY = 1
BLACK = 2

color = [WHITE] * n
d = [-1] * n
f = [-1] * n
p = [-1] * n
t = 0


def dfs(s):
    if color[s] == BLACK:
        return
    global t
    stack = [s]
    color[s] = GRAY
    d[s] = t
    t += 1
    while stack:
        u = stack[-1]
        for v in g[u]:
            if color[v] == WHITE:
                color[v] = GRAY
                d[v] = t
                p[v] = u
                t += 1
                stack.append(v)
                break
        else:
            color[u] = BLACK
            f[u] = t
            t -= 1
            stack.pop()

dfs(V)
d_cp = deepcopy(d)
back = (d[U] - 1) // 2

node = U
for _ in range(back):
    node = p[node]

if node == U:
    print(d[U] - 1)
    exit()

color = [WHITE] * n
d = [-1] * n
f = [-1] * n
p = [-1] * n
t = 0

dfs(node)
mx_depth = -1
for i, e in enumerate(d[::-1]):
    if i == n - 1:
        continue
    if e > mx_depth:
        mx_depth = e
        fin = n - i - 1

ans = d_cp[fin] - 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, U, V = map(int, input().split())
A = [[] for _ in range(N)]

import sys
sys.setrecursionlimit(10**8)
for _ in range(N - 1):
    a, b = map(int, input().split())

    A[a - 1].append(b - 1)
    A[b - 1].append(a - 1)

C = [0] * N

def DFS(x, pre, cnt):
    if C[x] < cnt:
        C[x] = cnt
    cnt += 1
    for a in A[x]:
        if a == pre:
            continue

        if a == (U - 1):
            continue 
        
        DFS(a, x, cnt)


DFS(V - 1, -1, 0)
ans = max(C) - 1
if ans < 0:
    ans = 0
print(ans)

Submission status: Wrong Answer

Solution code:
n,u,v = map(int,input().split())

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

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

visit1 = [False]*n
visit2 = [False]*n

visit1[u-1] = True
visit2[v-1] = True

stack1 = [u-1]
stack2 = [v-1]

dis1 = [-1] * n
dis2 = [-1] * n
dis1[u-1] = 0
dis2[v-1] = 0

while stack1:
    for _ in range(len(stack1)):
        q1 = stack1.pop(-1)
        for i in edges[q1]:
            if not visit1[i] and not visit2[i]:
                visit1[i] = True
                dis1[i] = dis1[q1] + 1
                stack1.append(i)

    for _ in range(len(stack2)):
        q2 = stack2.pop(-1)
        for i in edges[q2]:
            if not visit2[i]:
                visit2[i] = True
                dis2[i] = dis2[q2] + 1
                stack2.append(i)

while stack2:
    q = stack2.pop(-1)
    for i in edges[q]:
        if not visit2[i]:
            visit2[i] = True
            dis2[i] = dis2[q] + 1
            stack2.append(i)

ans = max(dis2)

print(ans)

Submission status: Wrong Answer

Solution code:
import copy

n, u, v = map(int, input().split())
graph = {i + 1:[] for i in range(n)}
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
graph2 = copy.deepcopy(graph)
taka = [u]
aoki = [v]
list_t = [[u]]
list_a = [[v]]
num = 0
while list_t or list_a:
    temp_a = []
    temp_t = []
    if list_a:
        check_a = list_a.pop(0)
        for i in check_a:
            for j in graph[i]:
                if j not in taka:
                    aoki.append(j)
                    temp_a.append(j)
                    graph[j].remove(i)
        if temp_a:
            list_a.append(temp_a)
    if list_t:
        check_t = list_t.pop(0)
        for i in check_t:
            for j in graph[i]:
                if j not in aoki:
                    taka.append(j)
                    temp_t.append(j)
                    graph[j].remove(i)
        if temp_t:
            list_t.append(temp_t)
list_d = []
for i in check_t:
    dis = 0
    check_list = [[i]]
    while check_list:
        check = check_list.pop(0)
        temp = []
        for j in check:
            for k in graph2[j]:
                temp.append(k)
                graph2[k].remove(j)
        if temp:
            check_list.append(temp)
            dis += 1
    list_d.append(dis)
print(max(list_d) - 1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

du = [0] * N
pu = [-1] * N
q = [(u - 1, -1)]
while q :
  cur, pre = q.pop()
  for nex in vec[cur] :
    if nex != pre :
      du[nex] = du[cur] + 1
      pu[nex] = cur
      q.append((nex, cur))

dv = [0] * N
pv = [-1] * N
q = [(v - 1, -1)]
while q :
  cur, pre = q.pop()
  for nex in vec[cur] :
    if nex != pre :
      dv[nex] = dv[cur] + 1
      pv[nex] = cur
      q.append((nex, cur))

# du[u - 1] = 2
# dv[v - 1] = 2

ret = 0
for i, (u, v) in enumerate(zip(du, dv)) :
  if pu[i] == -1 or pv[i] == -1 :
    continue
  # print(i, pu[i], pv[i])
  if u < v or (u == v and pu[i] != pv[i]) :
    if u == v :
      ret = max(ret, u)
    elif u % 2 == v % 2 :
      ret = max(ret, v - 2)
    else :
      ret = max(ret, v - 1)
print(ret)

Submission status: Wrong Answer

Solution code:
n,u,v = map(int,input().split())

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

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

visit1 = [False]*n
visit2 = [False]*n

visit1[u-1] = True
visit2[v-1] = True

stack1 = [u-1]
stack2 = [v-1]

dis1 = [-1] * n
dis2 = [-1] * n
dis1[u-1] = 0
dis2[v-1] = 0

while stack1:
    for _ in range(len(stack1)):
        q1 = stack1.pop(-1)
        for i in edges[q1]:
            if not visit1[i] and not visit2[i]:
                visit1[i] = True
                dis1[i] = dis1[q1] + 1
                stack1.append(i)

    for _ in range(len(stack2)):
        q2 = stack2.pop(-1)
        for i in edges[q2]:
            if not visit2[i]:
                visit2[i] = True
                dis2[i] = dis2[q2] + 1
                stack2.append(i)

while stack2:
    q = stack2.pop(-1)
    for i in edges[q]:
        if not visit2[i]:
            visit2[i] = True
            dis2[i] = dis2[q] + 1
            stack2.append(i)

ans = max(dis2) -1

print(ans)

Submission status: Wrong Answer

Solution code:
def p_f():
    from sys import stdin
    input = stdin.readline
    N, u, v = map(int, input().split())
    edges = [list(map(int, input().split())) for i in range(N - 1)]

    def BFS(K, edges, N):
        roots = [[] for i in range(N)]
        for a, b in edges:
            roots[a - 1] += [(b - 1, 1)]
            roots[b - 1] += [(a - 1, 1)]
        dist = [-1] * N
        stack = []
        stack.append(K)
        dist[K] = 0
        while stack:
            label = stack.pop(-1)
            for i, c in roots[label]:
                if dist[i] == -1:
                    dist[i] = dist[label] + c
                    stack += [i]
        return dist

    dist = BFS(v - 1, edges, N)
    if dist[u - 1] > max(dist) - dist[u - 1]:
        print(max(dist) - 1)
    else:
        print(dist[u - 1] - 1)


if __name__ == '__main__':
    p_f()

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(aoki[1]-1)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

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

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

WHITE = 0
GRAY = 1
BLACK = 2

color = [WHITE] * n
d = [-1] * n
f = [-1] * n
p = [-1] * n
t = 0


def dfs(s):
    if color[s] == BLACK:
        return
    global t
    stack = [s]
    color[s] = GRAY
    d[s] = t
    t += 1
    while stack:
        u = stack[-1]
        for v in g[u]:
            if color[v] == WHITE:
                color[v] = GRAY
                d[v] = t
                p[v] = u
                t += 1
                stack.append(v)
                break
        else:
            color[u] = BLACK
            f[u] = t
            t -= 1
            stack.pop()

dfs(V)
d_cp = deepcopy(d)
back = (d[U] - 1) // 2

node = U
for _ in range(back):
    node = p[node]

if node == U:
    print(d[U] - 1)
    exit()

color = [WHITE] * n
d = [-1] * n
f = [-1] * n
p = [-1] * n
t = 0

dfs(node)
fin = 0
mx_depth = 0
for i, e in enumerate(d[::-1]):
    if i == n - 1:
        continue
    if e > mx_depth:
        mx_depth = e
        fin = n - i - 1

ans = d_cp[fin] - 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)


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

ans = 1
for d in dijkstra(T, u):
    if d != float('inf'):
        ans = max(ans, d)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2 * 10 ** 5)

n, u, v = map(int, input().split())
conn = {}
for _ in range(n-1):
    ai, bi = map(int, input().split())
    if conn.get(ai):
        conn.get(ai).add(bi)
    else:
        conn[ai] = {bi}
        
    if conn.get(bi):
        conn.get(bi).add(ai)
    else:
        conn[bi] = {ai}
    
def hoge(start, geta, dist_dict):
    dist_dict[start] = geta
    for i in conn[start]:
        if dist_dict.get(i) == None:
            hoge(i, geta + 1, dist_dict)

    
u_dist = {}
hoge(u, 0, u_dist)
v_dist = {}
hoge(v, 0, v_dist)

safety = [val for k, val in u_dist.items() if val < v_dist[k]]
danger = [val for k, val in u_dist.items() if val == v_dist[k]]
print(max([max(safety or [0]), min(danger or [0])]))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, u, v, AB):
    ans = 0
    g = defaultdict(set)
    for a, b in AB:
        g[a].add(b)
        g[b].add(a)


    def f(start):
        s = [(start, 0)]
        d = {}
        d[start] = 0
        while s:
            c, l = s.pop()
            for n in g[c]:
                if n not in d:
                    s.append((n, l+1))
                    d[n] = l+1
        return d

    vd = f(v)
    t = u
    a = v
    s = [(t, 0)]
    d = {}
    d[t] = 0
    while s:
        u, l = s.pop()
        for v in g[u]:
            if v not in d and l + 1 < vd[v]:
                s.append((v, l+1))
                tmp = vd[v] - (l+1)
                tmp = (tmp//2) * 2
                d[v] = tmp + (l+1)
    dest = (0, -1)
    for k, v in d.items():
        dest = max(dest, (v, k))

    d[t] = (vd[t] // 2) * 2

    ans = dest[0]
    # error_print(dest)
    # error_print(d)
    # error_print(vd)
    if vd[dest[1]] - dest[0] > 1:
        ans += 1
    return ans


def main():
    N, u, v = read_int_n()
    AB = [read_int_n() for _ in range(N-1)]
    print(slv(N, u, v, AB))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2 * 10 ** 5)

n, u, v = map(int, input().split())
conn = {}
for _ in range(n-1):
    ai, bi = map(int, input().split())
    if conn.get(ai):
        conn.get(ai).add(bi)
    else:
        conn[ai] = {bi}
        
    if conn.get(bi):
        conn.get(bi).add(ai)
    else:
        conn[bi] = {ai}
    
def hoge(start, geta, dist_dict):
    dist_dict[start] = geta
    for i in conn[start]:
        if dist_dict.get(i) == None:
            hoge(i, geta + 1, dist_dict)

    
u_dist = {}
hoge(u, 0, u_dist)
v_dist = {}
hoge(v, 0, v_dist)

print(u_dist)
print(v_dist)

safety = [val for k, val in u_dist.items() if val < v_dist[k]]
danger = [val for k, val in u_dist.items() if val == v_dist[k]]
print(max([max(safety or [0]), min(danger or [0])]))

Submission status: Wrong Answer

Solution code:
def p_f():
    from sys import stdin
    input = stdin.readline
    N, u, v = map(int, input().split())
    edges = [list(map(int, input().split())) for i in range(N - 1)]

    def BFS(K, edges, N):
        roots = [[] for i in range(N)]
        for a, b in edges:
            roots[a - 1] += [(b - 1, 1)]
            roots[b - 1] += [(a - 1, 1)]
        dist = [-1] * N
        stack = []
        stack.append(K)
        dist[K] = 0
        while stack:
            label = stack.pop(-1)
            for i, c in roots[label]:
                if dist[i] == -1:
                    dist[i] = dist[label] + c
                    stack += [i]
        return dist

    dist = BFS(v - 1, edges, N)
    if dist[u - 1] >= max(dist) - dist[u - 1]:
        print(max(dist) - 1)
    else:
        print(dist[u - 1] - 1)


if __name__ == '__main__':
    p_f()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

tree=[[] for i in range(n)]
for i in list:
  tree[i[0]-1].append(i[1]-1)
  tree[i[1]-1].append(i[0]-1)

dist=[-1 for i in range(n)]
dist[u-1]=0

que=deque()
que.append(u-1)
while que:
    x=que.popleft()
    if x==v-1:
        print(dist[x]-1)
        break
    for p in tree[x]:
        if dist[p]==-1:
            que.append(p)
            dist[p]=dist[x]+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
        best = max(best, uDist[node])
print(best)

Submission status: Wrong Answer

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

n, u, v = 9, 6, 1
ab = [[1,2],[2,3],[3,4],[4,5],[5,6],[4,7],[7,8],[8,9]]

from collections import defaultdict
graph = defaultdict(list)
for i in range(n - 1):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    graph[a].append(b)
    graph[b].append(a)
u -= 1
v -= 1

visited = [0] * n
def dfs(cur, target, path):
    # print(cur, path)
    visited[cur] = 1
    if cur == target:
        return path
    else:
        for v in graph[cur]:
            if not visited[v]:
                p = dfs(v, target, path + [v])
                if p:
                    return p

path = dfs(v, u, [v])
# print(path)

_path_aoki = path[:len(path) // 2]
path_aoki = [0] * n
for i in range(len(_path_aoki)):
    path_aoki[_path_aoki[i]] = 1

# 最も遠い点
paths = []
visited = [0] * n
def dfs2(cur, path):
    visited[cur] = 1
    f = True
    for v in graph[cur]:
        if not visited[v] and not path_aoki[v]:
            f = False
            dfs2(v, path + [v])
    if f:
        paths.append(path)

cur = _path_aoki[-1]
dfs2(cur, [cur])

l = 0
for path in paths:
    if len(path) >= l:
        longest = path
        l = len(path)

path_aoki = _path_aoki[:-1] + longest

print(len(path_aoki) - 2)