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: Runtime Error

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 heapq import heappop, heappush
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

start = v
d = [float('inf') for i in range(n)] # 最短距離
d[start] = 0

q = [] # min-heap, (距離, 頂点)
prev = [None] * n
path = [u]
heappush(q, (d[start], start))
while q:
    duu, uu = heappop(q) # 最短距離とその頂点
    if d[uu] < duu:
        continue
    for vv in graph[uu]:
        alt = duu + 1
        if d[vv] > alt:
            d[vv] = alt
            prev[vv] = uu
            heappush(q, (alt, vv))

while prev[path[-1]] != None:
    path.append(prev[path[-1]])
path = path[::-1]
# 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)

Submission status: Runtime Error

Solution code:
sys.setrecursionlimit(1000000)

class Tree:
  C, RL = {}, {}
  R, N, D, S, P = None, None, None, None, None
  def __init__(s, num):
    s.N = num
  def setC(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def makeRank(s, root):
    s.R = [0] * s.N
    s.R[root] = 1
    s.RL[1] = [root]
    s.S = {}
    s.P = {}
    F = [root]
    s.D = 2
    while F != []:
      Ft = []
      s.RL[s.D] = []
      for i in F:
        for j in s.C[i]:
          if s.R[j] == 0:
            s.R[j] = s.D
            Ft.append(j)
            s.RL[s.D].append(j)
            if i not in s.S:
              s.S[i] = [j]
            else:
              s.S[i].append(j)
            s.P[j] = i

      s.D += 1
      F = Ft
  def getDeep(s, x):
    ans = 0
    if x in s.S:
      for i in s.S[x]:
        ans = max(ans, s.getDeep(i))
      return ans + 1
    else:
      return 0
  def getParent(s, x, n):
    if n == 0:
      return x
    return s.getParent(s.P[x], n - 1)
    

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

T = Tree(N)
for a, b in AB:
  T.setC(a - 1, b - 1)

T.makeRank(v - 1)
t = (T.R[u - 1] // 2) - 1
f = T.R[u - 1] % 2
k = T.getDeep(T.getParent(u - 1, t))
print(t + k + f)

Submission status: Runtime Error

Solution code:
sys.setrecursionlimit(100000)

class Tree:
  C, RL = {}, {}
  R, N, D, S, P = None, None, None, None, None
  def __init__(s, num):
    s.N = num
  def setC(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def makeRank(s, root):
    s.R = [0] * s.N
    s.R[root] = 1
    s.RL[1] = [root]
    s.S = {}
    s.P = {}
    F = [root]
    s.D = 2
    while F != []:
      Ft = []
      s.RL[s.D] = []
      for i in F:
        for j in s.C[i]:
          if s.R[j] == 0:
            s.R[j] = s.D
            Ft.append(j)
            s.RL[s.D].append(j)
            if i not in s.S:
              s.S[i] = [j]
            else:
              s.S[i].append(j)
            s.P[j] = i

      s.D += 1
      F = Ft
  def getDeep(s, x):
    ans = 0
    if x in s.S:
      for i in s.S[x]:
        ans = max(ans, s.getDeep(i))
      return ans + 1
    else:
      return 0
  def getParent(s, x, n):
    if n == 0:
      return x
    return s.getParent(s.P[x], n - 1)
    

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

T = Tree(N)
for a, b in AB:
  T.setC(a - 1, b - 1)

T.makeRank(v - 1)
t = (T.R[u - 1] // 2) - 1
f = T.R[u - 1] % 2
k = T.getDeep(T.getParent(u - 1, t))
print(t + k + f)

Submission status: Runtime Error

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 = 0
for I in range(n):
    If dis1[I] != 0:
    Ans =max(Ans,dis2[i])
ans = Ans -1

print(ans)

Submission status: Runtime Error

Solution code:
N, u, v = map(int,input().split())
edges=[list(map(int,input().split())) for i in range(N-1)]
root = [[] for i in range(N)]
ans = 100000000
for a,b in edges:
    root[a-1].append(b-1)
    root[b-1].append(a-1)
def chase_move(my_pos,opponent_pos):
    if opponent_pos in root[my_pos]:
        tmp = [opponent_pos]
        return tmp
    else:
        tmp = root[my_pos][:]
        return tmp

def escape_move(my_pos,opponent_pos):
    if opponent_pos in root[my_pos]:
        tmp = root[my_pos][:]
        tmp.remove(opponent_pos)
        return tmp
    else:
        tmp = root[my_pos][:]
        return tmp
        
def main(takahashi_pos,aoki_pos,cnt,turn):
    global ans
    if takahashi_pos==aoki_pos:
        if cnt<ans:
            ans=cnt
    if ans<=cnt:
        return
    if turn == 0:
        tmp = escape_move(takahashi_pos,aoki_pos)
        for i in tmp:
            main(i,aoki_pos,cnt,1)
    elif turn == 1:
        cnt+=1
        tmp = chase_move(aoki_pos,takahashi_pos)
        for i in tmp:
            main(takahashi_pos,i,cnt,0)
main(u-1,v-1,0,0)
print(ans)

Submission status: Runtime Error

Solution code:
N, u, v = map(int,input().split())
edges=[list(map(int,input().split())) for i in range(N-1)]
root = [[] for i in range(N)]
ans = 100000000
for a,b in edges:
    print(a,b)
    root[a-1].append(b-1)
    root[b-1].append(a-1)
def chase_move(my_pos,opponent_pos):
    if opponent_pos in root[my_pos]:
        tmp = [opponent_pos]
        return tmp
    else:
        tmp = root[my_pos][:]
        return tmp

def escape_move(my_pos,opponent_pos):
    if opponent_pos in root[my_pos]:
        tmp = root[my_pos][:]
        tmp.remove(opponent_pos)
        return tmp
    else:
        tmp = root[my_pos][:]
        return tmp
        
def main(takahashi_pos,aoki_pos,cnt,turn):
    global ans
    if takahashi_pos==aoki_pos:
        if cnt<ans:
            ans=cnt
    if ans<=cnt:
        return
    if turn == 0:
        tmp = escape_move(takahashi_pos,aoki_pos)
        for i in tmp:
            main(i,aoki_pos,cnt,1)
    elif turn == 1:
        cnt+=1
        tmp = chase_move(aoki_pos,takahashi_pos)
        for i in tmp:
            main(takahashi_pos,i,cnt,0)
main(u-1,v-1,0,0)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

input = sys.stdin.readline
n, u, v = map(int, input().split())

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

memo = [[0, 0] for i in range(n)]

def dfs(cur, pre, dep, p):
    stack = deque([[cur, pre, dep, p]])
    while stack:
        cur, pre, dep, p  = stack.pop()
        memo[cur][p] = dep
        for e in E[cur]:
            if e != pre:
                stack.push(e, cur, dep + 1, p)

dfs(u - 1, - 1, 0, 0)
dfs(v - 1, -1, 0, 1)

# print(memo)
ans = 0
for a, b in memo:
    ans = max(ans, b - 1)
print(ans)

Submission status: Runtime Error

Solution code:
#%%
import numpy as np
n,nige,oni = map(int,input().split())
aa = np.zeros((n,n),dtype=bool)
for i in range(n-1):
    a,b = map(int,input().split())
    aa[a-1][b-1] = 1
    aa[b-1][a-1] = 1
nigel = np.zeros(n)
nigel[nige-1] = 1
onil = np.zeros(n)
onil[oni-1] = 1
ans = 0
for i in range(n-1):
    nigel = np.any(aa[nigel] == True,axis = 0)
    if np.logical_and(onil,nigel) == nigel:
        print(ans)
        exit()
    ans += 1
    onil = np.any(aa[onil] == True,axis = 0)
    if np.logical_and(onil,nigel) == nigel:
        print(ans)
        exit()

Submission status: Runtime Error

Solution code:
n,u,v=map(int,input().split())
E=[[] for _ in range(n+1)]
for _ in range(n-1):
    a,b=map(int,input().split())
    E[a].append(b)
    E[b].append(a)
depth=[-1]*(n+1)
height=[-1]*(n+1)
def dsf_1(p,d):
    depth[p]=d
    for c in E[p]:
        if depth[c]==-1:
            dsf_1(c,d+1)
dsf_1(v,0)
def dsf_2(p):
    if len(E[p])==1 and p!=v:
        height[p]=0
    else:
        h=0
        for c in E[p]:
            if height[c]==-1 and depth[c]>depth[p]:
                dsf_2(c)
            h=max(h,height[c])
        h+=1
        height[p]=h
dsf_2(v)
d=depth[u]
dd=d//2+1
while d>dd:
    for c in E[u]:
        if depth[c]==d-1:
            u=c
            d-=1
            break
print(height[u]+depth[u]-1)

Submission status: Runtime Error

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

def get_input(inp):
    li = inp.split("\n")

    def inner():
        return li.pop(0)
    return inner

"""
from sys import setrecursionlimit
setrecursionlimit(100000)

from collections import Counter, deque
from heapq import heappush, heappop
from bisect import # docs.python.jp/3/library/bise…
from itertools import product, combinations

"""
##################################################
from tqdm import tqdm
from string import ascii_lowercase
INPUT = """9 6 1
1 2
2 3
3 4
4 5
5 6
4 7
7 8
8 9
"""
# 1:11:39
input = get_input(INPUT)

# -*- coding: utf-8 -*-


# -*- coding: utf-8 -*-
from heapq import heapify, heappop, heappush
from collections import defaultdict, deque
import sys
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

class LCA:
    # ダブリングver
    def __init__(self, G):
        self.N = len(G)
        self.base = int.bit_length(self.N)
        self.depth = [-1]*self.N
        self.parents = [[-1]*self.base for _ in range(self.N)]
        self.parents[0][0] = 0
        Q = [0]
        self.depth[0] = 0

        while Q:
            p = Q.pop()
            for q in G[p]:
                if self.depth[q] != -1:
                    continue
                self.parents[q][0] = p
                self.depth[q] = self.depth[p] + 1
                Q.append(q)

        for i in range(1, self.base):
            for j in range(self.N):
                self.parents[j][i] = self.parents[self.parents[j][i-1]][i-1]


    def find_ancestor(self, a, b):
        if self.depth[a] > self.depth[b]:
            a, b = b, a
        d = self.depth[b] - self.depth[a]
        f = 2**(self.base-1)
        c = b*1
        while f:
            if d&f:
                c = self.parents[c][int.bit_length(f)-1]
            f //= 2
        if c == a:
            return c, 1
        f = 2**(self.base-1)
        while f:
            na = self.parents[a][int.bit_length(f)-1]
            nc = self.parents[c][int.bit_length(f)-1]
            if na != nc:
                a = na*1
                c = nc*1
            f //= 2
        return self.parents[a][0], 0

    def distance(self, a, b):
        c, _ = self.find_ancestor(a, b)
        return self.depth[a] + self.depth[b] - 2*self.depth[c]

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

lca = LCA(G)

isleaf = [1]*N

Q = deque()
Q.append(0)
searched = [0]*N
searched[0] = 1
while Q:
    p = Q.popleft()
    for q in G[p]:
        if searched[q]:
            continue
        isleaf[p] = 0
        searched[q] = 1
        Q.append(q)

ans = 0
for i in range(N):
    if len(G[i]) > 1:
        continue
    uc = lca.find_ancestor(u, i)[0]
    vc = lca.find_ancestor(v, i)[0]
    
    if lca.depth[uc] >= lca.depth[vc]:
        ans = max(ans, lca.depth[v] + lca.depth[i] - 2*lca.depth[vc] - 1)
    else:
        if lca.distance(u, vc) < abs(lca.depth[v] - lca.depth[vc]) - 1:
            ans = max(ans, lca.depth[v] + lca.depth[i] - 2*lca.depth[vc] - 1)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n,u,v = map(int,input().split())
R = []
for _ in range(n):
    R.append([])
for _ in range(n-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    R[a].append(b)
    R[b].append(a)
taka = np.zeros(n)
taka[u]=1
aoki = np.zeros(n)
aoki[v]=1

def check(nige,oi):
    doko = nige.nonzero()
    flag = True
    for doko_i in doko[0]:
        if oi[doko_i]==0:
            flag = False
    return flag
    
    
t=1
while True:
    #taka
    #########
    next_taka = np.zeros(n)
    kiten = taka.nonzero()
    for kiten_i in kiten[0]:
        koho = R[kiten_i]
        for koho_i in koho:
            next_taka[koho_i]=1
    taka=next_taka
    #########
    if check(taka,aoki):
        break
        
    #aoki
    t+=1
    #########
    kiten = aoki.nonzero()
    for kiten_i in kiten[0]:
        koho = R[kiten_i]
        for koho_i in koho:
            aoki[koho_i]=1
    #########
    if check(taka,aoki):
        break
print(t)

Submission status: Runtime Error

Solution code:
class Tree:
  C, RL = {}, {}
  R, N, D, S, P = None, None, None, None, None
  def __init__(s, num):
    s.N = num
  def setC(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def makeRank(s, root):
    s.R = [0] * s.N
    s.R[root] = 1
    s.S = {}
    s.P = {}
    F = [root]
    s.D = 2
    while F != []:
      Ft = []
      for i in F:
        for j in s.C[i]:
          if s.R[j] == 0:
            s.R[j] = s.D
            Ft.append(j)
            if i not in s.S:
              s.S[i] = [j]
            else:
              s.S[i].append(j)
            s.P[j] = i

      s.D += 1
      F = Ft
  def getDeep(s, x):
    ans = 0
    if x in s.S:
      for i in s.S[x]:
        ans = max(ans, s.getDeep(i))
      return ans + 1
    else:
      return 0
  def getParent(s, x, n):
    if n == 0:
      return x
    return s.getParent(s.P[x], n - 1)
    

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

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

T = Tree(N)
for a, b in AB:
  T.setC(a - 1, b - 1)

T.makeRank(v - 1)
t = (T.R[u - 1] // 2) - 1
f = T.R[u - 1] % 2
k = T.getDeep(T.getParent(u - 1, t))
print(t + k + f)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from scipy.sparse.csgraph import shortest_path, dijkstra
from scipy.sparse import coo_matrix


def get_path(start, goal, pred):
    return get_path_row(start, goal, pred[start])


def get_path_row(start, goal, pred_row):
    path = []
    i = goal
    while i != start and pred_row[i] > 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]


read = sys.stdin.read
N, u, v, *AB = map(int, read().split())

a = AB[::2]
b = AB[1::2]
d = [1] * (N - 1)

graph = coo_matrix((d, (a, b)), shape=(N + 1, N + 1))
l, p = shortest_path(graph, directed=False, indices=u, return_predecessors=True)
dist = int(l[v]) // 2
s = get_path_row(u, v, p)[dist]
tour = shortest_path(graph, directed=False, indices=s)

print(int(max(i for i in tour if i != np.inf)) + dist - 1)

Submission status: Runtime Error

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):
            C[a] = cnt
            continue:
        
        DFS(a, x, cnt)


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

Submission status: Runtime Error

Solution code:
def main():
    n, u, v = map(int, input().split(" "))
    if u == v:
        return 0

    graphs = {}

    for node in range(1, n+1):
        graphs[node] = []

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

    def calc_depth(depths, max_depths, cur_node, parent, cur_depth, cur_path):
        if cur_node == u:
            nigeru_path = cur_path
        else:
            nigeru_path = None

        depths[cur_node] = cur_depth
        childs = graphs[cur_node].copy()
        childs.remove(parent)
        
        if len(childs) == 0:
            for node in cur_path:
                max_depths[node] = max(max_depths[node], cur_depth)

        for child in childs:
            depths, max_depths, nigeru_path2 = calc_depth(depths, max_depths, child, cur_node, cur_depth+1, cur_path+[child])
            if nigeru_path2 is not None:
                nigeru_path = nigeru_path2 
        return depths, max_depths, nigeru_path

    depths = [None for i in range(n+1)]
    max_depths = [-1 for i in range(n+1)]

    cur_depth = 0
    depths[v] = cur_depth
    childs = graphs[v]
    for child in childs:
        depths, max_depths, nigeru_path2 = calc_depth(depths, max_depths, child, v, cur_depth+1, [v, child])
        if nigeru_path2 is not None:
            nigeru_path = nigeru_path2 

    nigeru_dist = len(nigeru_path) - 1
    nigeru_dist2 = nigeru_dist

    for i, node in enumerate(sorted(nigeru_path2)):
        if i == 0:
            nigeru_max_depth = max_depths[u]
        elif nigeru_dist >= 1:
            nigeru_max_depth = max(nigeru_max_depth, max_depths[node])
        nigeru_dist -= 2
        if nigeru_dist < 1:
            break

    #print(depths, nigeru_path, max_depths)

    out = max(nigeru_max_depth -1, 0)
    return out


out = main()
print(out)

Submission status: Runtime Error

Solution code:
#%%
import numpy as np
n,nige,oni = map(int,input().split())
aa = np.zeros((n,n),dtype=bool)
for i in range(n-1):
    a,b = map(int,input().split())
    aa[a-1][b-1] = 1
    aa[b-1][a-1] = 1
nigel = np.zeros(n)
nigel[nige-1] = 1
onil = np.zeros(n)
onil[oni-1] = 1
ans = 0
for i in range(n-1):
    nigel = np.any(aa[nigel] == True,axis = 0)
    if np.logical_and(onil,nigel) == nigel:
        print(ans)
        return
    ans += 1
    onil = np.any(aa[onil] == True,axis = 0)
    if np.logical_and(onil,nigel) == nigel:
        print(ans)
        return

Submission status: Runtime Error

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


def search(parent, node, depth):
    chokudai_depth = 0
    max_depth = depth
    if node == u:
        chokudai_depth = depth
    if len(nodes[node]) == 1 and parent != -1:
        return max_depth, chokudai_depth
    for child in nodes[node]:
        if child != parent:
            _max_depth, _chokudai_depth = search(node, child, depth + 1)
            max_depth = max(max_depth, _max_depth)
            chokudai_depth = max(chokudai_depth, _chokudai_depth)
    return max_depth, chokudai_depth


max_depth, chokudai_depth = search(-1, v, 0)
print(max_depth - chokudai_depth + ((chokudai_depth) // 2) + 1 + (chokudai_depth % 2))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)

N, u, v=map(int, input().split())
path=[[] for i in range(N+1)]
for i in range(N-1):
  a, b=map(int, input().split())
  path[a].append(b)
  path[b].append(a)
  
def f(past, x, y, path):
  past.append(x)
  if x==y:
    return past
  else:
    n=len(path[x])
    if len(past)>1 and n==1:
      return past
    else:
      for i in range(n):
        if len(past)==1 or path[x][i]!=past[-2]:
          past=f(past, path[x][i], y, path)
      return past
  
shortpath=f([], v, u, path)
print(shortpath)
print(path)
path[u].remove(shortpath[-2])

def g(path, y, x, c):
  c+=1
  n=len(path[x])
  for i in range(n):
    if path[x][i]!=y:
      c=g(path, x, path[x][i], c)
  return c

k=len(path[u])
cand=0
for i in range(k):
  cand=max(cand, g(path, u, path[u][i], 0))
  
print(len(shortpath)-2+cand//2)

Submission status: Runtime Error

Solution code:
N, u, v = map(int,input().split())
edges=[list(map(int,input().split())) for i in range(N-1)]
root = [[] for i in range(N)]
ans = 100000000
for a,b in edges:
    root[a-1]+=b-1
    root[b-1]+=a-1
def chase_move(my_pos,opponent_pos):
    if opponent_pos in root[my_pos]:
        tmp = [opponent_pos]
        return tmp
    else:
        tmp = root[my_pos][:]
        return tmp

def escape_move(my_pos,opponent_pos):
    if opponent_pos in root[my_pos]:
        tmp = root[my_pos][:]
        tmp.remove(opponent_pos)
        return tmp
    else:
        tmp = root[my_pos][:]
        return tmp
        
def main(takahashi_pos,aoki_pos,cnt,turn):
    global ans
    if takahashi_pos==aoki_pos:
        if cnt<ans:
            ans=cnt
    if ans<=cnt:
        return
    if turn == 0:
        tmp = escape_move(takahashi_pos,aoki_pos)
        for i in tmp:
            main(i,aoki_pos,cnt,1)
    elif turn == 1:
        cnt+=1
        tmp = chase_move(aoki_pos,takahashi_pos)
        for i in tmp:
            main(takahashi_pos,i,cnt,0)
main(u,v,0,0)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
INFTY = 10**6
N,u,v = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
pre = {i:[] for i in range(1,N+1)}        
que = deque([(u,0)])
hist = [0 for _ in range(N+1)]
hist[u] = 1
dist = [0 for _ in range(N+1)]
dist[u] = 0
while que:
    x,d = que.popleft()
    for y in G[x]:
        if hist[y]==0:
            que.append((y,d+1))
            hist[y] = 1
            dist[y] = d+1
            pre[y].append(x)
w = dist[v]
cnt = (w-1)//2
a = u
i = 0
while i<cnt:
    a = pre[a][0]
    i += 1
b = pre[a][0]
que = deque([(a,0)])
hist = [0 for _ in range(N+1)]
hist[a] = 1
hist[b] = 1
dist2 = [0 for _ in range(N+1)]
while que:
    x,d = que.popleft()
    for y in G[x]:
        if hist[y]==0:
            que.append((y,d+1))
            hist[y] = 1
            dist2[y] = d+1
d = max(dist2)
if w%2==1:
    print(cnt+d)
else:
    print(cnt+d+1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import math
from collections import deque, defaultdict
import heapq
INF = float("inf")


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)
        pass

    def add_edge(self, from_, to_, weight=1):
        self.E[from_].append((to_, weight))
        self.E[to_].append((from_, weight))


def LCA_constract(g: Graph, root=0):
    N = g.N
    LN = int(math.log2(g.N))

    ###
    # 各頂点の親 parと各頂点の深さdepthを求める
    ###
    par = [INF]*N
    depth = [INF]*N

    que = deque()
    que.append([root, 0, None])
    while len(que) > 0:
        curr, dep, pre = que.popleft()
        par[curr] = pre
        depth[curr] = dep
        for n, w in g.E[curr]:
            if n != pre:
                que.append([n, dep+w, curr])

    ###
    # 祖先 ancの構築
    ###

    anc = [par]

    for i in range(LN):
        buf = [None]*N
        for j in range(N):
            if anc[i][j] == None:
                continue
            buf[j] = anc[i][anc[i][j]]
        anc.append(buf)
    return anc, depth


def LCA_query(anc, depth, g, u: int, v: int):
    N = len(depth)
    LN = int(math.log2(g.N))

    dd = depth[v] - depth[u]
    if dd < 0:
        u, v = v, u
        dd = -dd

    # assert depth[u] <= depth[v]
    for k in range(LN):
        if dd & 1:
            v = anc[k][v]
        dd >>= 1

    # assert depth[u] == depth[v]
    if u == v:
        return u

    for k in range(LN-1, -1, -1):
        pu = anc[k][u]
        pv = anc[k][v]
        if pu != pv:
            u = pu
            v = pv

    # assert anc[0][u] == anc[0][v]
    return anc[0][u]


INF = float("inf")


def solve(N: int, u: int, v: int, A: "List[int]", B: "List[int]"):
    g = Graph(N)
    for a, b in zip(A, B):
        g.add_edge(a-1, b-1)

    anc, depth = LCA_constract(g, v-1)

    visited = [False] * N
    ddhouse = [0]*N

    def dfs(f_, pre, dep):
        visited[f_] = True
        ddhouse[f_] = dep

        for t_, w in g.E[f_]:
            if t_ == pre or visited[t_] == True:
                continue
            dfs(t_, f_, dep+1)
        return

    dfs(v-1, -1, 0)

    visited = [False] * N
    ffhouse = [0]*N

    def dfs(f_, pre, dep):
        visited[f_] = True
        ffhouse[f_] = dep

        for t_, w in g.E[f_]:
            if t_ == pre or visited[t_] == True:
                continue
            dfs(t_, f_, dep+1)
        return

    dfs(u-1, -1, 0)
    m = 0

    for d, f in zip(ddhouse, ffhouse):
        if f >= d:
            continue
        else:
            m = max(d, m)
    print(max(m-1, 0))

    # while True:
    #     # 最も深いノード
    #     if current == N:
    #         print(0)
    #         return
    #     dep, node = ffhouse[current]
    #     lca = LCA_query(anc, ffhouse, g, node, u-1)
    #     # print("最も深いノード: ", node)
    #     # print("LCA ({}, {}) => {}".format(u-1, node, lca))

    #     # 到達可能か
    #     if (ddhouse[u-1] - dep) < dep:
    #         # 到達可能。移動すべし。
    #         # print("到達可能")
    #         break
    #     else:
    #         current += 1
    #         continue
    # print(dep-1)
    # return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    u = int(next(tokens))  # type: int
    v = int(next(tokens))  # type: int
    A = [int()] * (N - 1)  # type: "List[int]"
    B = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, u, v, A, B)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, u, v = map(int,input().split())
edges=[list(map(int,input().split())) for i in range(N)]
root = [[] for i in range(N-1)]
ans = 100000000
for a,b in edges:
    root[a-1]+=b-1
    root[b-1]+=a-1
def chase_move(my_pos,opponent_pos):
    if opponent_pos in root[my_pos]:
        tmp = [opponent_pos]
        return tmp
    else:
        tmp = root[my_pos][:]
        return tmp

def escape_move(my_pos,opponent_pos):
    if opponent_pos in root[my_pos]:
        tmp = root[my_pos][:]
        tmp.remove(opponent_pos)
        return tmp
    else:
        tmp = root[my_pos][:]
        return tmp
        
def main(takahashi_pos,aoki_pos,cnt,turn):
    global ans
    if takahashi_pos==aoki_pos:
        if cnt<ans:
            ans=cnt
    if ans<=cnt:
        return
    if turn == 0:
        tmp = escape_move(takahashi_pos,aoki_pos)
        for i in tmp:
            main(i,aoki_pos,cnt,1)
    elif turn == 1:
        cnt+=1
        tmp = chase_move(aoki_pos,takahashi_pos)
        for i in tmp:
            main(takahashi_pos,i,cnt,0)
main(u,v,0,0)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

input = sys.stdin.readline
n, u, v = map(int, input().split())

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

memo = [[0, 0] for i in range(n)]

def dfs(cur, pre, dep, p):
    stack = deque([[cur, pre]])
    memo[cur][p] = dep
    while stack:
        cur, pre = stack.pop()
        for e in E[cur]:
            if e != pre:
                dfs(e, cur, dep + 1, p)

dfs(u - 1, - 1, 0, 0)
dfs(v - 1, -1, 0, 1)

# print(memo)
ans = 0
for a, b in memo:
    ans = max(ans, b - 1)
print(ans)

Submission status: Runtime Error

Solution code:
class Tree:
  C, RL = {}, {}
  R, N, D, S, P = None, None, None, None, None
  def __init__(s, num):
    s.N = num
  def setC(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def makeRank(s, root):
    s.R = [0] * s.N
    s.R[root] = 1
    s.RL[1] = [root]
    s.S = {}
    s.P = {}
    F = [root]
    s.D = 2
    while F != []:
      Ft = []
      s.RL[s.D] = []
      for i in F:
        for j in s.C[i]:
          if s.R[j] == 0:
            s.R[j] = s.D
            Ft.append(j)
            s.RL[s.D].append(j)
            if i not in s.S:
              s.S[i] = [j]
            else:
              s.S[i].append(j)
            s.P[j] = i

      s.D += 1
      F = Ft
  def getDeep(s, x):
    ans = 0
    if x in s.S:
      for i in s.S[x]:
        ans = max(ans, s.getDeep(i))
      return ans + 1
    else:
      return 0
  def getParent(s, x, n):
    if n == 0:
      return x
    return s.getParent(s.P[x], n - 1)
    

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

T = Tree(N)
for a, b in AB:
  T.setC(a - 1, b - 1)

T.makeRank(v - 1)
t = (T.R[u - 1] // 2) - 1
f = T.R[u - 1] % 2
k = T.getDeep(T.getParent(u - 1, t))
print(t + k + f)