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: Accepted

Solution code:
from collections import deque


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

tree = [[] for i in range(n)]
for i in range(n - 1):
    a, b = info[i]
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

v -= 1
u -= 1

root = u
visited = [False] * n
q = deque([root])
visited[root] = True
new_tree = [[] for i in range(n)]

while q:
    pos = q.pop()
    for next_pos in tree[pos]:
        if visited[next_pos]:
            continue
        visited[next_pos] = True
        if next_pos != v:
            q.append(next_pos)
        new_tree[pos].append(next_pos)
        new_tree[next_pos].append(pos)

is_leaf = [False] * n
for i in range(n):
    if len(new_tree[i]) == 1:
        is_leaf[i] = True
        
time = [-1] * n
root = v
time[root] = 0
q = deque([root])
while q:
    pos = q.pop()
    for next_pos in new_tree[pos]:
        if time[next_pos] >= 0:
            continue
        time[next_pos] = time[pos] + 1
        q.append(next_pos)
#print(time)

time2 = [-1] * n
root = u
time2[root] = 0
q = deque([root])
while q:
    pos = q.pop()
    for next_pos in new_tree[pos]:
        if time2[next_pos] >= 0:
            continue
        time2[next_pos] = time2[pos] + 1
        q.append(next_pos)
#print(is_leaf)
#print(time)
#print(time2)
can_reach = [False] * n
for i in range(n):
    if time[i] > time2[i] and is_leaf[i]:
        can_reach[i] = True
    
ans = 0
for i in range(n):
    if can_reach[i]:
        ans = max(ans, time[i] - 1)
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 5)


def dfs(v, parent, depth):
    parents[v] = parent
    self_depths[v] = depth
    sd = 0
    for u in links[v]:
        if u == parent:
            continue
        res = dfs(u, v, depth + 1)
        sd = max(sd, res + 1)

    subtree_depths[v] = sd
    return sd


def solve(u):
    ans = 0
    catch = self_depths[u] // 2
    while self_depths[u] > catch:
        ans = max(ans, self_depths[u] + subtree_depths[u] - 1)
        u = parents[u]
    return ans


n, u, v = map(int, input().split())
u -= 1
v -= 1
links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)

parents = [-1] * n
self_depths = [0] * n
subtree_depths = [0] * n
dfs(v, -1, 0)
# print(parents)
# print(self_depths)
# print(subtree_depths)
print(solve(u))

Submission status: Accepted

Solution code:
n, u, v = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
d1 = [-1] * n
d1[u - 1] = 0
s = [u - 1]
while s:
    d = s.pop()
    for node in g[d]:
        if d1[node] == -1:
            s.append(node)
            d1[node] = d1[d] + 1
d2 = [-1] * n
d2[v - 1] = 0
s = [v - 1]
while s:
    d = s.pop()
    for node in g[d]:
        if d2[node] == -1:
            s.append(node)
            d2[node] = d2[d] + 1
m = 0
mi = 0
for i in range(n):
    if d1[i] < d2[i]:
        if m < d2[i]:
            m = d2[i]
            mi = i
print(m - 1)

Submission status: Accepted

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

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

que = deque()
que.append(u0)
du = [-1] * (N+1)
du[u0] = 0
while que:
    v = que.popleft()
    for u in adj[v]:
        if du[u] == -1:
            du[u] = du[v] + 1
            que.append(u)

que = deque()
que.append(v0)
dv = [-1] * (N+1)
dv[v0] = 0
while que:
    v = que.popleft()
    for u in adj[v]:
        if dv[u] == -1:
            dv[u] = dv[v] + 1
            que.append(u)

duv = [du[i] - dv[i] for i in range(N+1)]

ans = 0
#flg = 1 if duv[v] % 2 == 1 else 0
for i in range(1, N+1):
    if duv[i] < 0:
        ans = max(ans, dv[i] - 1)
print(ans)

Submission status: Accepted

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

N,u,v=map(int,input().split())
E=[tuple(map(int,input().split())) for i in range(N-1)]

EDGE=[[] for i in range(N+1)]

for x,y in E:
    EDGE[x].append(y)
    EDGE[y].append(x)

