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, Counter, namedtuple, deque

NN = 202020
MOD = 10**9+7
INF = float("inf")

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


def bfs(start, player):
    que = deque([(start, -1, 0)])
    while que:
        node, par, dst = que.popleft()
        # print(node, par, dst)
        if len(graph[node]) == 1:
            # print(player, node)
            dst_dict[player][node] = dst

        for nxt in graph[node]:
            if nxt == par:
                continue
            que.append((nxt, node, dst+1))


dst_dict = [{}, {}]
bfs(u, 0)
bfs(v, 1)
# print(dst_dict[0], dst_dict[1])

max_time = 0
for k in dst_dict[0]:
    if dst_dict[0][k] < dst_dict[1][k]:
        max_time = max(max_time, dst_dict[1][k]-1)

print(max_time)

Submission status: Accepted

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())
    G[a].append(b)
    G[b].append(a)
    
def dfs(x,n): # 再帰じゃない DFS かく(DFSでもBFSでもどっちでも同じか)
    stack=deque([x])
    dist=[-1]*(n+1)
    dist[x]=0
    
    while len(stack)>0:
        a=stack.pop()
        for k in G[a]:
            if dist[k]<0:
                dist[k]=dist[a]+1
                stack.append(k)
    return dist # リストを返している

distt=dfs(u,n) # u高橋くんからの最短距離
dista=dfs(v,n) # v青木くんからの最短距離

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

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, U, V = lr()
graph = [[] for _ in range(N+1)] # 1-indexed
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

def dfs(start): # 木グラフの時
    dist = [-1] * (N+1)
    dist[start] = 0
    stack = [start]
    while stack:
        s = stack.pop()
        for x in graph[s]:
            if dist[x] != -1:
                continue
            dist[x] = dist[s] + 1
            stack.append(x)
    return dist

dist_U = dfs(U); dist_V = dfs(V)
answer = 0
for u, v in zip(dist_U[1:], dist_V[1:]):
    if v > u:
        x = v - 1
        if x > answer:
            answer = x

print(answer)

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, U, V = lr()
graph = [[] for _ in range(N+1)] # 1-indexed
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

def dfs(start): # 木グラフの時
    dist = [-1] * (N+1)
    dist[start] = 0
    stack = [start]
    while stack:
        s = stack.pop()
        for x in graph[s]:
            if dist[x] != -1:
                continue
            dist[x] = dist[s] + 1
            stack.append(x)
    return dist

dist_U = dfs(U)
dist_V = dfs(V)
answer = max(v for u, v in zip(dist_U, dist_V) if v > u) - 1
print(answer)

Submission status: Accepted

Solution code:
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, U, V = lr()
graph = [[] for _ in range(N+1)] # 1-indexed
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

def dijkstra(start):
    INF = 10 ** 15
    dist = [INF] * (N+1)
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for next in graph[prev]:
            d1 = d + 1
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

dist_U = dijkstra(U)
dist_V = dijkstra(V)
answer = max(v for u, v in zip(dist_U, dist_V) if v > u) - 1
print(answer)
# 25

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
INF = 10 ** 18

def dijkstra(s):
    used = [1] * n
    dp = [INF] * n
    dp[s] = 0
    hq = []
    used[s] = 0
    for i in cost[s]:
        heappush(hq, i)

    while hq:
        minv = heappop(hq)
        if used[minv[1]] == 0:
            continue
        v = minv[1]
        dp[v] = minv[0]
        used[v] = 0
        for i in cost[v]:
            if used[i[1]]:
                heappush(hq, [i[0] + dp[v], i[1]])
    return dp

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

dp1 = dijkstra(v - 1)
dp2 = dijkstra(u - 1)
ans = 0
for i in range(n):
    if dp1[i] >= dp2[i]:
        ans = max(ans, dp1[i])

print(ans - 1)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
INF = 10 ** 18

