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 defaultdict

class Tree:
    def __init__(self, n, edges, weight=False):
        self.n = n
        self.adj = [[] for _ in range(n)]
        self.parent = [-1] * self.n
        self.children = [[] for _ in range(self.n)]
        self.dist = [-1] * self.n  # 根からの距離
        self.depth = [-1] * self.n  # 根からの深さ(cost=1での距離)
        self.weight = defaultdict(lambda: 10**18)
        if weight:
            for u, v, weight in edges:
                self.adj[u].append(v)
                self.adj[v].append(u)
                self.weight[(u, v)] = weight
                self.weight[(v, u)] = weight
        else:
            for u, v in edges:
                self.adj[u].append(v)
                self.adj[v].append(u)
                self.weight[(u, v)] = 1
                self.weight[(v, u)] = 1

    def set_root(self, root):  # O(n)
        self.root = root
        self.order = [root]
        self.dist[root] = 0
        self.depth[root] = 0
        stack = [root]
        while stack:
            v = stack.pop()
            for child in self.adj[v]:
                if child == self.parent[v]:
                    continue
                else:
                    self.parent[child] = v
                    self.children[v].append(child)
                    self.dist[child] = self.dist[v] + self.weight[(v, child)]
                    self.depth[child] = self.depth[v] + 1
                    self.order.append(child)
                    stack.append(child)

    def get_root_path(self, target):
        path = [target]
        v = target
        while v != self.root:
            path.append(self.parent[v])
            v = self.parent[v]
        path.reverse()
        return path

    def get_diameter(self, restore=False):  # double-sweepで求める  O(n)
        u = self.dist.index(max(self.dist))  # 根から一番遠いものを根とし、そこから一番遠いものを見つける
        dist_u = [-1] * self.n
        dist_u[u] = 0
        stack = [u]
        parent_u = [None for _ in range(self.n)]
        while stack:
            v = stack.pop()
            for child in self.adj[v]:
                if dist_u[child] == -1:
                    dist_u[child] = dist_u[v] + self.weight[(v, child)]
                    parent_u[child] = v
                    stack.append(child)
        diameter = max(dist_u)
        v = dist_u.index(diameter)
        if restore:
            path = [v]
            while v != u:
                v = parent_u[v]
                path.append(v)
            path.reverse()  # [u,...,v]
            return diameter, path
        else:
            return diameter, u, v

    # --- Heavy Light Decomposition --- #

    def heavy_light_decompose(self):  # O(n)
        self.subsize = [1] * self.n  # 部分木の要素数(自分含む)
        self.head = [self.root] * self.n  # 分割された各部分木の先頭
        self.tree_order = [0] * self.n

        # 末端の方から各頂点の部分木の要素数(subsize)を計算していって、
        # heavy-nodeがchildren[v][0]に来るようにする
        for v in reversed(self.order):
            v_kids = self.children[v]  # 名前が長いのでalias
            for i, child in enumerate(v_kids):
                self.subsize[v] += self.subsize[child]
                if self.subsize[child] > self.subsize[v_kids[0]]:
                    v_kids[i], v_kids[0] = v_kids[0], v_kids[i]

        # それぞれのnodeについて分割されたchianの先頭(head)を記録
        # また、DFSの行きがけ順をtree_orderとする headの浅い順でchainが入る
        stack = [self.root]
        tree_label = 0
        while stack:
            v = stack.pop()
            self.tree_order[v] = tree_label
            tree_label += 1
            for child in reversed(self.children[v]):  # スタックを使ったdfsのため逆にしておく
                if child == self.children[v][0]:
                    self.head[child] = self.head[v]
                else:
                    self.head[child] = child  # light-nodeは切り離されたsub-treeのheadになる
                stack.append(child)

    def get_hld_chain_paths(self, u, v):  # (u,v)間の経路をchainごとに返す [l,r)
        ret = []
        while True:
            if self.tree_order[u] > self.tree_order[v]:
                u, v = v, u
            if self.head[u] == self.head[v]:
                ret.append((self.tree_order[u], self.tree_order[v] + 1))
                return ret
            else:
                ret.append((self.tree_order[self.head[v]], self.tree_order[v] + 1))
                v = self.parent[self.head[v]]

    def get_hld_lca(self, u, v):  # Lowest Common Ancestor
        while True:  # head[u] = head[v] になるまで遡る
            if self.tree_order[u] > self.tree_order[v]:
                u, v = v, u
            if self.head[u] == self.head[v]:
                return u
            v = self.parent[self.head[v]]

    def get_hld_distance(self, u, v):
        return self.dist[u] + self.dist[v] - (2 * self.dist[self.get_hld_lca(u, v)])

    def exist_on_path_hld(self, u, v, x):  # u,v間の最短経路上にxがあるかどうか
        return self.get_hld_distance(u, x) + self.get_hld_distance(x, v) == self.get_hld_distance(u, v)

