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:
n = input()    
m = n.split()
p = [int(i) for i in m]
from collections import deque
list = []
for i in range(p[0]-1): #因数注意！
    n = input()    
    m = n.split()
    q = [int(i) for i in m] #1列の数列をリスト化
    list.append(q)
l = [[] for i in range(p[0]+1)]
for pi in list:  #0-originedに注意
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])
sousa = deque([[p[2],0,0]]) #[捜査対象ノード,親ノード,そのノードの距離]
node = [[] for i in range(p[0])] #n番目のリストにn+1について[親ノード,rootからの距離,子ノード]
while len(sousa) != 0:
    a = sousa.popleft()
    b = l[a[0]]
    if a[1]!=0:
        b.remove(a[1])
    if len(b) == 0:
        pass
    else:
        for i in b:
            sousa.append([i,a[0],a[2]+1])
    node[a[0]-1] = [a[1]] + [a[2]] + b
dis = node[p[1]-1][1]
takahashi = p[1]
max = dis
hate = p[1]
for i in range((dis+1)//2):
    tansaku = deque([[takahashi,dis]])
    if i >= 1:
        kitatoko = takahashi
        takahashi = node[takahashi-1][0]
        a = tansaku.popleft()
        b = node[takahashi-1][2:]
        b.remove(kitatoko)
        if len(b) == 0:
            continue
        else:
            for j in b:
                tansaku.append([j,dis+1-i])

    while len(tansaku) != 0:
        a = tansaku.popleft()
        b = node[a[0]-1][2:]
        print()
        if len(b) == 0:
            pass
        else:
            for j in b:
                tansaku.append([j,a[1]+1])

    if max < a[1]:
        max = a[1]
        hate = a[0]
print(node[hate-1][1]-1)

Submission status: Accepted

Solution code:
'''input
3 5
1 2 1
2 3 0
'''
# connected components
from sys import stdin, setrecursionlimit
from bisect import bisect_left
import sys, threading
from collections import defaultdict
sys.setrecursionlimit(10 ** 5 + 1)

def dfs(node, distance, graph, visited, cur):
    visited[node] = True
    distance[node] = cur
    for i in graph[node]:
        if i not in visited:
            dfs(i, distance, graph, visited, cur + 1)


# main start
n, T, A = list(map(int, stdin.readline().split()))
graph = defaultdict(list)
for _ in range(n - 1):
    u, v = list(map(int, stdin.readline().split()))
    graph[u].append(v)
    graph[v].append(u)

T_traverse = [0] * (n + 1)
A_traverse = [0] * (n + 1)
visited = dict()
dfs(T, T_traverse, graph, visited, 0)
visited = dict()
dfs(A, A_traverse, graph, visited, 0)
# print(T_traverse)
# print(A_traverse)
ans = 0
for i in range(1, n + 1):
    if T_traverse[i] <= A_traverse[i]:
        diff = A_traverse[i] - T_traverse[i]
        if diff % 2 == 0:
            for adj in graph[i]:
                if A_traverse[adj] > A_traverse[i] - 1:
                    ans = max(ans, A_traverse[i])
                    break
            else:
                ans = max(ans, A_traverse[i] - 2)
        else:
            ans = max(ans, A_traverse[i] - 1)
print(ans)

Submission status: Accepted

Solution code:
N,U,V=map(int,input().split())
if U==V:
    print(0)
    exit()

G=[[]*N 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)


from collections import deque
def calc(s):
    que=deque()
    que.append(s-1)
    visited=[-1]*N
    visited[s-1]=0
    while que:
        v=que.pop()
        for u in G[v]:
            if visited[u]==-1:
                que.appendleft(u)
                visited[u]=visited[v]+1
    return visited
taka=calc(U)
aoki=calc(V)
#print(taka)
#print(aoki)
ans=0
for i in range(N):
    if taka[i]<=aoki[i]:
        ans=max(ans,aoki[i])

print(ans-1)

Submission status: Accepted

Solution code:
from collections import deque
n, u, v = map(int, input().split())
Tree = [ [] for _ in range(n) ]

def calc(s, tree):
    S = deque([s])
    Dist = [-1]*n
    Dist[s] = 0
    while S:
        u = S.pop()
        for v in tree[u]:
            if Dist[v] < 0:
                Dist[v] = Dist[u] + 1
                S.append(v)
    return Dist

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

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

Submission status: Accepted

Solution code:
from collections import deque

def read():
    N, u, v = list(map(int, input().strip().split()))
    G = [list() for i in range(N+1)]
    for i in range(N-1):
        a, b = list(map(int, input().strip().split()))
        G[a].append(b)
        G[b].append(a)
    return N, u, v, G

def bfs(N, G, start):
    depth = [-1 for i in range(N+1)]
    depth[start] = 0
    q = deque()
    q.append(start)
    while(len(q) > 0):
        s = q.popleft()
        for t in G[s]:
            if depth[t] == -1:
                depth[t] = depth[s] + 1
                q.append(t)
    return depth

def solve(N, u, v, G):
    depth_u = bfs(N, G, u)
    depth_v = bfs(N, G, v)
    most_deepest_node = u
    for i in range(1, N+1):
        if depth_u[i] < depth_v[i]:
            if depth_v[i] > depth_v[most_deepest_node]:
                most_deepest_node = i
    neighbor_node = G[most_deepest_node][0]
    step_u = depth_u[neighbor_node]
    step_v = depth_v[neighbor_node]
    return step_v

if __name__ == '__main__':
    inputs = read()
    print('%d' % solve(*inputs))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
n, runner, chaser = map(int, input().split())
runner -= 1
chaser -= 1
if runner == chaser:
    print(0)
    exit()

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

def dfs(dists, start, d=0, p=-1):  
    dists[start] = d
    for neighbor in tree[start]:
        if neighbor == p:
            continue
        dfs(dists, neighbor, d+1, start)

def dist(start):
    dists = [0 for _ in range(n)]
    dfs(dists, start)
    return dists

furthest = 0
run_dist = dist(runner)
chs_dist = dist(chaser)
for i in range(n):
    if run_dist[i] < chs_dist[i]:
        furthest = max(furthest, chs_dist[i])

ans = furthest-1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 1 << 100
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, u, v = LI()
G = [[] for _ in range(n)]
for a, b in LIR(n - 1):
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]