def dijkstra(s):
    used = [1] * n
    dp = [INF] * n
    dp[s] = 0
    hq = []
    used[s] = 0
    for i in cost[s]:
        heappush(hq, i)

    while hq:
        minv = heappop(hq)
        if used[minv[1]] == 0:
            continue
        v = minv[1]
        dp[v] = minv[0]
        used[v] = 0
        for i in cost[v]:
            if used[i[1]]:
                heappush(hq, [i[0] + dp[v], i[1]])
    return dp

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

dp1 = dijkstra(v - 1)
dp2 = dijkstra(u - 1)
ans = 0
for i in range(n):
    if dp1[i] >= dp2[i]:
        ans = max(ans, dp1[i])

print(ans - 1)

Submission status: Accepted

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

for _ in range(N - 1):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)
    edges[to].append(fr)

def calc(s):
    minDist = [10**18] * N
    st = [(s, 0)]
    while st:
        now, dist = st.pop()

        if minDist[now] < dist:
            continue
        minDist[now] = dist

        for to in edges[now]:
            if minDist[to] > dist + 1:
                st.append((to, dist + 1))
    return minDist

distTaka = calc(u - 1)
distAoki = calc(v - 1)

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

Submission status: Accepted

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

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


def dfs(v, d, count):
    count[v] = d
    for v_next in graph[v]:
        if count[v_next] >= 0:
            continue
        dfs(v_next, d + 1, count)


count_tak = [-1] * n
dfs(u, 0, count_tak)
count_aok = [-1] * n
dfs(v, 0, count_aok)

ans = 0
for i in range(n):
    if count_tak[i] < count_aok[i]:
        ans = max(ans, count_aok[i] - 1)

print(ans)

Submission status: Accepted

Solution code:
N,u,v = map(int, input().split())
if u == v:
  print(0)
  exit()
  
ver= [[] for i in range(N)]

for i in range(N-1):
    a, b = map(int, input().split())
    ver[a-1].append(b-1)
    ver[b-1].append(a-1)
    
    
def bfs(start):
    dist_turn = [float('inf') for i in range(N)]
    dist_turn[start] = 0
    visited = set()
    visited.add(start)
    turn = 0
    prev_dists = [start]
    new_dists = []
    while len(prev_dists) != 0:
        turn += 1
        for prev_dist in prev_dists:
            for new_dist in ver[prev_dist]: 
                if new_dist not  in visited:
                    visited.add(new_dist)
                    new_dists.append(new_dist)
                    dist_turn[new_dist] = turn
        prev_dists = new_dists
        new_dists = []
    return dist_turn

u_shortest = bfs(u-1)
v_shortest = bfs(v-1)

max_dist = -1
for i in range(N):
    if u_shortest[i] < v_shortest[i]:
        max_dist = max(max_dist, v_shortest[i])
print(max_dist - 1)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N,u,v = inputIL()
l = inputILL(N-1)

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

dic = dict([(i,[]) for i in range(1,N+1)])
 
for i in l:
  dic[i[0]].append(i[1])
  dic[i[1]].append(i[0])

du = [INF for i in range(N+1)]
du[u] = 0
q = deque([u])

while q:
  x = q.popleft()
  nd = du[x]+1
  for nx in dic[x]:
    if nd < du[nx]:
      du[nx] = nd
      q.append(nx)
      
dv = [INF for i in range(N+1)]
dv[v] = 0
q = deque([v])

while q:
  x = q.popleft()
  nd = dv[x]+1
  for nx in dic[x]:
    if nd < dv[nx]:
      dv[nx] = nd
      q.append(nx)
  
best = 0
pos = None
for i in range(1,N+1):
  if du[i] < dv[i]:
    if best < dv[i]:
      best = dv[i]

print(best-1)

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7

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

dic=defaultdict(list)
for i in range(n-1):
    a,b=ab[i]
    dic[a].append(b)
    dic[b].append(a)
# print(dic)

taka=[-1]*(n+1)
aoki=[-1]*(n+1)

d=deque([[u,0]])
if len(dic[u])==1:
    taka[u]=0