from collections import deque
T=[-1]*(N+1)

Q=deque()
Q.append(u)
T[u]=0

while Q:
    x=Q.pop()
    for to in EDGE[x]:
        if T[to]==-1:
            T[to]=T[x]+1
            Q.append(to)

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

Q=deque()
Q.append(v)
A[v]=0

while Q:
    x=Q.pop()
    for to in EDGE[x]:
        if A[to]==-1:
            A[to]=A[x]+1
            Q.append(to)


OK=[0]*(N+1)

for i in range(N+1):
    if T[i]<A[i]:
        OK[i]=1

ANS=0
for i in range(N+1):
    if OK[i]==1:
        ANS=max(ANS,A[i])

print(max(0,ANS-1))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
N, u, v = map(int, input().split())
u, v = u-1, v-1
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

P = [-1] * N
Q = deque([v])
R = []
while Q:
    i = deque.popleft(Q)
    R.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            deque.append(Q, a)

DE = [0] * N
for i in R[1:]:
    DE[i] = DE[P[i]] + 1

D = [0] * N
for i in R[::-1]:
    D[i] = max([D[j] for j in X[i]] + [DE[i]])

i = u
ma = D[i]
while True:
    i = P[i]
    if DE[i] * 2 <= DE[u]: break
    ma = max(ma, D[i])

print(ma - 1)

Submission status: Accepted

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

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

V = [-1] * (n+1)
W = [-1] * (n+1)


M = [[] for i in range(n+1)]
for i in range(n-1):
    M[C[i][0]].append(C[i][1])
    M[C[i][1]].append(C[i][0])


Q = [[u,0]]
s = 0
V[u] = 0
while s < len(Q):
    i = Q[s][0]
    d = Q[s][1]
    for x in M[i]:
        if V[x] == -1:
            V[x] = d+1
            Q.append([x,d+1])
    s += 1

Q = [[v,0]]
s = 0
W[v] = 0
while s < len(Q):
    i = Q[s][0]
    d = Q[s][1]
    for x in M[i]:
        if W[x] == -1:
            W[x] = d+1
            Q.append([x,d+1])
    s += 1

# print(V,W)

ans = 0
for i in range(len(V)):
    if W[i] > V[i]:
        ans = max(ans,W[i])
print(ans-1)

Submission status: Accepted

Solution code:
from collections import deque

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

AB = []
dic = {}

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

    if a not in dic:
        dic[a] = []
    if b not in dic:
        dic[b] = []

    dic[a].append(b)
    dic[b].append(a)

q = deque([u])

tk = [float("inf")] * N
tk[u] = 0

while len(q) > 0:

    now = q.popleft()

    for i in dic[now]:

        if tk[i] > tk[now] + 1:
            tk[i] = tk[now] + 1
            q.append(i)

#print (dic)

ao = [float("inf")] * N
q = deque([v])
ao[v] = 0

while len(q) > 0:

    now = q.popleft()

    for i in dic[now]:

        if ao[i] > ao[now] + 1:
            ao[i] = ao[now] + 1
            q.append(i)

ans = 0
for i in range(N):

    if ao[i] > tk[i]:
        ans = max(ans , ao[i] - 1)

print (ans)

Submission status: Accepted

Solution code:
def examA():
    AB = [I() for _ in range(2)]
    for i in range(1,4):
        if not i in AB:
            ans = i
            break
    print(ans)
    return

def examB():
    N = I()
    S,T = LSI()
    ans = ""
    for i in range(N):
        ans += S[i]+T[i]
    print(ans)
    return

def gcd(x, y):
    if y == 0:
        return x
    while y != 0:
        x, y = y, x % y
    return x
def lcm(x, y):
    return x * y // gcd(x, y)
def examC():
    A, B = LI()
    ans = lcm(A,B)
    print(ans)
    return

def examD():
    N = I()
    A = LI()
    ans = N; cur = 1
    for a in A:
        if cur==a:
            ans -=1
            cur +=1
    if ans==N:
        ans = -1
    print(ans)
    return

def examE():
    N = I()
    ans = 0
    if N%2==0:
        N //=2
        while(N>0):
            ans +=N//5
            N //=5
    print(ans)
    return