def bfs(root):
    dq = deque([root])
    dist = [-1] * n
    dist[root] = 0
    while dq:
        u = dq.popleft()
        for v in G[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                dq += [v]
    return dist


dist_u = bfs(u - 1)
dist_v = bfs(v - 1)
ans = 0
for i in range(n):
    if dist_v[i] > dist_u[i]:
        ans = max(ans, dist_v[i] - 1)


print(ans)

Submission status: Accepted

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

dist1 = [100005]*(n+1)

q = []
q.append(v)
dist1[v] = 0
while q:
    now = q.pop()
    for next in tree[now]:
        if dist1[next] == 100005:
            q.append(next)
            dist1[next] = dist1[now] + 1


dist2 = [100005]*(n+1)

q = []
q.append(u)
dist2[u] = 0
while q:
    now = q.pop()
    for next in tree[now]:
        if dist2[next] == 100005:
            q.append(next)
            dist2[next] = dist2[now] + 1

for i in range(1, n+1):
    if dist1[i] <= dist2[i]:
        dist2[i] = -1

for i in range(1, n+1):
    if dist2[i] != -1:
        dist2[i] = 100005

q = []
q.append(u)
dist2[u] = 0
while q:
    now = q.pop()
    for next in tree[now]:
        if dist2[next] == 100005:
            q.append(next)
            dist2[next] = dist2[now] + 1



ans = 0
for i in range(1, n+1):
    if dist2[i] != -1:
        ans = max(ans, dist1[i])

print(ans-1)

Submission status: Accepted

Solution code:
from collections import deque
N, u, v = map(int, input().split())
u, v = u-1, v-1
AB = [list(map(int, input().split())) for a in range(N-1)]

G = [[] for a in range(N)]

for ab in AB:
  G[ab[0]-1].append(ab[1]-1)
  G[ab[1]-1].append(ab[0]-1)

qA = deque([v])
qT = deque([u])
costsA = [0 for a in range(N)]
doneA = [0 for a in range(N)]
costsT = [0 for a in range(N)]
doneT = [0 for a in range(N)]

doneA[v] = 1
doneT[u] = 1

def bfs(q, costs, done):
  while q:
    start = q.popleft()
    for i in G[start]:
      if done[i] == 0:
        q.append(i)
        costs[i] = costs[start] + 1
        done[i] = 1

bfs(qA, costsA, doneA)
bfs(qT, costsT, doneT)

distances = [0]
for i in range(N):
  if costsA[i] > costsT[i]:
    distances.append(costsA[i])

print(max(distances)-1)

Submission status: Accepted

Solution code:
from collections import defaultdict


def dfs(N, tree, v):
    s = []
    done = [False for _ in range(N)]
    dist = [0 for _ in range(N)]

    done[v] = True
    dist[v] = 0
    s.append(v)

    while 0 < len(s):
        v = s.pop()

        # process
        # print(v, tree[v], dist[v])

        for i in tree[v]:
            if not done[i]:
                done[i] = True
                dist[i] = dist[v] + 1
                s.append(i)

    return dist


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

    tree = defaultdict(list)

    for _ in range(N - 1):
        A, B = map(int, input().split())
        A -= 1
        B -= 1

        tree[A].append(B)
        tree[B].append(A)

    u_dist = dfs(N, tree, u)
    v_dist = dfs(N, tree, v)
    # print(u_dist)
    # print(v_dist)

    ans = 0
    for u1, v1 in zip(u_dist, v_dist):
        if u1 < v1:
            ans = max(ans, v1 - 1)

    print(ans)


main()

Submission status: Accepted

Solution code:
N, u, v = map(int, input().split())
tree = [[] for i in range(N + 1)]
for _ in range(N - 1):
	a, b = map(int, input().split())
	tree[a].append(b)
	tree[b].append(a)
    
def dfs(v: int, tree: int, N: int) -> int:
    dist = [-1] * (N + 1)
    dist[v] = 0
    stack = [v]
    
    while stack:
        now = stack.pop()
        dw = dist[now] + 1
        
        for ne in tree[now]:
            if dist[ne] >= 0:
                continue
            dist[ne] = dw
            stack.append(ne)
            
    return dist

T = dfs(u, tree, N)
A = dfs(v, tree, N)

ans = 0
for t, a in zip(T[1:], A[1:]):
    if t < a:
        ans = max(ans, a - 1)
print(ans)

Submission status: Accepted

Solution code:
# 写経
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, u, v = map(int, readline().split())
m = map(int, read().split())
AB = zip(m, m)

graph = [[] for _ in range(n + 1)]
for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)


