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:
import sys
sys.setrecursionlimit(200000)

N, s, t = map(int, input().split())
s -= 1; t -= 1
to = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    to[a].append(b)
    to[b].append(a)

def calcDist(u):
    dfs(u)
    return dist

def dfs(v, d=0, p=-1):
    dist[v] = d
    for u in to[v]:
        if u == p:
            continue
        dfs(u, d+1, v)

dist = [0 for _ in range(N)]
distS = calcDist(s)
dist = [0 for _ in range(N)]
distT = calcDist(t)

ans = 0
for i in range(N):
    if distS[i] < distT[i]:
        ans = max(ans, distT[i])

print(ans-1)

Submission status: Accepted

Solution code:
import queue

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

path = [[] for i in range(n)]

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

t = [10**9]*n
t[u]=0
q = queue.Queue()

q.put(u)

while not q.empty():
    p = q.get()
    for x in path[p]:
        if t[x]>t[p]+1:
            q.put(x)
            t[x]=t[p]+1

a = [10**9]*n
a[v]=0
q = queue.Queue()

q.put(v)

while not q.empty():
    p = q.get()
    for x in path[p]:
        if a[x]>a[p]+1:
            q.put(x)
            a[x]=a[p]+1

c = [a[i] for i in range(n) if a[i]>t[i]]
print(max(c)-1)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,st,sa=f()
g=[set() for _ in range(n)]
for _ in range(n-1):
  a,b=f()
  g[a-1].add(b-1)
  g[b-1].add(a-1)
def bfs(s):
  l=[-1]*n; l[s]=0; q=[s]
  while q:
    v=q.pop(); d=l[v]+1
    for c in g[v]:
      if l[c]<0: l[c]=d; q+=[c]
  return l