def bfs(n,e,fordfs):
    #点の数、スタートの点、有向グラフ
    W = [-1]*n
    #各点の状態量、最短距離とか,見たかどうかとか
    W[e] = 0
    que = deque()
    que.append(e)
    len = [float("inf")]*n
    len[e] = 0
    while que:
        now = que.popleft()
        nowv = W[now]
        nowlen = len[now]
        for ne in fordfs[now]:
            if nowv == W[ne]:
                #ループが嫌な時
                return -1
            elif W[ne] == -1:
                W[ne] = (nowv+1) % 2
                len[ne] = nowlen+1
                que.append(ne)
    return len
def examF():
    N, u, v = LI()
    V = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        V[a-1].append(b-1)
        V[b-1].append(a-1)
    La = bfs(N,u-1,V)
    Lb = bfs(N,v-1,V)
#    print(La)
#    print(Lb)
    ans = 0
    for i in range(N):
        if La[i]>Lb[i]:
            continue
        ans = max(Lb[i],ans)
    print(ans-1)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examF()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def lca(x,y):
        k = depth[x] - depth[y]
        while k > 0:
            x = par[x][int(math.log(k,2))]
            k = depth[x] - depth[y]
        k = -k
        while k > 0:
            y = par[y][int(math.log(k,2))]
            k = depth[y] - depth[x]
        if x == y:
            return x
        for i in range(17)[::-1]:
            if par[x][i] != par[y][i]:
                x = par[x][i]
                y = par[y][i]
        return par[x][0]
    n,s,t = LI()
    s -= 1
    t -= 1
    v = [[] for i in range(n)]
    f = [0]*n
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
        f[a] += 1
        f[b] += 1
    l = []
    for i in range(n):
        if f[i] == 1:
            l.append(i)
    par = [[] for i in range(n)]
    par[t].append(t)
    depth = [-1]*n
    depth[t] = 0
    q = deque([t])
    while q:
        x = q.popleft()
        for y in v[x]:
            if depth[y] < 0:
                depth[y] = depth[x]+1
                q.append(y)
                par[y].append(x)
    d = [-1]*n
    d[s] = 0
    q = deque([s])
    while q:
        x = q.popleft()
        for y in v[x]:
            if d[y] < 0:
                d[y] = d[x]+1
                q.append(y)
    for i in range(16):
        for x in range(n):
            par[x].append(par[par[x][i]][i])
    l.sort(key = lambda x:-depth[x])
    for i in l:
        x = lca(i,s)
        if d[x] < depth[x]:
            break
    print(depth[i]-1)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import itertools, heapq, bisect
from collections import defaultdict as ddic, deque, Counter

rr = raw_input
rri = lambda: int(raw_input())
rrm = lambda: map(int, raw_input().split())
MOD = 10 ** 9 + 7

###

def solve(N, T, A, graph):
    if T == A: return 0
    stack = [(A, None)]
    seen = {A}
    back = {}
    while stack:
        node, par = stack.pop()
        back[node] = par
        for nei in graph[node]:
            if nei != par:
                if nei not in seen:
                    stack.append((nei, node))
                    seen.add(nei)

    path = [T]
    while back[path[-1]] is not None:
        path.append(back[path[-1]])

    def bfs(source, par):
        queue = deque([(source, par, 0)])
        d=  0
        while queue:
            node, par, d = queue.popleft()
            for nei in graph[node]:
                if nei != par:
                    queue.append((nei, node, d+1))
        return d
    
    ans = 0
    i = 0
    j = len(path) - 1
    while i + 2 < j:
        i += 1
        j -= 1
        ans += 1
    # now T goes away from A
    #print "!", path[i], path[i+1], ans
    ans += j-i-1
    ans += bfs(path[i], path[i+1])
    return ans


N, T, A = rrm()
T -= 1; A -= 1
graph = [[] for _ in xrange(N)]

for _ in xrange(N-1):
    a, b = rrm()
    a -= 1; b -= 1
    graph[a].append(b)
    graph[b].append(a)

print solve(N, T, A, graph)

Submission status: Runtime Error