def dfs(v):
    dist = [-1] * (n + 1)
    # 初期化
    stack = [v]
    # 初期位置を記憶
    dist[v] = 0
    # 初期位置の距離を0に
    while stack:
        # stackの中身がなくなるまで頑張る
        v = stack.pop()
        # stackから1つ要素を取り出す
        dw = dist[v] + 1
        # その要素の周りを考えるので、距離としてはその要素の距離に1を加えたものを考える
        for w in graph[v]:
            # 考えている要素に対して隣接している点に対して
            if dist[w] >= 0:
                # もし今まで訪れたことがあったら無視
                continue
            dist[w] = dw
            # 訪れたことがなかったら距離を更新
            stack.append(w)
            # 訪れたことがないところだったらstackに訪れる点リストとして保存
    return dist


answer = 0
du, dv = dfs(u), dfs(v)
for u, v in zip(du[1:], dv[1:]):
    if v - u > 0:
        x = v - 1
        if answer < x:
            answer = x
print(answer)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from collections import defaultdict
import json
from copy import deepcopy
import sys
sys.setrecursionlimit(10**4)

def dfs(graph, s):
  dist = [-1 for _ in range(len(graph))]
  dist[s] = 0
  stack = [s]
  while len(stack) != 0:
    s = stack.pop()
    for t in graph[s]:
      dist[t] = dist[s]+1
      if s in graph[t]:
        graph[t].remove(s)
      stack.append(t)
  return dist