lt=bfs(st-1)
la=bfs(sa-1)
print(max(la[i] for i in range(n) if lt[i]<la[i])-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
f=lambda:map(int,sys.stdin.readline().split())
n,st,sa=f()
g=[set() for _ in range(n)]
for _ in range(n-1):
  a,b=f()
  g[a-1].add(b-1)
  g[b-1].add(a-1)
def dfs(l,v,p=-1,d=0):
  l[v]=d
  for c in g[v]:
    if c!=p: dfs(l,c,v,d+1)
lt=[0]*n
dfs(lt,st-1)
la=[0]*n
dfs(la,sa-1)
print(max(la[i] for i in range(n) if lt[i]<la[i])-1)

Submission status: Accepted

Solution code:
import sys
f=lambda:map(int,sys.stdin.readline().split())
n,st,sa=f()
st-=1
sa-=1
g=[[] for _ in range(n)]
for _ in range(n-1):
  a,b=f()
  g[a-1].append(b-1)
  g[b-1].append(a-1)
def bfs(s):
  l=[-1]*n; l[s]=0; q=[s]
  while q:
    v=q.pop(); d=l[v]+1
    for c in g[v]:
      if l[c]<0: l[c]=d; q+=[c]
  return l
lt=bfs(st)
la=bfs(sa)
m=0
for i in range(n):
  if lt[i]<la[i]: m=max(m,la[i])
print(m-1)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,st,sa=f()
st-=1
sa-=1
g=[[] for _ in range(n)]
for _ in range(n-1):
  a,b=f()
  g[a-1].append(b-1)
  g[b-1].append(a-1)
def bfs(s):
  l=[-1]*n; l[s]=0; q=[s]
  while q:
    v=q.pop(); d=l[v]+1
    for c in g[v]:
      if l[c]<0: l[c]=d; q+=[c]
  return l
lt=bfs(st)
la=bfs(sa)
m=0
for i in range(n):
  if lt[i]<la[i]: m=max(m,la[i])
print(m-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
f=lambda:map(int,input().split())
n,st,sa=f()
st-=1
sa-=1
g=[[] for _ in range(n)]
for _ in range(n-1):
  a,b=f()
  g[a-1].append(b-1)
  g[b-1].append(a-1)
def dfs(v,p=-1,d=0):
  l[v]=d
  for c in g[v]:
    if c==p: continue
    dfs(c,v,d+1)
def dist(s):
  global l
  l=[0]*n
  dfs(s)
  return l
lt=dist(st)
la=dist(sa)
m=0
for i in range(n):
  if lt[i]<la[i]: m=max(m,la[i])
print(m-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**5)
def input(): return sys.stdin.readline().strip()

"""
Pypyは再帰が遅いらしいのでPythonで通してみる
"""

def main():
    N, u, v = map(int, input().split())
    u -= 1
    v -= 1
    repn = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b = map(int, input().split())
        repn[a - 1].append((b - 1, i))
        repn[b - 1].append((a - 1, i)) # (to, id)

    """
    まずu, vを結ぶ単純パス上にあるnodeを列挙する。
    これはvを根とする根付き木に対するdfs（再帰）により求まる（参考：ABC152F）
    """

    path = []
    def connected(v, tv, p=-1):
        if v == tv:
            return True
        for w, _ in repn[v]:
            if w == p:
                continue
            elif connected(w, tv, v):
                path.append(w)
                return True
        return False
    connected(v, u)
    path.append(v)
    #print("path={}".format(path))

    """
    次にu, vを結ぶ単純パスP上の各頂点wに対して、wからPに沿わない向きにどれだけ深く潜れるかを求める。
    しかし最終的には「頂点vから（高橋君が逃げ込める中で）最も遠い頂点」を求めればよいので、
    uvの中点からdfsすれば十分。
    """

    def dfs(v, p): # Pと異なる頂点方向にdfsして深さを求める
        d = -1
        for w, _ in repn[v]:
            if w == p:
                continue
            else:
                d = max(d, dfs(w, v))
        return d + 1
    
    dist = len(path)
    mid = path[dist // 2 - 1]
    par = path[dist // 2]
    ans = dfs(mid, par)
    print(ans + (dist - 1) // 2)
   


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline().strip()

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

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)

from queue import Queue

# 青木君によるWFS
aoki = [-1 for _ in range(n)]
aoki[v] = 0
todo = Queue()
todo.put(v)
while not todo.empty():
    i = todo.get()
    for j in tree[i]:
        if aoki[j] == -1:
            todo.put(j)
            aoki[j] = aoki[i] + 1

# 高橋君によるWFS
taka = [-1 for _ in range(n)]
taka[u] = 0
todo = Queue()
todo.put(u)
while not todo.empty():
    i = todo.get()
    for j in tree[i]:
        if taka[j] == -1:
            if taka[i] + 1 < aoki[j]:
                todo.put(j)
            taka[j] = taka[i] + 1

# search
ans = 0
for i in range(n):
    if taka[i] != -1:
        if aoki[i] - 1 > ans:
            ans = aoki[i] - 1

print(ans)

Submission status: Accepted

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

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)

from queue import Queue

# 青木君によるWFS
aoki = [-1 for _ in range(n)]
aoki[v] = 0
todo = Queue()
todo.put(v)
while not todo.empty():
    i = todo.get()
    for j in tree[i]:
        if aoki[j] == -1:
            todo.put(j)
            aoki[j] = aoki[i] + 1

# 高橋君によるWFS
taka = [-1 for _ in range(n)]
taka[u] = 0
todo = Queue()
todo.put(u)
while not todo.empty():
    i = todo.get()
    for j in tree[i]:
        if taka[j] == -1:
            if taka[i] + 1 < aoki[j]:
                todo.put(j)
            taka[j] = taka[i] + 1

# search
ans = 0
for i in range(n):
    if taka[i] != -1:
        if aoki[i] - 1 > ans:
            ans = aoki[i] - 1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,u,v=map(int,input().split())
edge=[[] for i in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
visitedu=[-1]*n
visitedv=[-1]*n
def bfs(s,visited):
    q=deque([s])
    visited[s]=0
    while q:
        x=q.popleft()
        for nx in edge[x]:
            if visited[nx]==-1:
                visited[nx]=visited[x]+1
                q.append(nx)
    return
bfs(u-1,visitedu)
bfs(v-1,visitedv)
a=0
b=10**10
for i in range(n):
    if visitedu[i]<visitedv[i]:
        a=max(a,visitedv[i])
    elif visitedu[i]==visitedv[i]:
        b=min(b,visitedv[i])
#print(visitedv)
#print(visitedu)
if b==10**10:
    b=-1
if a<=b:
    print(b)
else:
    print(a-1)

Submission status: Accepted

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

parent={i:-1 for i in range(1,N+1)}
depth={i:-1 for i in range(1,N+1)}
parent[v]=0
depth[v]=0
q=set([v])
sub=set([])
while q:
    while q:
        x=q.pop()
        for i in edge[x]:
            if parent[i]==-1:
                parent[i]=x
                depth[i]=depth[x]+1
                sub.add(i)

        if not q:
            q=sub
            sub=set([])
            break

if depth[u]%2==1:
    i=depth[u]//2
    stand=u
    while i>0:
        stand=parent[stand]
        i-=1
    test=depth[stand]
    q=set([stand])
    sub=set([])
    while q:
        while q:
            x=q.pop()
            for i in edge[x]:
                if i!=parent[x]:
                    test=max(test,depth[i])
                    sub.add(i)

            if not q:
                q=sub
                sub=set([])
                break

    print(test-1)
else:
    i=depth[u]//2-1
    stand=u
    while i>0:
        stand=parent[stand]
        i-=1
    test=depth[stand]
    q=set([stand])
    sub=set([])
    while q:
        while q:
            x=q.pop()
            for i in edge[x]:
                if i!=parent[x]:
                    test=max(test,depth[i])
                    sub.add(i)

            if not q:
                q=sub
                sub=set([])
                break

    print(test-1)

Submission status: Accepted

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

def dfs(G, v, p, d, depth):
    depth[v] = d
    for nv in G[v]:
        if nv == p:
            continue
        dfs(G, nv, v, d+1, depth)
    return G, depth


n, T, A = map(int,input().split())
T, A = T-1, A-1
g = [[] for _ in range(n)]
for i in range(n-1):
    x, y = map(int,input().split())
    x, y = x-1, y-1
    g[x].append(y)
    g[y].append(x)

depth = [0]*n
GT = copy.deepcopy(g)
GT[T].append(-1)
GT, dt = dfs(GT, T, -1, 0, depth)

depth = [0]*n
GA = copy.deepcopy(g)
GA[A].append(-1)
GA, da = dfs(GA, A, -1, 0, depth)

ans = 0
for t, a in zip(dt, da):
    if t <= a:
        ans = max(ans, a)
print(ans-1)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(s):
    q = deque()
    q.append(s)
    dist = [-1] * (n + 1)
    dist[s] = 0
    while q:
        p = q.popleft()
        for i in G[p]:
            if dist[i] == -1:
                dist[i] = dist[p] + 1
                q.append(i)
    return dist

n, u, v = map(int, input().split())
G = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
dist1 = bfs(u)
dist2 = bfs(v)
ans = 0
for i in range(1, n + 1):
    if dist1[i] <= dist2[i]:
        ans = max(ans, dist2[i] - 1)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
N, u, v = map(int, input().split())

E = [[] for _ in range(N+1)]
for _ in range(N-1):
	ta, tb = map(int, input().split())
	E[ta].append(tb)
	E[tb].append(ta)
E = np.array(E)

inf = 10**9
taka = np.full(N+1, inf, dtype = np.int64)
ao = np.full(N+1, inf, dtype = np.int64)
taka[u] = 0
ao[v] = 0
def solve(dist, start):
	q = [start]
	while q:
		cp = q.pop()
		for nep in E[cp]:
			if dist[nep] != inf:
				continue
			else:
				dist[nep] = dist[cp] + 1
				q.append(nep)

solve(taka, u)
solve(ao, v)
ind = taka < ao
ao_max = np.max(ao[ind])
print(ao_max - 1)

Submission status: Accepted

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

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

for x,y in a:
    b[x-1].append(y-1)
    b[y-1].append(x-1)

import collections
from collections import deque
def tree(s):

    INF=-10**9
    dis = [INF for i in range(n)]
    dis[s]=0
    def bfs():
        d = deque()
        d.append(s)

        while len(d):
            x = d.popleft()

            for i in range(len(b[x])):
                y=b[x][i]
                if dis[y] == INF:
                    d.append(y)
                    dis[y]=dis[x]+1


        return dis
    return bfs()

# q1:高橋くんからの最短距離、q2:青木君からの最短距離
q1=tree(u-1)
q2=tree(v-1)
ans=0

for i in range(n):
    if q2[i]>q1[i]:
        ans=max(q2[i],ans)
print(ans-1)

Submission status: Accepted

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

from collections import deque, defaultdict

#以下０オリジンで考える

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

G = defaultdict(lambda:deque([])) #連結リスト

#以下０オリジンで考える
for _ in range(n-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    
#start位置から繋がる全ノードへの距離を求める関数、幅優先探索
#dst_dict[player][node]がplayerとnodeの距離
def bfs(start, player):
    que = deque([(start, -1, 0)])
    while que:
        node, par, dst = que.popleft() #par:親, dst:距離
        if len(G[node]) == 1:
            dst_dict[player][node] = dst
            
        for nxt in G[node]:
            if nxt == par:
                continue
            que.append((nxt, node, dst+1))
            
dst_dict = [{}, {}]

bfs(u, 0)
bfs(v, 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:
# even faster by using a comprehensive list at the end

from collections import deque
import sys
si = sys.stdin.readline


def BFS(g, n, s):
    d = 0
    dt = [0 for _ in range(n+1)]
    dt[s] = 0
    visited = set()
    visited.add(s)
    Q = deque([s])

    while len(Q):
        d += 1
        Qs = len(Q)
        for _ in range(Qs):
            Qpop = Q.popleft()
            for node in g[Qpop]:
                if node not in visited:
                    Q.append(node)
                    visited.add(node)
                    dt[node] = d
    return dt[1:]


def main():
    l = [int(e) for e in si().split()]
    n, u, v = l[0], l[1], l[2]
    graph = [[] for _ in range(n+1)]
    for _ in range(n-1):
        l = [int(e) for e in si().split()]
        graph[l[0]].append(l[1])
        graph[l[1]].append(l[0])

    udt = BFS(graph, n, u)
    vdt = BFS(graph, n, v)
    print(-1+max([v for u, v in zip(udt, vdt) if u < v]))


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def BFS(g, s):
    d = 0
    dt = dict()
    visited = set()
    visited.add(s)
    Q = deque([s])

    while len(Q):
        d += 1
        Qs = len(Q)
        for _ in range(Qs):
            Qpop = Q.popleft()
            for node in g[Qpop]:
                if node not in visited:
                    Q.append(node)
                    visited.add(node)
                    dt[node] = d
    return dt


def main():
    l = [int(e) for e in si().split()]
    n, u, v = l[0], l[1], l[2]
    graph = [[] for _ in range(n+1)]
    for _ in range(n-1):
        l = [int(e) for e in si().split()]
        graph[l[0]].append(l[1])
        graph[l[1]].append(l[0])

    udt = BFS(graph, u)
    vdt = BFS(graph, v)
    udt[u], vdt[v] = 0, 0

    vdmax = 0
    for i in range(1, n+1):
        if (vdt[i]-udt[i]) > 0 and vdt[i] > vdmax:
            vdmax = vdt[i]
    print(vdmax-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#ABC148-F Playing Tag on Tree
"""
与えられるグラフは木構造
青木くん(追いかける方)がいる頂点を根とすると、この問題は解きやすくなる。
そうした場合、高橋くんが追いつかれずに行ける頂点の中で、最も深さが深い葉に行くのが最適。
そのような頂点は頂点u,vからの距離によって求めることができ、結果的に高橋くんが行ける最深部の葉から
根までの距離が答えとなる。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n,u,v = map(int,readline().split())
u,v = u-1,v-1 #u:高橋くん初期位置,v:青木くん初期位置

g = [[] for _ in range(n+1)] #隣接リスト
for i in range(n-1):
    a,b = map(int,readline().split())
    a,b = a-1,b-1
    g[a].append(b)
    g[b].append(a)

#根からの距離を記録
#rank:rootからの距離
root = v
rank = [0]*n
new = [root] #深さを揃えて探索する必要があるのでstackとは若干異なる
c = 1
while len(new):
    tank = []
    for e in new:
        for go in g[e]:
            if go != root and rank[go] == 0:
                rank[go] = c
                tank.append(go)
    c += 1
    new = tank

#まず、高橋くんが最大でどの頂点まで戻れるのかを求める
now = u
res = rank[u]-(rank[u]-1)//2 #制限は(u-g間の距離-1)//2
ans = (rank[u]-1)//2 #戻れる最大の回数をansに入れる
while True:
    for e in g[now]:
        if rank[e] < rank[now]:
            if rank[e] < res: #制限より大きいならそこには行けない
                break
            else:
                now = e #nowに戻れる最大の頂点を格納
        else:
            continue
    if rank[e] < res: #制限より大きいならそこには行けない
        break

#ans + nowからの最大の深さが答え。
new = [now]
while new:
    tank = []
    for e in new:
        for go in g[e]:
            if rank[go] > rank[e]: #深さが増すなら
                tank.append(go)
    ans += 1
    new = tank

print(ans-1 if rank[u]%2==1 else ans)

Submission status: Accepted

Solution code:
from collections import deque
n,u,v=map(int,input().split())
u=u-1
v=v-1
G=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  G[a].append(b)
  G[b].append(a)
P=[0]*n #親のノード
P[v]=-1
F=[0]*n
D=deque([v])
V=[0]*n
V[v]=1
GG=[[] for i in range(n)]
while len(D)>0:
  x=D[0]
  D.popleft()
  for i in range(len(G[x])):
    if V[G[x][i]]==0:
      V[G[x][i]]=1
      D.append(G[x][i])
      P[G[x][i]]=x
      GG[x].append(G[x][i])
      F[G[x][i]]=F[x]+1
a=F[u]
ans1=(a-1)//2 #高橋君が上る回数
b=F[u]%2
if b==0:
  b=2 #上り切った後の差(1or2)
for i in range(ans1):
  u=P[u]
V=[0]*n
V[u]=1
V[P[u]]=1
F=[0]*n
D=deque([u])
while len(D)>0:
  x=D[0]
  D.popleft()
  for i in range(len(GG[x])):
    D.append(GG[x][i])
    F[GG[x][i]]=F[x]+1
ans2=max(F)
print(ans1+ans2+b//2)

Submission status: Accepted

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

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    n, u, v = mi()
    u -= 1
    v -= 1
    adj = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = mi_0()
        adj[a].append(b)
        adj[b].append(a)
    dist = [[None, None] for _ in range(n)]
    def dfs(current, key, previous=-1, depth=0):
        dist[current][key] = depth
        for v in adj[current]:
            if v != previous:
                dfs(v, key, current, depth+1)
    dfs(current=u, key=0, previous=-1, depth=0)
    dfs(current=v, key=1, previous=-1, depth=0)
    ans = -1
    for i in range(n):
        if dist[i][0] < dist[i][1]:
            ans = max(ans, dist[i][1] - 1)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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


def dfs(s):
    d = [-1] * n
    d[s] = 0
    stack = [s]
    while stack:
        frm = stack.pop()
        for to in adj[frm]:
            if d[to] == -1:
                d[to] = d[frm] + 1
                stack.append(to)

    return d


du = dfs(u)
dv = dfs(v)

ans = 0
for eu, ev in zip(du, dv):
    if eu < ev:
        ans = max(ans, ev - 1)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque


def bfs(s):
    d = [-1] * n
    p = [-1] * n
    dq = deque([s])
    d[s] = 0

    while dq:
        u = dq.popleft()
        for v in adj[u]:
            if d[v] == -1:
                d[v] = d[u] + 1
                p[v] = u
                dq.append(v)

    return d, p


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

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

depth, par = bfs(takahashi)
aoki_move = depth[aoki] // 2 + 1
root = aoki
for _ in range(aoki_move):
    child = root
    root = par[root]

adj[child].remove(root)
adj[root].remove(child)

depth2, par2 = bfs(root)

aoki_move += max(depth2) - 1
print(aoki_move)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)
N,u,v=map(int,input().split())

du,dv=[0]*-~N,[0]*-~N
T=[list() for i in range(-~N)]

def dfs(p,t,v,d):
  d[v]=t
  for i in T[v]:
    if i!=p:
      dfs(v,t+1,i,d)

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

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

c=0
for i in range(1,-~N):
  if len(T[i])==1 and i!=v:
    if du[i]<dv[i]:
      c=max(c,~-dv[i])

print(c)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(s):
    que = deque([(s, 0)])
    dist = [None]*n
    while que:
        cur, cst = que.popleft()
        if dist[cur] != None:
            continue
        dist[cur] = cst
        for nxt in es[cur]:
            que.append((nxt, cst+1))
    return dist

n,u,v = map(int,input().split())
es = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    es[a-1].append(b-1)
    es[b-1].append(a-1)
dist_u = bfs(u-1)
dist_v = bfs(v-1)
ans = 0

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

Submission status: Accepted

Solution code:
import sys
from collections import deque, defaultdict
def input(): return sys.stdin.readline().strip()

def main():
    N, u, v = map(int, input().split())
    u -= 1
    v -= 1
    
    edges = [map(int, input().split()) for _ in range(N-1)]

    to = [[] for _ in range(N)]
    for a, b in edges:
        a -= 1
        b -= 1
        to[a].append(b)
        to[b].append(a)
    
    dist  = {key:defaultdict(int) for key in [u, v]}

    def bfs(key):
        q = deque()
        q.append(key)
        while(len(q)):
            now = q.popleft()
            for nv in to[now]:
                if nv == key or dist[key][nv]:
                    continue
                else:
                    dist[key][nv] = dist[key][now] + 1
                    q.append(nv)
    
    for key in [u, v]:
        bfs(key)
    
    ans = 0
    for i in range(N):
        diff = dist[v][i] - dist[u][i]
        if diff > 0:
            ans = max(ans, dist[v][i]-1)

    print(ans)    

if __name__ == "__main__":
    main()

Submission status: Accepted

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


def get_dist(s, d, N):
    dist = [-1]*(N+1)
    dist[s] = 0
    q = [s]
    while q:
        a = q.pop()
        for b in d[a]:
            if dist[b]!=-1:
                continue
            dist[b] = dist[a] + 1
            q.append(b)
    return dist


def solve():
    N, u, v = map(int, input().split())
    d = defaultdict(list)
    for _ in range(N-1):
        A, B = map(int, input().split())
        d[A].append(B)
        d[B].append(A)
    du, dv = get_dist(u, d, N), get_dist(v, d, N)
    ds = [(i, j) for i, j in zip(du, dv) if i<j]
    ds.sort(key=lambda x:-x[1])
    print(ds[0][1]-1)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
N, u, v = map(int, input().split())
d = defaultdict(list)
for _ in range(N-1):
    A, B = map(int, input().split())
    d[A].append(B)
    d[B].append(A)

def get_dist(s):
    dist = [-1]*(N+1)
    dist[s] = 0

    q = [s]
    while q:
        a = q.pop()
        for b in d[a]:
            if dist[b]!=-1:
                continue
            dist[b] = dist[a] + 1
            q.append(b)
    return dist

du, dv = get_dist(u), get_dist(v)
ds = [(i,j[0], j[1]) for i,j in enumerate(zip(du, dv)) if j[0]<j[1]]
ds.sort(key=lambda x:-x[2])
a, b, c = ds[0]
print(c-1)

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)

u -= 1; v -= 1

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

takahashi, _ = bfs(u)
aoki, prev = bfs(v)

node = 0
dist = -1
for i,(t,a) in enumerate(zip(takahashi, aoki)):
    if t < a and a > dist:
        dist = a
        node = i

print(aoki[prev[node]])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)

N, u, v = 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)
#print(tree)

def calc_dist(dlist, n, dist, nnode):
  for c in tree[n]:
    if c == nnode:
      continue
    dlist[c] = dist
    calc_dist(dlist, c, dist+1, n)
    
u_dist_list = [0] * N
calc_dist(u_dist_list, u-1, 1, -1)
#print(u_dist_list)

v_dist_list = [0] * N
calc_dist(v_dist_list, v-1, 1, -1)
#print(v_dist_list)

ans = 0
for i in range(N):
  if (v_dist_list[i] - u_dist_list[i]) > 0 and v_dist_list[i] > ans:
    ans = v_dist_list[i] - 1
    
print(ans)

Submission status: Accepted

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

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

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

def bfs(graph, root):
    depth = [None] * (n+1)
    depth[0] = (-1,None)

    d = deque()
    d.append((root,0))
    max_dep = 0
    while(d):
        child,parent = d.popleft()
        depth[child] = (depth[parent][0] + 1, parent)
        if( max_dep < depth[child][0] ):
            max_dep = depth[child][0]
        for i in graph[child]:
            if i != parent:
                d.append( (i,child) )

    return depth,max_dep

depth_v,_ = bfs(graph, v)
now = list(depth_v[u])
u_depth = now[0]
limit = (u_depth+2)//2
while(now[0] > limit):
    u = now[1]
    now = depth_v[ u ]

if(len(graph[u]) == 1):
    print( depth_v[u][0]//2 )
    exit()

graph[u].discard( now[1] )
depth_new,max_dep = bfs(graph, u)
ans = limit + max_dep - 1
print(ans)

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,u,v = mi()
data = [[] for _ in range(n)]
for i in range(n-1):
    a,b = mi()
    a -= 1
    b -= 1
    data[a].append(b)
    data[b].append(a)
inf = -1
oni = [inf]*n
ko = [inf]*n

from collections import deque

def start(hazime,alis):
    d = deque()
    d.append((hazime-1,0))
    alis[hazime-1] = 0
    while d:
        ima,num = d.popleft()
        num += 1
        for i in data[ima]:
            if alis[i] != inf:
                continue
            alis[i] = num 
            d.append((i,num))
start(u,ko)
start(v,oni)

if len(data[u]) == 1 and data[u] == v:
    print(0) 
    exit()
ans = -1
for i in range(n):
    if ko[i] <= oni[i]:
        ans = max(ans,oni[i]-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
sys.setrecursionlimit(10 ** 7)

from collections import deque

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


def dfs(v):
    dist = [-1] * (n + 1)
    stack = deque([v])
    dist[v] = 0
    while stack:
        v = stack.popleft()
        memo = dist[v] + 1
        for w in graph[v]:
            if dist[w] >= 0:
                continue
            dist[w] = memo
            stack.append(w)
    return dist


U, V = dfs(u), dfs(v)
ans = 0
for x, y in zip(U[1:], V[1:]):
    if x < y:
        ans = max(ans, y - 1)
print(ans)