Solution code:
class LCA(object):
    def __init__(self, n, root, edges, decrement=True):
        """
        :param n: 頂点数
        :param root: 木の根
        :param edges: 辺のリスト
        :param decrement:

        :param self.depth: rootを根とした時の各頂点の深さ
        """
        self.n = n
        self.decrement = decrement
        self.root = root - self.decrement
        self.edges = [set() for _ in range(self.n)]
        for x, y in edges:
            self.add_edge(x,y)
        self.k_max = (self.n - 1).bit_length()
        self.depth = [-1 if i != self.root else 0 for i in range(self.n)]
        self.doubling = [[-1] * self.n for _ in range(self.k_max)]
        self.parent = [-1]*self.n
        self.dfs()
        for i in range(1, self.k_max):
            for k in range(self.n):
                if self.doubling[i - 1][k] != -1:
                    self.doubling[i][k] = self.doubling[i - 1][self.doubling[i - 1][k]]

    def add_edge(self, x, y):
        """
        後から追加した場合は update() をする
        """
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        self.edges[y].add(x)

    def update(self):
        self.depth = [-1 if i != self.root else 0 for i in range(self.n)]
        self.doubling = [[-1] * self.n for _ in range(self.k_max)]
        self.dfs()
        for i in range(1, self.k_max):
            for k in range(self.n):
                if self.doubling[i - 1][k] != -1:
                    self.doubling[i][k] = self.doubling[i - 1][self.doubling[i - 1][k]]


    def dfs(self):
        next_set = [self.root]
        while next_set:
            p = next_set.pop()
            for q in self.edges[p]:
                if self.depth[q] == -1:
                    self.depth[q] = self.depth[p] + 1
                    self.doubling[0][q] = p
                    next_set += [q]

    def get(self, u, v):
        """
        :return: u と v の最近共通祖先の頂点番号を返す
        """
        if self.decrement:
            u -= 1
            v -= 1
        if self.depth[v] < self.depth[u]:
            u, v = v, u

        for i in range(self.k_max):
            """ v を u の位置まで遡らせる """
            if (self.depth[v] - self.depth[u]) >> i & 1:
                v = self.doubling[i][v]
        if v == u:
            """ v の祖先が u だった場合"""
            return u + self.decrement

        for i in range(self.k_max-1, -1, -1):
            """ k = 2**(k_max-1), ..., 2**0 について、 
            「k個先を確認して共通祖先でないなら u1,v1 をk個先に移動」ということを繰り返す"""
            parent_u, parent_v = self.doubling[i][u], self.doubling[i][v]
            if parent_u != parent_v:
                u, v = parent_u, parent_v
        return self.doubling[0][u] + self.decrement

    def distance(self, u, v):
        """
        :return: u と v の最短距離を求める
        備考: 経路復元をしようとすると O(E)かかるので、経路復元が必要な場合は dfs を用いるとよい
        """
        lca_at = self.get(u,v)
        if self.decrement:
            u -= 1
            v -= 1
            lca_at -= 1
        return self.depth[u] + self.depth[v] - 2*self.depth[lca_at]

    def distance_list(self, start=1, save=False):
        """
        :param start: スタート地点
        :return: スタート地点から各点への距離のリスト
        """
        dist = [-1]*self.n
        if self.decrement:
            start -= 1
        if not save:
            self.parent = [-1] * self.n
        p, t = start, 0
        self.parent[p] = -2
        dist[p] = 0
        next_set = deque([(p, t)])

        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                if self.parent[q] != -1:
                    continue
                if q == xx-1:
                    continue
                dist[q] = t + 1
                self.parent[q] = p
                next_set.append((q, t + 1))
        return dist

    def most_distant_point(self, start=1, save=False):
        """
        計算量　O(N)
        :return: (start から最も遠い頂点, 距離)
        """
        if not save:
            self.parent = [-1] * self.n
        res = (start - self.decrement, 0)
        temp = 0
        for i, dist in enumerate(self.distance_list(start, save=save)):
            if dist > temp:
                temp = dist
                res = (i + self.decrement, dist)
        return res

#################################################################################################
import sys
from collections import deque
input = sys.stdin.readline

N, u, v = map(int, input().split())
edges = []
for _ in range(N-1):
    x, y = map(int, input().split())
    edges.append((x,y))