if __name__=='__main__':
  graph = defaultdict(list)
  n, u, v = map(int, input().strip().split())
  for _ in range(n-1):
    ai, bi = map(int, input().strip().split())
    graph[ai-1].append(bi-1)
    graph[bi-1].append(ai-1)
  du = dfs(deepcopy(graph), u-1)
  dv = dfs(deepcopy(graph), v-1)
  costv = [0]
  for duv, dvv in zip(du, dv):
    if duv < dvv:
      costv.append(dvv)
  print(max(costv) - 1)

Submission status: Accepted

Solution code:
from collections import defaultdict

# def find_distances(edge_dict, node, distances):
#     for end in edge_dict[node]:
#         if distances[end] < 0:
#             distances[end] = distances[node] + 1
#             distances = find_distances(edge_dict, end, distances)

#     return distances


def find_distances(edge_dict, node, V):
    distances = [-1] * V
    stack = [(0, node)]

    while stack:
        dist, node = stack.pop()
        if distances[node] >= 0:
            continue

        distances[node] = dist
        for end in edge_dict[node]:
            stack.append((dist + 1, end))

    return distances

if __name__ == "__main__":
    V, T, A = map(int, input().split())
    T -= 1
    A -= 1
    edge_dict = defaultdict(list)

    for _ in range(V - 1):
        start, end = map(int, input().split())
        edge_dict[start - 1].append(end - 1)
        edge_dict[end - 1].append(start - 1)
    
    dist_T = [-1] * V
    dist_T[T] = 0
    dist_T = find_distances(edge_dict, T, V)

    dist_A = [-1] * V
    dist_A[A] = 0
    dist_A = find_distances(edge_dict, A, V)

    max_dist = 0
    for i in range(V):
        if dist_T[i] <= dist_A[i]:
            max_dist = max(max_dist, dist_A[i])
    
    print(max_dist - 1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#写経
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

#　縦に並んだ入力を受け取りたい時はread().split()をとる zip(m,m)で分ける
N,U,V = map(int,readline().split())
m = map(int,read().split())
AB = zip(m,m)

#tree の受け取り：頂点の数＋１のリストを用意して、それぞれの頂点が辺を貼るnodeを全てリストに保存
graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
#全探索して入力頂点からの距離を返す
#全ての頂点に対して、
def dfs(v):
    dist = [-1] * (N+1)
    stack = [v]
    dist[v] = 0
    while stack:
        v = stack.pop()
        dw = dist[v] + 1
        for w in graph[v]:#頂点から辺が貼られている頂点に対して
            if dist[w] >= 0:#すでに訪れている
                continue
            dist[w] = dw#訪れてないなら更新
            stack.append(w)
    return dist

DU,DV = dfs(U),dfs(V)
 
answer = 0
#元の場所以外の全ての頂点を探索する
for u,v in zip(DU[1:],DV[1:]):
    if u < v:#逃げる方が先につく中で最短を探す
        x = v - 1
        if answer < x:
            answer = x
 
print(answer)

Submission status: Accepted

Solution code:
import sys

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

def dfs(v):
    dist = [-1] * (n+1)
    dist[v] = 0
    stack = [v]
    while stack:
        now = stack.pop()
        dw = dist[now] + 1
        for ne in graph[now]:
            if dist[ne] >= 0:
                continue
            dist[ne] = dw
            stack.append(ne)
    return dist

Takahashi = dfs(u)
Aoki = dfs(v)

ans = 0
for t, a in zip(Takahashi[1:], Aoki[1:]):
    if t < a:
        ans = max(ans, a - 1)

print(ans)

Submission status: Accepted

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

def dfs(node):
	sta = [node]
	dis = [-1] * (N + 1)
	dis[node] = 0
	while sta:
		no = sta.pop()
		tempD = dis[no] + 1
		for tempN in tree[no]:
			if dis[tempN] < 0:
				dis[tempN] = tempD
				sta.append(tempN)
	else:
		return dis

disU = dfs(u)
disV = dfs(v)
ans = 0

for u_, v_ in zip(disU[1:], disV[1:]):
	if u_ < v_:
			ans = max(ans, v_)
else:
	print(ans - 1)

Submission status: Accepted

Solution code:
#入力
n, u, v = map(int, input().split())
mapdata = [list(map(int,input().split())) for _ in range(n-1)]

#グラフ作成
graph = [[] for _ in range(n+1)]
for i, j in mapdata:
  graph[i].append(j)
  graph[j].append(i)

#探索
def dfs(v):
  dist = [-1] * (n + 1)
  stack = [v]
  dist[v] = 0
  while stack:
    v = stack.pop()
    dw = dist[v] + 1
    for w in graph[v]:
      if dist[w] >= 0:
        continue
      dist[w] = dw
      stack.append(w)
  return dist

du, dv = dfs(u), dfs(v)
ans = 0

for u, v in zip(du[1:], dv[1:]):
  if u < v:
    x = v-1
    if ans < x:
      ans = x

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,x,y=map(int,input().split())
    x-=1; y-=1
    E1=[[] for _ in range(n)]
    E2=[[] for _ in range(n)]
    for _ in range(n-1):
        u,v=map(int,input().split())
        u-=1; v-=1
        E1[u].append(v)
        E1[v].append(u)
    E2=E1

    # E2 において、y-rooted tree とみて、depth,par を計算
    par=[None]*n # x の必勝頂点を判定するのに必要
    par[y]=y
    depth2=[None]*n
    depth2[y]=0
    Q=[y]
    while(Q):
        v=Q.pop()
        for nv in E2[v]:
            if(depth2[nv] is not None): continue
            depth2[nv]=depth2[v]+1
            par[nv]=v
            Q.append(nv)

    # E1の辺で、E2での距離が 3 以上のものは必勝
    win=[0]*n
    for v in range(n):
        for nv in E1[v]:
            if(par[v]==nv or par[nv]==v or par[v]==par[nv] or par[par[v]]==nv or par[par[nv]]==v): continue
            win[nv]=win[v]=1

    # E1 において、x-rooted tree とみて探索
    # depth1 < depth2 -> 以降も探索できる
    # depth1 = depth2 -> そこで捕まる
    ans=depth2[x]
    depth1=[None]*n
    depth1[x]=0
    Q=[x]
    while(Q):
        v=Q.pop()
        if(win[v]): # 探索できる状態 & 必勝頂点にいれば勝ち
            print(-1)
            return
        for nv in E1[v]:
            if(depth1[nv] is not None): continue
            depth1[nv]=depth1[v]+1
            ans=max(ans,depth2[nv])
            if(depth1[nv]<depth2[nv]): Q.append(nv)

    print(ans-1)
resolve()

Submission status: Accepted

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

for _ in range(N-1):
    A, B = map(int, input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)

# 1つしかつながる頂点がないものを葉とする
isLeaf, dU, dV = [len(g) == 1 for g in G], [-1]*N, [-1]*N

for D, P in [(dU, u-1), (dV, v-1)]:
    S = [(P, 0)]
    while len(S) > 0:
        p, d = S.pop()
        D[p] = d # その頂点になんパスでいけるか記録
        # 今いる場所から行ける頂点がまだ行ったことのないところならキューに追加
        for g in G[p]:
            if D[g] == -1:
                S.append((g, d+1))

ans = 0
# 全頂点のうち、葉（端っこの頂点）であり、かつ、高橋くんの方が青木くんより先につける頂点のうち最大のものが2人が目指す頂点
# 最終的に高橋くんが自ら捕まりにいくので、その頂点1歩手前が答え
for i in range(N):
    if isLeaf[i] and dU[i] < dV[i]:
        ans = max(ans, dV[i]-1)

print(ans)

Submission status: Accepted

Solution code:
N, u, v = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N-1)]
 
