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())
inf = 10**9
d = [[inf for i in range(N+1)] for j in range(N+1)]
G = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
    d[a][b] = 1
    d[b][a] = 1
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
warshall_floyd(d)
n = d[u][v]

a = n//2
if n % 2 == 0:
    for i in range(N):
        if (d[u][i] == a) & (d[v][i] == a)
            s = i
            break
for j in G[s]:
    if d[u][j] == a-1:
        u = j
    if d[v][j] == a-1:
        v = j
if n % 2 == 0:
    G[u].remove(s)
else:
    G[u].remove(v)
ans = (n-1)//2

F = [u]
list = []
while len(F) > 0:
    x = F.pop(0)
    list.append(x)
    for j in G[x]:
        if j not in F:
            if j not in list:
                F.append(j)
m = 0
for i in list:
    m = max(m,i)
ans += m + ((n-1)%2)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N,u,v = map(int,input().split(' '))
l = [None]*N
for i in range(N-1):
    l[i] = list(map(int, input().split()))

MAP = {}
for i in range(N):
    if l[i]==None:
        continue
    a,b = l[i]
    if a in MAP:
        MAP[a].append(b)
    else:
        MAP[a] = [b]
    if b in MAP:
        MAP[b].append(a)
    else:
        MAP[b] = [a]

#Tがたどり着くのにかかる手数
t_MAP = [0]*(N+1)
cost = 0

def t_dfs(n,c):
    t_MAP[n] = c
    c += 1
    if n in MAP:
        for j in MAP[n]:
            if t_MAP[j]==0 and j!=u:
                t_dfs(j,c)
t_dfs(u,cost)

a_visited = [False]*(N+1)
break_even = False
pre_tcost = 10**5
ANS = [0]
def a_dfs(n,c):
    a_visited[n] = True
    t_cost = t_MAP[n]
    if t_cost>c:
        if t_cost>pre_tcost:
            return
    ANS[0] = max(c,ANS[0])
    c += 1
    if n in MAP:
        for j in MAP[n]:
            if not a_visited[j]:
                a_dfs(j,c)
a_visited[v] = True
a_dfs(v,cost)
print(ANS[0]-1)

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:
    if b - a > 1:
        ans = max(ans, b - 1)
print(ans)

Submission status: Runtime Error

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

DU = [-1 for _ in range(N)]  
DV = [-1 for _ in range(N)]
def dfs(p,c,D):
  D[p] = c
  for q in E[p]:
    if D[q] == -1:
      dfs(q,c+1,D)
dfs(u,0,DU)
dfs(v,0,DV)
#print(DU)
#print(DV)
DX = []
for du,dv in zip(DU,DV):
  DX.append(dv-du)
#print(DX)
#print(max(max(DX)-1,0))
mx = max(DX)
#print(DX.index(mx))
if DU[DX.index(mx)]%2 == 1:
  print(max(mx,0))
else:
  print(max(mx-1,0))

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 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(len(path))

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 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)

Submission status: Runtime Error

Solution code:
def jisin(gen,mae,huka):
    hukasa[gen]=huka
    for c in tens[gen]:
        if(c!=mae):
            jisin(c,gen,huka+1)
    return

def kyokudai(gen,mae):
    dai=0
    if(len(tens[gen])==1 and mae!=-1):
        dai=hukasa[gen]
        #print(dai)
    else:
        for c in tens[gen]:
            if(c!=mae):
                dai=max(dai,kyokudai(c,gen))
    saisin[gen]=dai
    #print(gen,dai)
    return dai

def oikake(gen):
    miti.append(gen)
    if(hukasa[gen]==0):
        return
    for c in tens[gen]:
        if(hukasa[c]==hukasa[gen]-1):
            oikake(c)

n,u,v=map(int,input().split())
u-=1
v-=1
tens=[[]for i in range(n)]
hukasa=[0]*n
saisin=[0]*n

for i in range(n-1):
    s,t=map(int,input().split())
    tens[s-1].append(t-1)
    tens[t-1].append(s-1)

#print(tens)

jisin(v,-1,0)
#print(hukasa)
kyokudai(v,-1)
#print(saisin)

miti=[]
oikake(u)
l=len(miti)-1
#print(miti)
#print(l)