# ---------------------- #

n, u, v = (int(x) for x in input().split())
u -= 1
v -= 1
edges = [tuple(int(x) - 1 for x in input().split()) for _ in range(n - 1)]
tree = Tree(n, edges)
tree.set_root(v)
tree.heavy_light_decompose()
ans = 0
for i in range(n):
    if tree.get_hld_distance(i, u) <= tree.get_hld_distance(i, v):
        ans = max(ans, tree.get_hld_distance(i, v) - 1)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n,U,V = map(int, input().split())
U -= 1
V -= 1
ns = defaultdict(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)

def bfs(start, ng=None):
    from queue import deque
    q = deque([start])
    seen = [None] * n
    dist = [None] * n
    dist[start] = 0
    seen[start] = -1
    while q:
        u = q.pop()
        d = dist[u]
        for v in ns[u]:
            if seen[v] is None and (ng is None or v!=ng):
                seen[v] = u
                dist[v] = d + 1
                q.appendleft(v)
    return seen, dist
ps, du = bfs(U)
_, dv = bfs(V)
l = []
tmp = V
while tmp!=U:
    l.append(tmp)
    tmp = ps[tmp]
d = len(l)
l = l[::-1]
dist = d//2 if d%2 else d//2-1
ng = l[dist]
start = U if dist==0 else l[dist-1]
_, D = bfs(start, ng=ng)
if max(item for item in D if item is not None)==0:
    ans = dv[start] - 1
else:
    ans = -1
    for i,num in enumerate(D):
        if num is None:
            continue
        val = num + dv[start] - 1#((dv[num]-du[num])%2==1)
        ans = max(ans, val)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

tree = [[] for _ in range(N + 1)]
for a, b in X:
    tree[a].append(b)
    tree[b].append(a)

def find_dist(s):
    dist = [-1] * (N + 1)
    dist[s] = 0
    q = deque()
    q.append(s)
    while q:
        u = q.popleft()
        for v in tree[u]:
            if dist[v] >= 0:
                continue
                
            dist[v] = dist[u] + 1
            q.append(v)
            
    return dist


dist_u = find_dist(U)
dist_v = find_dist(V)

ans = 0
for i in range(1, N + 1):
    if dist_u[i] <= dist_v[i]:
        ans = max(ans, dist_v[i] - 1)
        
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N,U,V = map(int, input().split())
U,V = U-1, V-1
E = [[] for _ in range(N)]

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

def BFS(root):
  D = [ 0 for _ in range(N) ]
  visited = [False for _ in range(N)]
  willSearch = [ False for _ in range(N)]
  Q = deque()
  Q.append(root)
  willSearch[root] = True
  while len(Q) > 0:
    now = Q.pop()
    visited[now] = True
    for nx in E[now]:
      if visited[nx] or willSearch[nx]:
        continue
      willSearch[nx] = True
      D[nx] = D[now] + 1
      Q.append(nx)
  return D

UD = BFS(U)
VD = BFS(V)

#print(UD)
#print(VD)

#初手で青木くんのPOINTにしか行けないケース
if E[U] == [V]:
  print(0)
  exit(0)
  
ans=0
 
for i in range(N):
    if UD[i]<=VD[i]:
        ans=max(ans,VD[i]-1)

print(ans)

Submission status: Accepted