xx = -2
lca = LCA(N, 1, edges, decrement=True)
p = lca.get(u,v)
lu, lv = lca.depth[u-1] - lca.depth[p-1], lca.depth[v-1] - lca.depth[p-1]
if lu >= lv:
    q, _ = lca.most_distant_point(v)
    print(lca.distance(q,v)-1)
    exit()
else:
    L = (lu+lv)//2
    cnt = 0
    lca.distance_list()
    if lca.depth[u-1] >= lca.depth[v-1]:
        a = u-1
        while cnt < L:
            a = lca.parent[a]
            cnt += 1
        xx, s = lca.parent[a], a
    else:
        a = v-1
        while cnt < L+1:
            a = lca.parent[a]
            cnt += 1
        xx, s = a, lca.parent[a]
    q, _ = lca.most_distant_point(s)
    print(lca.distance(q,v)-1)
    exit()

Submission status: Runtime Error

Solution code:
from collections import deque
N, u, v = map(int, input().split())

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


def bfs(s):
    dist = [-1] * (N + 1)
    dist[s] = 0
    d = deque([s])
    while len(d) > 0:
        v = d.popleft()
        for w in edge[v]:
            if dist[w] < 0:
                dist[w] = dist[v] + 1
                d.append(w)
    return dist


tkhs = bfs(u)
aok = bfs(v)
ans = 0
for i in range(1, N + 1):
    if tkhs[i] < aok[i]:
        ans = max(ans, aok[i] - 1)
print(ans)

Submission status: Runtime Error

Solution code:
N, u, v = list(map(int, input().split()))
class ver:
  def __init__(self, x):
    self.__x = x
    self.__p = -1
    self.__c = []
    self.__d = -1
    
  def get_p(self):
    return self.__p
  
  def set_p(self, x):
    self.__p = x
    
  def get_c(self):
    return self.__c
  
  def add_c(self, x):
    self.__c.append(x)
  
  def pop_c(self, x):
    return self.__c.pop(self.__c.index(x))
  
  def set_d(self, d):
    self.__d = d
    
  def get_d(self):
    return self.__d
    
class tree:
  def __init__(self, N, v):
    self.__N = N
    self.__a = [ver(i) for i in range(N+1)]
    self.__root = v
    
  def find_root(self, x):
    if self.__a[x].get_p() == -1:
      return x
    else:
      return self.__find(self.__a[x].get_p())
    
  def leaves(self):
    res = []
    for i, var in enumerate(self.__a):
      if not var.get_c():
        res.append(i)
    return res
  
  def add_(self, x, y):
    self.__a[x].add_c(y)
    self.__a[y].add_c(x)
  
  def change_root(self, v, d):
    self.__a[v].set_d(d)
    d += 1
    for i in self.__a[v].get_c():
      self.__a[i].set_p(self.__a[i].pop_c(v)) 
      self.change_root(i, d)
      
  def show_p(self):
    res = []
    for i in self.__a:
      res.append(i.get_p())
    return res
  
  def show_d(self):
    res = []
    for i in self.__a:
      res.append(i.get_d())
    return res
  
t = tree(N, v)
for _ in range(N-1):
  x, y = map(int, input().split())
  t.add_(x, y)
t.change_root(v, 0)
print(t.show_p())
print(t.show_d())

Submission status: Runtime Error

Solution code:
N,T,A = map(int,input().split()); INF = float("inf")
T-=1;A-=1 #0index
G = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int,input().split())
  a-=1;b-=1 #0index
  G[a].append(b);G[b].append(a)

disT = [INF for _ in range(N)]; disT[T] = 0
disA = [INF for _ in range(N)]; disA[A] = 0

def dfs(v, L):
  for u in G[v]:
    if L[u] != INF:
      continue
    L[u] = L[v]+1
    dfs(u,L)
dfs(T,disT)
dfs(A,disA)
#print(disT)
#print(disA)
ans = 0
for i in range(N):
  if disT[i] < disA[i]:
    ans = max(ans,disA[i]-1)
print(ans)

Submission status: Runtime Error