ans=saisin[miti[l//2]]
print(ans-1)

Submission status: Runtime Error

Solution code:
from heapq import heapify, heappop, heappush

N, u, v = list(map(int, input().split()))
A = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    _u, _v = list(map(int, input().split()))
    A[_u].append(_v)
    A[_v].append(_u)

# 距離の計算 (青木)
INF = int(1e18)
dist = {_v: INF for _v in range(1, N + 1)}
dist[v] = 0
queue = [(0, v)]
heapify(queue)
while len(queue) > 0:
    d, node = heappop(queue)
    for ngv in A[node]:
        if dist[ngv] > d + 1:  # INF:
            dist[ngv] = d + 1
            heappush(queue, (d + 1, ngv))

# 青木の距離が最短
# 高橋の距離は青木の距離+1かどうか
# check V ∈ {1,...,N} is reachable by N-1 step
def reachable(node, value):
    if value < 0:
        return False
    # print("call ", node, " ", value)
    if node == u:
        return True
    else:
        flag = False
        for ng in A[node]:
            if reachable(ng, value - 1):
                flag = True
                break
        return flag

# 最大の距離
max_v = -1
for n in range(1, N+1):
    if reachable(n, dist[n] + 1):
        max_v = max(dist[n], max_v)
print(max_v - 1)

Submission status: Runtime Error

Solution code:
def f_playing_tag_on_tree():
    N, U, V = [int(i) for i in input().split()]
    Edges = [[int(i) for i in input().split()] for j in range(N - 1)]

    tree = [[] for _ in range(N)]
    for u, v in Edges:
        tree[u - 1].append(v - 1)
        tree[v - 1].append(u - 1)

    depth = [-1] * N

    def dfs(current, parent, dep):
        depth[current] = dep

        for child in tree[current]:
            if child == parent:
                continue
            dfs(child, current, dep + 1)
        return None
    dfs(V - 1, -1, 0)
    return max(depth) - 1

print(f_playing_tag_on_tree())

Submission status: Runtime Error

Solution code:
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: 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)

    ffhouse = sorted(zip(ddhouse, range(N)), reverse=True)
    current = 0
    # print(ffhouse)

    while True:
        # 最も深いノード
        if current == N:
            print(0)
            return
        dep, node = ffhouse[current]
        lca = LCA_query(anc, ddhouse, 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:
import sys
n, u, v = [int(i) for i in sys.stdin.readline().split()]
u -= 1
v -= 1
graph = {i : [] for i in range(n)}
for i in range(n-1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

distance = 0
stack = [(u, 0)]
already = set()
parent = [i for i in range(n)]
while len(stack) > 0:
    cur, dis = stack.pop(-1)
    already.add(cur)
    for _next in graph[cur]:
        if _next in already:
            continue
        parent[_next] = cur
        if _next == v:
            distance = dis + 1
            break
        stack.append((_next, dis + 1))
cur = v
path = []
while cur != u:
    path.append(cur)
    cur = parent[cur]

path_dict = {j : i for i, j in enumerate(path)}
already = set()

def dfs(ind, cur_dis):
    res = 0
    already.add(ind)
    for _next in graph[ind]:
        parent[_next] = ind
        if _next in already:
            continue
        if _next in path:
            if path_dict[_next] <= cur_dis:
                continue
            else:
                res = max(res, dfs(_next, cur_dis + 1) - 1)
        else:
            res = max(res, dfs(_next, cur_dis + 1) + 1)
    return res

res = dfs(u, 0)
if res == 0:
    print(distance - 1)
else:
    print(distance + res - distance % 2)

Submission status: Runtime Error

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


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

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)

    ffhouse = sorted(zip(ddhouse, range(N)), reverse=True)
    current = 0
    # print(ffhouse)

    while True:
        # 最も深いノード
        dep, node = ffhouse[current]
        lca = LCA_query(anc, ddhouse, 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:
def dfs(cur, par, g, d):
    pars[cur] = par
    for to in g[cur]:
        if to == par:
            continue
        d[to] = d[cur]+1
        md[cur] = max(md[cur], dfs(to, cur, g, d)+1)
    return md[cur]


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

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 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)

import math
_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 = False
    for v in graph[cur]:
        if not visited[v] and not path_aoki[v]:
            f = True
            dfs2(v, path + [v])
    if not f:
        paths.append(path)

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

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

path_aoki = _path_aoki[:-1] + longest

print(len(path_aoki) - 2)

Submission status: Runtime Error

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


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

Submission status: Runtime Error

Solution code:
n,u,v = map(int,input().split())
l = [[] for _ in range(n+1)]
x = [0 for _ in range(n+1)]
y = [0 for _ in range(n+1)]
for i in range(n-1):
  ai,bi = map(int,input().split())
  l[ai].append(bi)
  l[bi].append(ai)
def s(p,a,m):
  global x
  for li in l[a]:
    if li != p:
      x[li] = m+1
      s(a,li,m+1)
  return
def t(p,a,m):
  global y
  for li in l[a]:
    if li != p:
      y[li] = m+1
      t(a,li,m+1)
  return
s(-1,u,0)
t(-1,v,0) 
mx = 0
for i in range(1,n+1):
  if x[i] < y[i]:
    if y[i] -1 > mx:
      mx = y[i]-1
print(mx)

Submission status: Runtime Error

Solution code:
import sys
#input = sys.stdin.readline
from collections import deque
N, u, v = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
v-=1
u-=1
que = deque([v])
par = [-1]*N
depth = [-1]*N
depth[v] = 0
while que:
    i = que.popleft()
    d = depth[i]
    for nv in G[i]:
        if depth[nv]>=0:
            continue
        depth[nv] = d+1
        par[nv] = i
        que.append(nv)
d = depth[u]
now = u
m = 0
que = deque([now])
while que:
    i = que.pop()
    m = max(m, depth[i])
    for nv in G[i]:
        if depth[nv]<depth[i]:
            continue
        que.append(nv)
for i in range(d//2):
    pp = par[now]
    que = deque([p])
    while que:
        i = que.pop()
        m = max(m, depth[i])
        for nv in G[i]:
            if depth[nv]<depth[i] or nv == pp:
                continue
            que.append(nv)
    now = pp
print(m-1)

Submission status: Runtime Error

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

Submission status: Runtime Error

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


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

Submission status: Runtime Error

Solution code:
n = int(input())

if n < 2:
  print(1)
elif n % 2 == 1:
  print(0)
  exit()
else:
  if n > 9:
    a = n // 10
  else:
    print(0)
    exit()
  
  def calc(a,n):
    num = 50
    while n > num:
      a += n//num
      num *= 5
    return a
  
  print(calc(a,n))

Submission status: Runtime Error

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


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

Submission status: Runtime Error

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


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

Submission status: Runtime Error

Solution code:
N,u,v = map(int,input().split())
inf = 10**9
d = [[inf for i in range(N+1)] for j in range(N+1)]
G = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
    d[a][b] = 1
    d[b][a] = 1
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
warshall_floyd(d)
ans = 0
while u != v:
    m = 0
    for i in G[u]:
        if d[u][i] > m:
            m = d[u][i]
            a = i
    u = a
    if u != v:
        m = inf
        for j in G[v]:
            if d[v][j] < m:
                m = d[v][j]
                b = j
        v = b
        ans += 1
print(ans)

Submission status: Runtime Error

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

root=[[] for i in range(n)]
for a,b in edge:
    root[a].append(b)
    root[b].append(a)

def dfs(node,depth,par,dp):
    for vertex in root[node]:
        if vertex == par:
            continue
        dp[vertex]=depth+1
        dfs(vertex,depth+1,node,dp)
dfs(u,0,u,dp1)
dfs(v,0,v,dp2)
buf=-1
buf1=0
#print(dp1,dp2,root)
for i in range(n):
    if dp1[i]<dp2[i] and dp2[i]>buf:
        buf=dp2[i]
        buf1=dp1[i]
print(buf-1)

Submission status: Runtime Error

Solution code:
n, u, v = [int(x) for x in input().split()]
adj     = [[] for _ in range(0, n + 1)]
vs      = [False] * (n + 1)

for i in range(1, n):
	a, b = [int(x) for x in input().split()]
	adj[a].append(b)
	adj[b].append(a)
	
def dfs(i, d, n):
	if i == d:
		return n
	
	vs[i] = True
	
	for j in adj[i]:
		r = dfs(j, d, n + 1)
		if r is not None:
			return r
		
	vs[i] = False
	
	return None
	
r = dfs(u, v, 0)

print(r)