Solution code:
N,u,v=list(map(int,input().split()))
g=[[] for _ in range(N+1)]

def dist(x):
    dist=[-1]*(N+1)
    dist[x]=0
    stack=[x]
    while len(stack)>0:
        current=stack.pop()

        for s in g[current]:
            if dist[s]>-1:
                continue

            dist[s]=dist[current]+1
            stack.append(s)

    return dist

for _ in range(N-1):
    a,b=list(map(int,input().split()))

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

du=dist(u)
dv=dist(v)

ans=0

for i in range(1,N+1):
    if du[i]<=dv[i]:
        ans=max(ans,dv[i]-1)

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, p, q, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(*[iter(AB)] * 2):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    p -= 1
    q -= 1

    if len(G[p]) == 1 and G[p][0] == q:
        print(0)
        return

    dist1 = [-1] * N
    dist1[p] = 0
    queue1 = deque([p])
    while queue1:
        v = queue1.popleft()
        for nv in G[v]:
            if dist1[nv] == -1:
                dist1[nv] = dist1[v] + 1
                queue1.append(nv)

    dist2 = [-1] * N
    dist2[q] = 0
    queue2 = deque([q])
    while queue2:
        v = queue2.popleft()
        for nv in G[v]:
            if dist2[nv] == -1:
                dist2[nv] = dist2[v] + 1
                queue2.append(nv)

    max_dist = -1
    for d1, d2 in zip(dist1, dist2):
        if d1 < d2 and max_dist < d2:
            max_dist = d2

    print(max_dist - 1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

dist=[[-1, -1] for _ in range(n)]
dist[v][0]=0
dist[u][1]=0
 
def dfs(graph,v,k):
    ver=graph[v]
    for vers in ver:
        if dist[vers][k]==-1:
            dist[vers][k]=dist[v][k]+1
            dfs(graph,vers,k)
 
 
dfs(graph,v,0)
dfs(graph,u,1)
dist.sort(reverse=True)
 
for i in range(10**6):
    if dist[i][0]-dist[i][1]>=1:
        print(dist[i][0]-1)
        break

Submission status: Accepted

Solution code:
from collections import deque

def bfs(s):
    stack=deque([s])
    check = [-1]*n
    check[s] = 0
    while len(stack)>0:
        v = stack.popleft()
        for i in root[v]:
            if check[i] == -1:
                check[i]=check[v]+1
                stack.append(i)
    return check

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

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

takahashi_root = bfs(u-1)
aoki_root = bfs(v-1)

ans = 0

for i in range(n):
    if takahashi_root[i] < aoki_root[i]:
        ans = max(ans,aoki_root[i]-1)
print(ans)

Submission status: Accepted

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

# 青木君からの到達距離 - 高橋君からの到達距離が最も大きい場所に逃げるべき
# そこに到達したときに、
# 高橋君と青木君の距離が偶数のとき
# 青 - x - x - x - 高
# 青 - x - x - 高 - x
# x - 青 - x - 高 - x
# x - 青 - x - x - 高
# x - x - 青 - x - 高
# x - x - 青- 高 - x 
# x - x - x - 終 - x 
# 青木君からの距離 - 1が答え
# 高橋君と青木君の距離が奇数のとき
# 青 - x - x - 高
# 青 - x - 高 - x
# x - 青 - 高 - x
# x - 青 - x - 高
# x - x - 青 - 高
# x - x - 終 - x
# やっぱり青木君からの距離 - 1が答え
# つまり、
# ・[青木君からの距離が遠い場所について]
# ・[青木君からの距離 - 1]が答え

N,u,v = map(int,readline().split())
G = [[] for i in range(N)]
for i in range(N - 1):
  a,b = map(int,readline().split())
  G[a - 1].append(b - 1)
  G[b - 1].append(a - 1)

dist_from_u = [0 for i in range(N)] # 高橋君からの距離
dist_from_v = [0 for i in range(N)] # 青木君からの距離

stack = []
# 頂点, 高橋君からの距離, 親
stack.append([u - 1,0,-1])
while stack:
  e, dist, parent = stack.pop()
  dist_from_u[e] = dist
  for child in G[e]:
    if child == parent:
      continue
    stack.append([child, dist + 1, e])

stack = []
# 頂点, 青木君からの距離, 親
stack.append([v - 1,0,-1])
while stack:
  e, dist, parent = stack.pop()
  dist_from_v[e] = dist
  for child in G[e]:
    if child == parent:
      continue
    stack.append([child, dist + 1, e])
    
maxdiff_from_v = 0
for i in range(N):
  if dist_from_u[i] < dist_from_v[i]:
    if maxdiff_from_v < dist_from_v[i]:
      maxdiff_from_v = dist_from_v[i]
    
print(maxdiff_from_v - 1)

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n, u, v = ns()
    edge = [[] for _ in range(n)]

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

    dist_takahashi = [-1] * n
    dist_aoki = [-1] * n

    def bfs(pos, dist):
        que = queue.Queue()
        que.put(pos)
        dist[pos] = 0

        while not que.empty():
            current = que.get()
            for e in edge[current]:
                if dist[e] == -1:
                    dist[e] = dist[current] + 1
                    que.put(e)

        return dist

    dist_takahashi = bfs(u - 1, dist_takahashi)
    dist_aoki = bfs(v - 1, dist_aoki)

    ans = 0
    for dt, da in zip(dist_takahashi, dist_aoki):
        if dt < da:
            ans = max(ans, da - 1)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

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

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

dist=[[-1, -1] for _ in range(n)]
dist[v][0]=0
dist[u][1]=0

def dfs1(graph,v):
    vv=graph[v]
    for vvv in vv:
        if dist[vvv][0]==-1:
            dist[vvv][0]=dist[v][0]+1
            dfs1(graph,vvv)

def dfs2(graph,v):
    vv=graph[v]
    for vvv in vv:
        if dist[vvv][1]==-1:
            dist[vvv][1]=dist[v][1]+1
            dfs2(graph,vvv)

dfs1(graph,v)
dfs2(graph,u)
dist.sort(reverse=True)

for i in range(10**6):
    if dist[i][0]-dist[i][1]>=1:
        print(dist[i][0]-1)
        break

Submission status: Accepted

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


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

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

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

dist=[[-1, -1] for _ in range(n)]
dist[v][0]=0
dist[u][1]=0

def dfs1(graph,v):
    vv=graph[v]
    for vvv in vv:
        if dist[vvv][0]==-1:
            dist[vvv][0]=dist[v][0]+1
            dfs1(graph,vvv)

def dfs2(graph,v):
    vv=graph[v]
    for vvv in vv:
        if dist[vvv][1]==-1:
            dist[vvv][1]=dist[v][1]+1
            dfs2(graph,vvv)

dfs1(graph,v)
dfs2(graph,u)
dist.sort(reverse=True)

for i in range(10**6):
    if dist[i][0]-dist[i][1]>=1:
        print(dist[i][0]-1)
        break

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
 
N,u,v = map(int,input().split())
edges = [list(map(int,input().split())) for _ in range(N-1)]
E = [[] for _ in range(N+1)]
for a,b in edges:
    E[a].append(b)
    E[b].append(a)
 
depth = [[-1,-1] for _ in range(N+1)] 
depth[v][0] = 0
depth[u][1] = 0

def dfs1(E,v):
    vv = E[v]
    for vvv in vv:
        if depth[vvv][0] == -1:
            depth[vvv][0] = depth[v][0] + 1
            dfs1(E,vvv)
 
def dfs2(E,v):
    vv = E[v]
    for vvv in vv:
        if depth[vvv][1] == -1:
            depth[vvv][1] = depth[v][1] + 1
            dfs2(E,vvv)
dfs1(E,v)
dfs2(E,u)
depth = sorted(depth, reverse=True)
idx = 0
while True:
    if depth[idx][0] - depth[idx][1] >= 1:
        print(depth[idx][0]-1)
        exit()
    else:
        idx += 1

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)

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