Solution code:
n, u, v = map(int, input().split())
# よりたかはしくんが早く辿り着ける葉のうち、青木君から最も遠いで
u -= 1
v -= 1

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

INF = 1 << 30
t = [INF] * n
a = [INF] * n

t[u] = 0
a[v] = 0


def dfs(v, p, d):
    for nv in g[v]:
        if nv == p:
            continue
        if d[nv] == INF:
            d[nv] = d[v] + 1
            dfs(nv, v, d)


dfs(u, -1, t)
dfs(v, -1, a)

ans = 0
for i in range(n):
    if t[i] < a[i]:
        ans = max(ans, a[i] - 1)
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    from collections import defaultdict,deque
    from math import ceil
    INF = 10**20
    f = lambda :map(int,input().split())
    n,u,v = f() # u:高橋
    edge = defaultdict(list)
    for i in range(n-1):
        a,b = f()
        edge[a].append(b)
        edge[b].append(a)
    
    distance = [[-1]*2 for _ in range(n+1)]
    distance[u][0] = 0
    distance[v][1] = 0
    def dfs(parent, start):
        distance_parent = distance[parent][start]
        for child in edge[parent]:
            if distance[child][start] == -1:
                distance[child][start] = distance_parent + 1
                dfs(child, start)
    dfs(u,0)
    dfs(v,1)
    ans = 0
    for u_d, v_d in distance:
        if u_d < v_d:
            ans = max(ans,v_d)
    print(ans-1)


        


main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, u: int, v: int, A: "List[int]", B: "List[int]"):
    if u == v:
        return 0
    edges = [[] for _ in range(N)]
    for a, b in zip(A, B):
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)
    t_a = [[float('inf')] * N for _ in range(2)]
    def dfs(n, c, t):
        if t_a[t][n] < float('inf'):
            return
        t_a[t][n] = c
        for nn in edges[n]:
            dfs(nn, c+1, t)
    dfs(u-1, 0, 0)
    dfs(v-1, 0, 1)
    c = max(a for t, a in zip(*t_a) if t < a)
    return c - 1

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
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))
    print(solve(N, u, v, A, B))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Runtime Error

Solution code:
from collections import deque


def nearlist(N, LIST):  # 隣接リスト
    NEAR = [set() for _ in range(N)]
    for a, b in LIST:
        NEAR[a - 1].add(b - 1)
        NEAR[b - 1].add(a - 1)
    return NEAR


def bfs(NEAR, S, N):  # 幅優先探索  # キュー
    dist = [-1 for _ in range(N)]  # 前処理
    dist[S] = 0
    que, frag = deque([S]), set([S])

    while len(que) > 0:
        q = que.popleft()
        for i in NEAR[q]:  # 移動先の候補
            if i in frag:  # 処理済みか否か
                continue
            dist[i] = dist[q] + 1
            que.append(i), frag.add(i)
    return dist


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

near = nearlist(n, ab)
tkdist, akdist = bfs(near, u - 1, n), bfs(near, v - 1, n)