#グラフ作成部
graph = [[] for i in range(N+1)]
for i,j in AB:
    graph[i].append(j)
    graph[j].append(i)
 
#深さ優先探索
def dfs(v):
    dist = [-1] * (N+1)
    stack = [v]
    dist[v] = 0
    while stack:
        v = stack.pop()
        dw = dist[v] + 1
        for w in graph[v]:
            if dist[w] >= 0:
                continue
            dist[w] = dw
            stack.append(w)
    return dist
 
DU,DV = dfs(u),dfs(v)
 
answer = 0
for u,v in zip(DU[1:],DV[1:]):
    if u < v:
        x = v - 1
        if answer < x:
            answer = x
 
print(answer)

Submission status: Accepted

Solution code:
import heapq

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

du = [float('inf')]*N
dv = [float('inf')]*N
G = [[]]*N

def calcDist(s, dist):
    q = []
    heapq.heappush(q,[0, s])
    dist[s] = int(0)
    
    while q!=[]:
        p = heapq.heappop(q)
        pv = p[1]
        if dist[pv] < p[0] :
            continue
        for eto in G[pv]:
            if dist[eto] > dist[pv] + 1:
                 dist[eto] = int(dist[pv] + 1)
                 heapq.heappush(q, [dist[eto], eto])


for i in range(N-1):
    e1,e2 = map(int, input().split())
    e1 -= 1
    e2 -= 1
    if G[e1] == []:
        G[e1] = [e2]
    else:
        G[e1].append(e2)
    if G[e2] == []:
        G[e2] = [e1]
    else:
        G[e2].append(e1)