distT = [-1]*n
distA = [-1]*n
distT[u] = 0
distA[v] = 0
def dfs(now,dist):
    for nxt in G[now]:
        if dist[nxt] != -1: continue
        dist[nxt] = dist[now]+1
        dfs(nxt,dist)
dfs(u,distT)
dfs(v,distA)

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

Submission status: Accepted

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

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

def dfs1(pos, before_pos):
    for next_pos in ab[pos]:
        if next_pos == before_pos:
            continue
        if next_pos == u:
            return True, [pos]
        tf, root = dfs1(next_pos, pos)
        if tf:
            root.append(pos)
            return True, root
    return False, []
    
root = dfs1(v, -1)[1]
root = root[::-1]
root.append(u)
n = (len(root) + 1) // 2
pos = root[n]
before_pos = root[n - 1]

max_len = n

def dfs2(pos, before_pos, cnt):
    global max_len
    cnt += 1
    max_len = max(max_len, cnt)
    if cnt < n - 1:
        dfs2(root[cnt + 1], pos, cnt)
    else:
        for next_pos in ab[pos]:
            if next_pos == before_pos:
                continue
            dfs2(next_pos, pos, cnt)


dfs2(pos, before_pos, n - 1)
ans = max_len - 1
ans = max(ans, 0)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