node = [i for i in range(n) if tkdist[i] <= akdist[i]]
ans = max(akdist[i] for i in node)
print(ans[0] - 1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys


sys.setrecursionlimit(10 ** 6)


def find_path(adj, to_node, node, parent=None):
    if node == to_node:
        return [to_node]
    path = None
    for child in adj[node]:
        if child == parent:
            continue
        p = find_path(adj, to_node, child, node)
        if p is None:
            continue
        if path is None or len(path) > len(p):
            path = p
    return path + [node]


def depth(adj, node, parent=None):
    ret = 0
    for child in adj[node]:
        if child == parent:
            continue
        d = depth(adj, child, node) + 1
        ret = max(ret, d)
    return ret


def main():
    N, U, V = list(map(int, input().split(' ')))
    U -= 1
    V -= 1
    adj = defaultdict(list)
    for _ in range(N - 1):
        A, B = list(map(lambda x: int(x) - 1, input().split(' ')))
        adj[A].append(B)
        adj[B].append(A)
    path = find_path(adj, U, V)  # to U from V
    path.reverse()
    dist = len(path) - 1
    partial_depth = depth(adj, path[(dist // 2) + 1], path[dist // 2])
    print(partial_depth + (dist // 2))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict


def find_path(adj, to_node, node, parent=None):
    if node == to_node:
        return [to_node]
    path = None
    for child in adj[node]:
        if child == parent:
            continue
        p = find_path(adj, to_node, child, node)
        if p is None:
            continue
        p = [node] + p
        if path is None or len(path) > len(p):
            path = p
    return path


def depth(adj, node, parent=None):
    ret = 0
    for child in adj[node]:
        if child == parent:
            continue
        d = depth(adj, child, node) + 1
        ret = max(ret, d)
    return ret


def main():
    N, U, V = list(map(int, input().split(' ')))
    U -= 1
    V -= 1
    adj = defaultdict(list)
    for _ in range(N - 1):
        A, B = list(map(lambda x: int(x) - 1, input().split(' ')))
        adj[A].append(B)
        adj[B].append(A)
    path = find_path(adj, U, V)  # to U from V
    dist = len(path) - 1
    partial_depth = depth(adj, path[(dist // 2) + 1], path[dist // 2])
    print(partial_depth + (dist // 2))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n, u, v = list(map(int, input().split(' ')))
paths = {}
for i in range(n-1):
    a, b = list(map(int, input().split(' ')))
    paths[a] = paths.get(a, []) + [b]
    paths[b] = paths.get(b, []) + [a]
# 鬼を root にした時に逃げる人が途中で鬼に追いつかれずにたどり着ける葉までの root からの深さが答えっぽい(+-1位ズレそうだけど)
# print(paths)
u_leaves = {}
v_leaves = {}
def f(current, parent, cost, uv):
    finish = True
    for vertex in paths.get(current, []):
        if vertex == parent:
            continue
        f(vertex, current, cost + 1, uv)
        finish = False
    if finish:
        if uv == 'u':
            u_leaves[current] = cost
        else:
            v_leaves[current] = cost
f(u, None, 0, 'u')
f(v, None, 0, 'v')
# print(u_leaves)
# print(v_leaves)
ans = 0
for i in range(1, n+1):
    if i in u_leaves and i in v_leaves:
        ans = max(ans, max(v_leaves[i], u_leaves[i]) - 1)  # ???
        if u_leaves[i] == v_leaves.get(i, 0):
            ans = 1
print(ans)

Submission status: Runtime Error

Solution code:
n, u, v = list(map(int, input().split(' ')))
paths = {}
for i in range(n-1):
    a, b = list(map(int, input().split(' ')))
    paths[a] = paths.get(a, []) + [b]
    paths[b] = paths.get(b, []) + [a]
# 鬼を root にした時に逃げる人が途中で鬼に追いつかれずにたどり着ける葉までの root からの深さが答えっぽい(+-1位ズレそうだけど)
# print(paths)
u_leaves = {}
v_leaves = {}
def f(current, parent, cost, uv):
    finish = True
    for vertex in paths[current]:
        if vertex == parent:
            continue
        f(vertex, current, cost + 1, uv)
        finish = False
    if finish:
        if uv == 'u':
            u_leaves[current] = cost
        else:
            v_leaves[current] = cost
f(u, None, 0, 'u')
f(v, None, 0, 'v')
# print(u_leaves)
# print(v_leaves)
ans = 0
for i in range(1, n+1):
    if i in u_leaves and i in v_leaves:
        ans = max(ans, max(v_leaves[i], u_leaves[i]) - 1)  # ???
        if u_leaves[i] == v_leaves.get(i, 0):
            ans = 1
print(ans)

Submission status: Runtime Error

Solution code:
n, a, b = map(int, input().split())
D = [[0]*2 for _ in range(101010)]
E = [[] for _ in range(n)]


def dfs(cur, pre, d, id):
    D[cur][id] = d
    for nv in E[cur]:
        if nv != pre:
            dfs(nv, cur, d+1, id)


a -= 1
b -= 1
for i in range(n-1):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    E[x].append(y)
    E[y].append(x)
dfs(a, a, 0, 0)
dfs(b, b, 0, 1)
max_d = 0
for i in range(n):
    if D[i][0] < D[i][1]:
        max_d = max(max_d, D[i][1]-1)
print(max_d)