if v in G[u]:
    ans = 0
else:    

    calcDist(v,dv)
    calcDist(u,du)
    maxD = 0
    for idu,idv in zip(du,dv):
        if idu < idv:
            maxD = max(maxD, idv)       
    ans = maxD-1
    
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

du = [float('inf')]*N
dv = [float('inf')]*N
G = [[]]*N

def calcDist(s, dist):
    q = []
    heapq.heappush(q,[0, s])
    dist[s] = int(0)
    
    while q!=[]:
        p = heapq.heappop(q)
        pv = p[1]
        if dist[pv] < p[0] :
            continue
        for i in range(len(G[pv])):
            eto = G[pv][i]
            if dist[eto] > dist[pv] + 1:
                 dist[eto] = int(dist[pv] + 1)
                 heapq.heappush(q, [dist[eto], eto])


for i in range(N-1):
    e1,e2 = map(int, input().split())
    e1 -= 1
    e2 -= 1
    if G[e1] == []:
        G[e1] = [e2]
    else:
        G[e1].append(e2)
    if G[e2] == []:
        G[e2] = [e1]
    else:
        G[e2].append(e1)

if v in G[u]:
    ans = 0
else:    

    calcDist(v,dv)
    calcDist(u,du)
    maxD = 0
    for idu,idv in zip(du,dv):
        if idu < idv:
            maxD = max(maxD, idv)       
    ans = maxD-1
    
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