N, u, v  = map(int, input().split())
way = defaultdict(list)
for _ in range(N-1):
    a, b =  map(int, input().split())
    
    way[a].append(b)
    way[b].append(a)
seen1 = [-1]*N
seen2 = [-1]*N
seen1[u-1] = 0
seen2[v-1]= 0

queue = deque([u])
while queue:
    q = queue.popleft()
    for i in way[q]:
        if seen1[i-1]==-1:
            queue.append(i)
            seen1[i-1] = seen1[q-1]+1

queue = deque([v])
while queue:
    q = queue.popleft()
    for i in way[q]:
        if seen2[i-1]==-1:
            queue.append(i)
            seen2[i-1] = seen2[q-1]+1
            
#print(way)
#print(seen1)
#print(seen2)
for i in range(N):
    if seen1[i]>=seen2[i]:
        seen2[i] = -1
print(max(seen2)-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

INF = float('inf')

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

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

costUs = bfsMinCosts(adjL, u, INF)
costVs = bfsMinCosts(adjL, v, INF)

ans = 0
for x in range(N):
    if costUs[x] < costVs[x]:
        if costVs[x] > ans:
            ans = costVs[x]

print(ans-1)

Submission status: Accepted

Solution code:
from collections import deque
import sys

N, u, v = map(int, input().split())
u -= 1; v -= 1
edge = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    A, B = map(lambda x: int(x) - 1, s.split())
    edge[A].append(B)
    edge[B].append(A)

INF = float('inf')

# Aoki
pathV = [INF] * N
pathV[v] = 0
q = deque()
q.append((v, 0))
while q:
    p, d = q.popleft()
    nd = d + 1
    for np in edge[p]:
        if pathV[np] > nd:
            pathV[np] = nd
            q.append((np, nd))

# Takahashi
ans = 0
pathU = [INF] * N
pathU[u] = 0
q = deque()
q.append((u, 0))
while q:
    p, d = q.popleft()
    nd = d + 1
    if len(edge[p]) == 1:
        ans = max(ans, pathV[p] - 1)
    for np in edge[p]:
        if pathU[np] > nd and pathV[np] > nd:
            pathU[np] = nd
            q.append((np, nd))

print(ans)

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,u,v = map(int,ipt().split())
    way = [[] for _ in range(n+1)]
    for _ in range(n-1):
        a,b = map(int,ipt().split())
        way[a].append(b)
        way[b].append(a)

    ta = [-1]*(n+1)
    tt = [-1]*(n+1)
    ta[v] = 0 #AOKI
    tt[u] = 0
    qa = queue.Queue()
    qt = queue.Queue()
    qt.put((0,u,-1))
    qa.put((0,v,-1))

    while not qa.empty():
        ti,pi,pp = qa.get()
        for i in way[pi]:
            if i == pp:
                continue
            if ta[i] == -1:
                ta[i] = ti+1
                qa.put((ti+1,i,pi))

    while not qt.empty():
        ti,pi,pp = qt.get()
        if ta[pi] <= ti:
            continue
        for i in way[pi]:
            if i == pp:
                continue
            if ta[i] > ti:
                tt[i] = ti+1
                qt.put((ti+1,i,pi))

    ma = 0
    for i in range(1,n+1):
        if tt[i] == -1:
            continue
        if ma < tt[i]+max(0,ta[i]-tt[i]-1):
            ma = tt[i]+max(0,ta[i]-tt[i]-1)
    print(ma)


    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

def dfs_a(N,v,adjlist,cur):
    global depth_a
    depth_a[v]=cur
    for node in adjlist[v]:
        if depth_a[node]<0:
            dfs_a(N,node,adjlist,cur+1)
def dfs_t(N,v,adjlist,cur):
    global depth_t
    depth_t[v]=cur
    for node in adjlist[v]:
        if depth_t[node]<0:
            dfs_t(N,node,adjlist,cur+1)
    
    
    

from collections import deque

N,u,v=map(int,input().split())
adjlist=[[] for _ in range(N)]
for _ in range(N-1):
    a,b=map(int,input().split())
    adjlist[a-1].append(b-1)
    adjlist[b-1].append(a-1)
depth_a=[-1]*N
depth_t=[-1]*N
dfs_a(N,v-1,adjlist,0)
dfs_t(N,u-1,adjlist,0)
M=0
for i in range(N):
    if depth_a[i]>depth_t[i]:
        curm=depth_a[i]-1
        if curm>M:
            M=curm
print(M)

Submission status: Accepted

Solution code:
from collections import deque

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

d_1 = deque()
d_1.append(u-1)
dist_1 = [-1] * n
dist_1[u-1] = 0
while d_1:
    node = d_1.popleft()
    for next_node in edge[node]:
        if dist_1[next_node] < 0:
            dist_1[next_node] = dist_1[node] + 1
            d_1.append(next_node)

d_2 = deque()
d_2.append(v-1)
dist_2 = [-1] * n
dist_2[v-1] = 0
while d_2:
    node = d_2.popleft()
    for next_node in edge[node]:
        if dist_2[next_node] < 0:
            dist_2[next_node] = dist_2[node] + 1
            d_2.append(next_node)

res = 0
for i in range(n):
    if dist_1[i] < dist_2[i]:
        res = max(res, dist_2[i]-1)
print(res)

Submission status: Accepted

Solution code:
N,u,v=map(int,input().split())
from collections import deque
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)
def bfs(n):
  stack=deque([])
  depth=[-1]*N
  depth[n-1]=0
  stack.append(n-1)
  while stack:
    a=stack.popleft()
    for b in g[a]:
      if depth[b]==-1:
        depth[b]=depth[a]+1
        stack.append(b)
  return depth