while d:
    now,cnt=d.popleft()
    flag=0
    for i in range(len(dic[now])):
        if taka[dic[now][i]]==-1:
            taka[dic[now][i]]=-2
            flag=1
            d.append([dic[now][i],cnt+1])
    if flag==0:
        taka[now]=cnt
# print(taka)

d=deque([[v,0]])
if len(dic[v])==1:
    aoki[v]=0
while d:
    now,cnt=d.popleft()
    flag=0
    for i in range(len(dic[now])):
        if aoki[dic[now][i]]==-1:
            aoki[dic[now][i]]=-2
            flag=1
            d.append([dic[now][i],cnt+1])
    if flag==0:
        aoki[now]=cnt
# print(aoki)

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)


def get_distance(v):              
    distance = [0] * n
    visited = [0] * n
    visited[v] = 1
    dfs(v, 0, distance, visited)
    return distance


def dfs(v, d, distance, visited):
    distance[v] = d
    for u in adj[v]:
        if not visited[u]:
            visited[u] = 1
            dfs(u, d + 1, distance, visited)


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

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

u_distance = get_distance(u - 1)
v_distance = get_distance(v - 1)

ans = 0
for u, v in zip(u_distance, v_distance):
    if u < v and v - 1 > ans:
        ans = v - 1

print(ans)

Submission status: Accepted

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

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

connect = [set() for _ in range(n)]
for a, b in edge:
    connect[a-1].add(b-1)
    connect[b-1].add(a-1)

du = [0] * n
dv = [0] * n

def dfs(v, dis, ng, d):
    d[v] = dis
    ng.add(v)
    for w in connect[v]:
        if w not in ng:
            dfs(w, dis+1, ng, d)

dfs(u, 0, set(), du)
dfs(v, 0, set(), dv)

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

Submission status: Accepted

Solution code:
from collections import deque
n,u,v=map(int,input().split())
G=[[] for i in range(n)]
dist_u=[-1]*n
dist_v=[-1]*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)

u-=1
v-=1

dist_u[u]=0
q=deque([u])

while q:
    cur=q.popleft()
    for nx in G[cur]:
        if dist_u[nx]==-1:
            q.append(nx)
            dist_u[nx]=dist_u[cur]+1

dist_v[v]=0
q=deque([v])

while q:
    cur=q.popleft()
    for nx in G[cur]:
        if dist_v[nx]==-1:
            q.append(nx)
            dist_v[nx]=dist_v[cur]+1
ans=0
for i in range(n):
    if dist_u[i]<dist_v[i] and dist_v[i]>=ans:
        ans=dist_v[i]
print(ans-1)

Submission status: Accepted

Solution code:
import queue

N, U, V = map(int, input().rstrip().split())
U -= 1
V -= 1

v2e = [set() for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().rstrip().split())
    v2e[a].add(b)
    v2e[b].add(a)
    
q = queue.Queue()
q.put(U)
p = [-1] * N
p[U] = U
while True:
    a = q.get()
    
    if a == V:
        break
    
    for b in v2e[a]:
        if p[b] == -1:
            p[b] = a
            q.put(b)
            
a = V
min_p = []
while True:
    min_p.append(a)
    if a == U:
        break
    a = p[a]