#du = [0]*N
#dv = [0]*N
du = [float('inf')]*N
dv = [float('inf')]*N
#du[u] = 0
#dv[v] = 0
q = []

G = [[]]*N

'''
def dfs(v, d, p, dis):
    dis[v] = d
    if G[v] != []:
        for u in G[v]:
            if( u == p):
                continue
            else:
                dfs( u, d+1, v, dis )

def calcDist(s, dist):
    dfs(s, 0, -1, dist)
'''
def calcDist(s, dist):
    heapq.heappush(q,[0, s])
    dist[s] = int(0)
    
    while q!=[]:
        p = heapq.heappop(q)
        pv = p[1]
        if dist[pv] < p[0] :
            continue
        for i in range(len(G[pv])):
            eto = G[pv][i]
            if dist[eto] > dist[pv] + 1:
                 dist[eto] = int(dist[pv] + 1)
                 heapq.heappush(q, [dist[eto], eto])


for i in range(N-1):
    e1,e2 = map(int, input().split())
    e1 -= 1
    e2 -= 1
    if G[e1] == []:
        G[e1] = [e2]
    else:
        G[e1].append(e2)
    if G[e2] == []:
        G[e2] = [e1]
    else:
        G[e2].append(e1)

if v in G[u]:
    ans = 0
else:    

    calcDist(v,dv)
    calcDist(u,du)
    maxD = 0
    for idu,idv in zip(du,dv):
        if idu < idv:
            maxD = max(maxD, idv)       
    ans = maxD-1
    
print(ans)

Submission status: Accepted

Solution code:
#読み込み部
N, u, v = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N-1)]

#グラフ作成部
graph = [[] for i in range(N+1)]
for i,j in AB:
    graph[i].append(j)
    graph[j].append(i)

#深さ優先探索
def dfs(v):
    dist = [-1] * (N+1)
    stack = [v]
    dist[v] = 0
    while stack:
        v = stack.pop()
        dw = dist[v] + 1
        for w in graph[v]:
            if dist[w] >= 0:
                continue
            dist[w] = dw
            stack.append(w)
    return dist

DU,DV = dfs(u),dfs(v)
 
answer = 0
for u,v in zip(DU[1:],DV[1:]):
    if u < v:
        x = v - 1
        if answer < x:
            answer = x

print(answer)

Submission status: Accepted

Solution code:
def p_f():
    from sys import stdin
    input = stdin.readline
    N, u, v = map(int, input().split())
    edges = [list(map(int, input().split())) for i in range(N - 1)]
    if u == v:
        print(0)
        exit()

    def BFS(K, edges, N):
        roots = [[] for i in range(N)]
        for a, b in edges:
            roots[a - 1] += [(b - 1, 1)]
            roots[b - 1] += [(a - 1, 1)]
        dist = [-1] * N
        stack = []
        stack.append(K)
        dist[K] = 0
        while stack:
            label = stack.pop(-1)
            for i, c in roots[label]:
                if dist[i] == -1:
                    dist[i] = dist[label] + c
                    stack += [i]
        return dist

    dist_v = BFS(v - 1, edges, N)
    dist_u = BFS(u - 1, edges, N)
    ans = 0
    for du, dv in zip(dist_u, dist_v):
        if du < dv and ans < dv - 1:
            ans = dv - 1
    print(ans)


if __name__ == '__main__':
    p_f()

Submission status: Accepted

Solution code:
from collections import deque

def BFS(t):
    tree=[[] for i in range(n)]
    for i in list:
      tree[i[0]-1].append(i[1]-1)
      tree[i[1]-1].append(i[0]-1)

    dist=[-1 for i in range(n)]
    dist[t-1]=0

    que=deque()
    que.append(t-1)
    while que:
        x=que.popleft()
        for p in tree[x]:
            if dist[p]==-1:
                que.append(p)
                dist[p]=dist[x]+1
    return dist

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

u_dist=BFS(u)
v_dist=BFS(v)