U=bfs(u)
V=bfs(v)
List=[]
for i in range(N):
  if len(g[i])==1 and U[i]<V[i]:
    List.append(i)
ans=0

for i in List:
  ans=max(ans,V[i]-1)

print(ans)

Submission status: Accepted

Solution code:
n,t,aoki=map(int,input().split())

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

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

if tree[t-1]==[aoki-1]:
    print(0)
    exit()


from collections import deque
ans=[-1]*n
stack = deque([t-1])
ans[t-1]=0

while len(stack)>0:
    tmp=stack.popleft()
    for item in tree[tmp]:
        if ans[item]==-1:
            ans[item]=ans[tmp]+1
            stack.append(item)


ans2=[-1]*n
stack = deque([aoki-1])
ans2[aoki-1]=0

result=0
#print("hoge",ans2)

while len(stack)>0:
    tmp=stack.popleft()
    for item in tree[tmp]:
        if ans2[item]==-1:
            ans2[item]=ans2[tmp]+1
            stack.append(item)
            if ans[item]<ans2[item]:
                result=max(result,ans2[item])-1
            elif ans[item]==ans2[item]:
                result=max(result,ans2[item])-1

print(result)

Submission status: Accepted

Solution code:
from collections import deque

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

not_yet = deque([u-1])
already = [False]*n
already[u-1] = True
dist = [0]*n