p = [-1] * N
p[min_p[(len(min_p)-1)//2-len(min_p)%2]] = min_p[(len(min_p)-1)//2-len(min_p)%2]
for a in v2e[min_p[(len(min_p)-1)//2-len(min_p)%2]]:
    p[a] = a
p[min_p[-len(min_p)//2+len(min_p)%2]] = min_p[-len(min_p)//2+len(min_p)%2]

q = queue.Queue()
q.put((min_p[-len(min_p)//2+len(min_p)%2], 0))
while q.qsize() > 0:
    a, d = q.get()
    
    for b in v2e[a]:
        if p[b] == -1:
            p[b] = a
            q.put((b, d + 1))
            
print(d + (len(min_p) - 2) // 2 + len(min_p) % 2)

Submission status: Accepted

Solution code:
N, U, V = map(int, input().split())
G = [set() for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a].add(b)
    G[b].add(a)

stack = [V]
path = []
vs = set([V])
G2 = [set() for _ in range(N+1)]
depth = [0] * (N+1)
while stack:
    v = stack.pop()
    if v > 0:
        path.append(v)
        if v == U:
            tmp = len(path)//2
#            print(path)
            ss = path[-tmp]
        for u in G[v]:
            if u in vs:
                continue
            depth[u] = depth[v] + 1
            G2[v].add(u)
            vs.add(u)
            stack += [-v, u]
    else:
        path.pop()

stack = [ss]
vs = set([ss])
while stack:
    v = stack.pop()
    for u in G2[v]:
        if u in vs:
            continue
        vs.add(u)
        stack.append(u)
#print(vs, depth)
x = 0
for v in vs:
    x = max(depth[v], x)
print(x-1)

Submission status: Accepted

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

from collections import deque
q = deque()
q.append(u)
t = [-1]*n
t[u] = 0
while q:
    x = q.popleft()
    for new_x in g[x]:
        if t[new_x] == -1:
            t[new_x] = t[x]+1
            q.append(new_x)

q = deque()
q.append(v)
a = [-1]*n
a[v] = 0
while q:
    x = q.popleft()
    for new_x in g[x]:
        if a[new_x] == -1:
            a[new_x] = a[x]+1
            q.append(new_x)
            
max_ = 0
for i in range(n):
    if t[i] < a[i]:
        max_ = max(max_, a[i])
print(max_-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**6)
n,U,V = map(int,input().split())
U-=1;V-=1
G = [[] for i in range(n)]
for i in range(n-1):
  a,b = map(int,input().split())
  a-=1;b-=1
  G[a].append(b)
  G[b].append(a)
Aokidis = [0]*n
Takahashidis = [0]*n
def dfs(node,dis,TorA,pre):
  if TorA == "Takahashi":Takahashidis[node] = dis
  else:Aokidis[node] = dis
  for vi in G[node]:
    if vi == pre:continue
    dfs(vi,dis+1,TorA,node)
dfs(U,0,"Takahashi",-1)
dfs(V,0,"",-1)
for i in range(n):
  if Takahashidis[i] <= Aokidis[i]:
    ans = max(ans,Aokidis[i]-1)
print(ans)

Submission status: Accepted

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

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


def calc_dist(s):
    dist = [-1] * (N + 1)
    dist[s] = 0
    node = [s]
    while node:
        s = node.pop()
        d = dist[s]
        for t in edge[s]:
            if dist[t] != -1:
                continue
            dist[t] = d + 1
            node.append(t)
    return dist[1:]


taka = calc_dist(u)
aoki = calc_dist(v)
ans = 0

for x, y in zip(taka, aoki):
    if x <= y:
        ans = max(ans, y - 1)

print(ans)

Submission status: Accepted

Solution code:
n,u,v=map(int,input().split())
u-=1
v-=1
e=[[]for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  e[a].append(b)
  e[b].append(a)
cho=[u]
cho_dis=[10**7]*n
cho_dis[u]=0
cho_visited={u}
countt=1
while cho:
  CHO=[]
  for i in cho:
    for j in e[i]:
      if j in cho_visited:continue
      cho_visited.add(j)
      CHO.append(j)
      cho_dis[j]=countt
  countt+=1
  cho=CHO
aok=[v]
aok_dis=[10**7]*n
aok_dis[v]=0
aok_visited={v}
countt=1
while aok:
  AOK=[]
  for i in aok:
    for j in e[i]:
      if j in aok_visited:continue
      aok_visited.add(j)
      AOK.append(j)
      aok_dis[j]=countt
  countt+=1
  aok=AOK
ans=0
for i in range(n):
  if cho_dis[i]<aok_dis[i]:ans=max(ans,aok_dis[i]-1)
print(ans)

Submission status: Accepted

Solution code:
#148_F
import queue
n, u, v = map(int, input().split())
inf = 10 ** 6
ans = 0

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

def bfs(d,start):
    d[start] = 0
    que = queue.Queue()
    que.put(start)
    while not que.empty():
            x = que.get()
            for to in edges[x]:
                if d[to] == inf:
                    que.put(to)
                    d[to] = d[x] + 1
                    
du, dv = [inf]*n, [inf]*n
bfs(du,u-1)
bfs(dv,v-1)
for i in range(n):
    if dv[i] > du[i]:
        ans = max(ans, dv[i] - 1)
    
print(ans)

Submission status: Accepted

Solution code:
N, u, v = map(int,input().split())
u, v = u - 1, v - 1
path = [] 
for _ in range(N):
    path.append([])
for _ in range(N - 1):
    A, B = map(int,input().split())
    A, B = A - 1, B - 1
    path[A].append(B)
    path[B].append(A)
dep = [0] * N
dep[v] = 1
leaf = []
stack2 = [v]
cnt = 2
while stack2:
    stack = stack2[0:]
    stack2 = []
    while stack:
        s = stack.pop()
        for to in path[s]:
            judge = len(path[s])
            if dep[to]:
                judge -= 1
                if judge == 0:
                    leaf.append([cnt - 1, s])
                continue
            dep[to] = cnt
            stack2.append(to)
            judge += 1 
    cnt += 1
leaf.sort(reverse=True)
depmax = [0] * N
for i in range(len(leaf)):
    depth, a = leaf[i][0], leaf[i][1] 
    depmax[a] = depth
    end = False
    for j in range(depth - 1, 0, -1):
        if end:
            break
        for b in path[a]:
            if dep[b] == j:
                if depmax[b] < depmax[a]:
                    depmax[b] = depmax[a]
                    a = b
                    break
                else:
                    end = True
                    break
dis = dep[u] - 2
leng = depmax[u]
a = u
for depth in range(dep[u] - 1, dep[u] - 1 - (dis // 2), -1):
    for to in path[a]:
        if depth == dep[to]:
            leng = depmax[to]
            a = to
print(leng - 2)

Submission status: Accepted

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

n, u, v = [int(x) for x in input().split()]

import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

################################
n, w = n, n - 1 #n:頂点数　w:辺の数

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    x,y = map(int,input().split())
    z = 1
    edge[x - 1].append([z,y - 1])
    edge[y - 1].append([z,x - 1]) 

takahashi = dijkstra_heap(u - 1)
aoki = dijkstra_heap(v - 1)

ans = -1

for i, j in zip(takahashi, aoki):
    if j - i > 0:
        ans = max(ans, j - 1)

print(ans)

Submission status: Accepted

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

n, u, v = [int(x) for x in input().split()]

import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

################################
n, w = n, n - 1 #n:頂点数　w:辺の数

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    x,y = map(int,input().split())
    z = 1
    edge[x - 1].append([z,y - 1])
    edge[y - 1].append([z,x - 1]) 

takahashi = dijkstra_heap(u - 1)
aoki = dijkstra_heap(v - 1)

ans = takahashi[v - 1] - 1 # 高橋君がいもる

idx = 0
for i, j in zip(takahashi, aoki):
    if idx == u - 1 or idx == v - 1:
        idx += 1
        continue
    if j - i > 0:
        ans = max(ans, j - 1)
    idx += 1

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def dijkstra(E, start):
    N_d = len(E)
    dist = [INF] * N_d
    dist[start] = 0
    q = [(0, start)]
    while q:
        dist_v, v = heappop(q)
        if dist[v] != dist_v:
            continue
        for u, dist_vu in E[v]:
            dist_u = dist_v + dist_vu
            if dist_u < dist[u]:
                dist[u] = dist_u
                heappush(q, (dist_u, u))
    return dist

def main():
	N, u, v = MAP()

	tree = [[] for _ in range(N)]
	for _ in range(N-1):
		A, B = MAP()
		tree[A-1].append((B-1, 1))
		tree[B-1].append((A-1, 1))

	d_t = dijkstra(tree, u-1)
	d_a = dijkstra(tree, v-1)
	# print(d_t, d_a)
	ans = -1
	for i in range(N):
		if d_t[i] <= d_a[i]:  # 青木くんより距離が近いか同じところで追いつかれる
			ans = max(ans, d_a[i])
	print(ans-1)

if __name__ == '__main__':
	main()

Submission status: Accepted

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

tree=[]
for i in range(N+1):
  tree.append([])

for i in range(N-1):
  A,B=map(int,input().split())
  tree[A].append(B)
  tree[B].append(A)
#print(u,v)
#print(tree)

dist_tak=[-1]*(N+1)
queue=[u]
d=0
while(len(queue)>0):
  new_queue=set()  
  for q in queue:
    if dist_tak[q]==-1:
      dist_tak[q]=d
      for q2 in tree[q]:
        new_queue.add(q2)
  d+=1
  queue=new_queue
#print(dist_tak)

dist_aok=[-1]*(N+1)
queue=[v]
d=0
while(len(queue)>0):
  new_queue=set()  
  for q in queue:
    if dist_aok[q]==-1:
      dist_aok[q]=d
      for q2 in tree[q]:
        new_queue.add(q2)
  d+=1
  queue=new_queue
#print(dist_aok)

answer=0
for i in range(1,N+1):
  if dist_tak[i]<dist_aok[i]:
    answer=max(answer,dist_aok[i]-1)
    
print(answer)

Submission status: Accepted

Solution code:
N,u,v = map(int,input().split())
E = [[] for _ in range(N + 1)]
for i in range(N-1):
    a,b = map(int,input().split())
    E[a].append(b)
    E[b].append(a)
#print(E)
def bfs(start,N):
    d = [-1]*(N+1)
    d[start] = 0
    q = [start]
    while q:
        #print(d,q)
        v = q.pop()
        cnt = d[v]+1
        for i in E[v]:
            if(d[i] == -1):
                q.append(i)
                d[i] = cnt
    return d
taka = bfs(u,N)
aoki = bfs(v,N)
#print(taka,aoki)
fin = 0
for i in range(N+1):
    if(taka[i] < aoki[i]):
        fin = max(fin,aoki[i])
print(fin - 1)

Submission status: Accepted

Solution code:
import sys
n,u,v=map(int,input().split())
sys.setrecursionlimit(10**9)
tree=[[] for i 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)
a=[None]*n
t=[None]*n
t[u-1]=0
a[v-1]=0
def dfsA(x,c):
  for i in tree[x]:
    if a[i]==None:
      a[i]=c
      dfsA(i,c+1)
dfsA(v-1,1)
k=a[u-1]
def dfsT(x,c):
  global k
  for i in tree[x]:
    if t[i]==None and c<a[i]:
      t[i]=c
      if k<a[i]:
        k=a[i]
      dfsT(i,c+1)
dfsT(u-1,1)
print(k-1)

Submission status: Accepted

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

class Node:
    def __init__(self, num):
        self.link = []
        self.costs = [num, num]
        self.check = False

def clear_nodes(nodes):
    for node in nodes:
        node.check = False

def main():
    N, u, v = map(int, input().split())

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

    for i in range(N-1):
        a, b = map(int, input().split())
        nodes[a].link.append(nodes[b])
        nodes[b].link.append(nodes[a])
    
    starts = [u, v]
    for i in range(2):
        clear_nodes(nodes)
        q = deque()
        q.append((nodes[starts[i]], 0))
        while len(q) > 0:
            node, cost = q.popleft()
            node.costs[i] = cost
            for next_node in node.link:
                if not next_node.check:
                    q.append((next_node, cost + 1))
                    next_node.check = True

    if nodes[u].costs[1] == 1:
        print(0)
        return

    clear_nodes(nodes)
    q = deque()
    ans = 0
    q.append(nodes[u])
    while len(q) > 0:
        node = q.popleft()
        ans = max(ans, node.costs[1])
        for next_node in node.link:
            if (not next_node.check) and next_node.costs[0] < next_node.costs[1]:
                q.append(next_node)
                next_node.check = True
    print(ans - 1)

    


if __name__ == "__main__":
    main()