l=0
for u_d,v_d in zip(u_dist,v_dist):
 if u_d<v_d:
  l=max(l,v_d)

print(l-1)

Submission status: Accepted

Solution code:
from collections import deque

INF = 1000000
N,T,A=map(int,input().split())
T -= 1
A -= 1
G = [ [] for i in range(N) ]
DT = [ INF for _ in range(N) ]
DA = [ INF for _ in range(N) ]
for i in range(N-1):
    h1,h2=map(int,input().split())
    h1 -= 1
    h2 -= 1
    G[h1].append(h2);
    G[h2].append(h1);

DT[T] = 0
DA[A] = 0

q = deque()

# BFS
q.append(T)
while len(q) > 0:
    v = q.popleft()
    for nv in G[v]:
        if DT[nv] == INF:
            DT[nv] = DT[v] + 1
            q.append(nv)

q.clear()
q.append(A)
while len(q) > 0:
    v = q.popleft()
    for nv in G[v]:
        if DA[nv] == INF:
            DA[nv] = DA[v] + 1
            q.append(nv)

max_da = 0
for i in range(N):
    #print(i, " T:", DT[i], " A:", DA[i])
    if DA[i] - DT[i] >= 1 :
        max_da = max(DA[i], max_da)
print(max_da-1)

Submission status: Accepted

Solution code:
import sys, heapq
from collections import defaultdict
from itertools import product, permutations, combinations

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

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



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

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

adjl = [[] for _ in range(N)]
for ab in AB:
    a, b = ab[0]-1, ab[1]-1
    adjl[a].append([1, b])
    adjl[b].append([1, a])

du = dijkstra_heap(u-1, adjl)
dv = dijkstra_heap(v-1, adjl)
dOK = [j for i, j in zip(du, dv) if i < j]

print(int(max(dOK)-1))

Submission status: Accepted

Solution code:
import sys

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

def dfs(v):
    dist = [-1] * (n+1)
    dist[v] = 0
    stack = [v]
    while stack:
        now = stack.pop()
        dw = dist[now] + 1
        for ne in graph[now]:
            if dist[ne] >= 0:
                continue
            dist[ne] = dw
            stack.append(ne)
    return dist

Takahashi = dfs(u)
Aoki = dfs(v)

ans = 0
for t, a in zip(Takahashi[1:], Aoki[1:]):
    if t < a:
        ans = max(ans, a - 1)

print(ans)

Submission status: Accepted

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

Leaf = []  # 葉かどうかを記録する
for i in range(N):
    c = 0
    for j in L[i]:
        c = c + 1
    if c == 1:
        Leaf.append(True)
    else:
        Leaf.append(False)

UD = [0 for i in range(N)]  # 各頂点のuからの距離
UD[u - 1] = -1  # 0でないなら訪問済みとする
M = L[u - 1]  # 次に訪れるノードのリスト
d = 1  # uからの距離
while True:
    new_M = []
    for i in M:
        if UD[i] == 0:  # 0 ならiに隣接するノードをnew_Mに追加
            UD[i] = d
            for j in L[i]:
                new_M.append(j)
        else:
            pass
    M = new_M
    if len(M) == 0:
        break
    d = d + 1
UD[u-1] = 0

VD = [0 for i in range(N)]
VD[v-1] = -1
M = L[v-1]
d = 1

while True:
    new_M = []
    for i in M:
        if VD[i] == 0:  # 0 ならiに隣接するノードをnew_Mに追加
            VD[i] = d
            for j in L[i]:
                new_M.append(j)
        else:
            pass
    M = new_M
    if len(M) == 0:
        break
    d = d + 1
VD[v-1] = 0




d = -1
index = u-1
# vよりもuの方が近く,最もvから離れている葉を見つける
for i in range(N):
    if Leaf[i]:
        if UD[i] < VD[i]:
            if d < VD[i]:
                d = VD[i]

print(d-1)