while not_yet:
  key = not_yet.popleft()
  for value in tree[key]:
    if already[value]:
      continue
    dist[value] = dist[key] + 1
    already[value] = True
    not_yet.append(value)
  
not_yet = deque([v-1])
already = [False]*n
already[v-1] = True
dist2 = [0]*n

while not_yet:
  key = not_yet.popleft()
  for value in tree[key]:
    if already[value]:
      continue
    dist2[value] = dist2[key] + 1
    already[value] = True
    not_yet.append(value)

judge = dist[v-1]
ans = 0
for i in range(n):
  if dist[i]+dist2[i] > judge:
    if dist[i] >= dist2[i]:
      continue
    sub = dist2[i]-1
  else:
    sub = judge-1
  if sub > ans:
    ans = sub
print(ans)

Submission status: Accepted

Solution code:
from collections import deque


def calc_dist(head, my_dict, dist_a):
    deq = deque()
    deq.append((head, 0))
    visited = set()
    visited.add(head)

    while deq:
        ptr, length = deq.pop()
        dist_a[ptr] = length
        for item in my_dict[ptr]:
            if item not in visited:
                visited.add(item)
                deq.append((item, length+1))


n, u, v = map(int, input().split())
my_dict = dict()

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

dist_a = dict()
dist_b = dict()

calc_dist(u, my_dict, dist_a)
calc_dist(v, my_dict, dist_b)
ret = 0

for i in range(1, n+1):
    if dist_a[i] > dist_b[i]:
        continue
    else:
        ret = max(ret, dist_b[i] - 1)

print(ret)

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
N,u,v=map(int, input().split())
D=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int, input().split())
  a-=1
  b-=1
  D[a].append(b)
  D[b].append(a)
Taka=[0]*(N+1)
Aoki=[0]*(N+1)
def f(n,p,A):
  for i in D[n]:
    if i!=p:
      A[i]=A[n]+1
      f(i,n,A)
      
f(u-1,-1,Taka)
f(v-1,-1,Aoki)
ans=0
for i in range(N):
  if Taka[i]<Aoki[i]:
    ans=max(ans,Aoki[i]-1)
print(ans)

Submission status: Accepted

Solution code:
n,u,v=map(int,input().split())
u-=1;v-=1
ki=[[] for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  ki[a-1].append(b-1)
  ki[b-1].append(a-1)
ha=[]
for i in range(n):
  if len(ki[i])==1:
    ha.append(i)
ta=[0]*n
ao=[0]*n
from collections import deque
d=deque()
d.append(u)
visited=[False]*n
visited[u]=True
while d:
  g=d.popleft()
  for i in ki[g]:
    if visited[i]:
      continue
    d.append(i)
    visited[i]=True
    ta[i]=ta[g]+1
d=deque()
d.append(v)
visited=[False]*n
visited[v]=True
while d:
  g=d.popleft()
  for i in ki[g]:
    if visited[i]:
      continue
    d.append(i)
    visited[i]=True
    ao[i]=ao[g]+1
if u in ha and ki[u][0]==v:
  print(0)
  exit()
m=0
for i in ha:
  if ta[i]<ao[i]:
    m=max(m,ao[i])
print(m-1)

Submission status: Accepted

Solution code:
from collections import deque
n,u,v=map(int, input().split())
edgelist = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    edgelist[a-1].append(b-1)
    edgelist[b-1].append(a-1)
dist = [[0,0] for _ in range(n)]
def distance(start, id):
    que=deque()
    visited = [0]*n

    found = False
    que.append([edgelist[start],start])
    while que:
        ver=que.popleft()
        visited[ver[1]]=1
        for next_v in ver[0]:
            if not visited[next_v]:
                dist[next_v][id]=dist[ver[1]][id]+1
                que.append([edgelist[next_v], next_v])
distance(u-1,0)
distance(v-1,1)
dist.sort(key = lambda x:x[1],reverse = True)
ans=0
for i in range(n):
    if dist[i][1]-dist[i][0]>=1:
        print(dist[i][1]-1)
        exit()