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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2000000)
n,u,v=map(int,input().split())
u=u-1
v=v-1
root=[[] for i in range(n)]

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

dp=[[-1]*n for i in range(2)]
dp[0][u]=0
dp[1][v]=0
def dfs(node,depth,par,flag):
    for vertex in root[node]:
        if vertex == par or dp[flag][vertex]!=-1:
            continue
        dp[flag][vertex]=depth+1
        dfs(vertex,depth+1,node,flag)
dfs(u,0,u,0)
dfs(v,0,v,1)
buf=-1
buf1=0
#print(dp1,dp2,root)
for i in range(n):
    if dp[0][i]<dp[1][i] and dp[1][i]>buf:
        buf=dp[1][i]
        buf1=dp[0][i]
print(buf-1)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

n, u, v = map(int, input().split())
g = [[] for _ 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)


ftakahasi = [-1 for i in range(n)]
faoki = [-1 for i in range(n)]


def dfst(i, n):
    ftakahasi[i] = n
    for sg in g[i]:
        if ftakahasi[sg] == -1:
            dfst(sg, n + 1)


def dfsa(i, n):
    faoki[i] = n
    for sg in g[i]:
        if faoki[sg] == -1:
            dfsa(sg, n + 1)


dfst(u - 1, 0)
dfsa(v - 1, 0)
res1 = 0
for i in range(n):
    pt = ftakahasi[i]
    pa = faoki[i]
    if pt < pa:
        tres = pa - 1
        res1 = max(res1, tres)
print(res1)

Submission status: Time Limit Exceeded

Solution code:

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())


N,T,A = inpl()
T -= 1
A -= 1
lines = defaultdict(set)
for _ in range(N-1):
    a,b = inpl()
    lines[a-1].add(b-1)
    lines[b-1].add(a-1)

def dfs(s,b,d):
    global aoki_nodes
    aoki_nodes[d].add(s)
    for t in lines[s]:
        if t !=b:
            dfs(t,s,d+1)
    return

aoki_nodes = [set() for _ in range(N)]
dfs(A,-1,0)


turn = 0
takahashi = [set() for _ in range(N)]
takahashi[0].add(T)
while True:
    nexts = set()
    for s in takahashi[turn]:
        if s in aoki_nodes[turn]:
            continue
        for t in lines[s]:
            if t not in aoki_nodes[turn]:
                takahashi[turn+1].add(t)
    if len(takahashi[turn+1]) == 0:
        print(turn)
        break
    turn += 1
    assert turn<N+5, "error"

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2000000)
n,u,v=map(int,input().split())
u=u-1
v=v-1
root=[[] for i in range(n)]

for i in range(n-1):
    a,b=map(int,input().split())
    root[a-1].append(b-1)
    root[b-1].append(a-1)
dp1=[-1]*n
dp1[u]=0
dp2=[-1]*n
dp2[v]=0

def dfs(node,depth,par,dp):
    for vertex in root[node]:
        if vertex == par or dp[vertex]!=-1:
            continue
        dp[vertex]=depth+1
        dfs(vertex,depth+1,node,dp)
dfs(u,0,u,dp1)
dfs(v,0,v,dp2)
buf=-1
buf1=0
#print(dp1,dp2,root)
for i in range(n):
    if dp1[i]<dp2[i] and dp2[i]>buf:
        buf=dp2[i]
        buf1=dp1[i]
print(buf-1)

Submission status: Time Limit Exceeded

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

def main():
    n, u, v = map(int, input().split())
    u, v = u-1, v-1
    G = [[] for i 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)

    N = n
    # Euler Tour Technique
    S = []
    FS = [0]*N
    depth = [0]*N
    is_leaf = [0]*N
    def dfs(v, p, d):
        depth[v] = d
        FS[v] = len(S)
        S.append(v)
        f = True
        for w in G[v]:
            if w == p:
                continue
            dfs(w, v, d+1)
            S.append(v)
            f = False
        if f:
            is_leaf[v] = 1

    dfs(v, -1, 0)

    # Sparse Table
    L = len(S)
    lg = [0]*(L + 1)
    for i in range(2, L+1):
        lg[i] = lg[i >> 1] + 1
    st = [None]*(lg[L] + 1)
    st0 = st[0] = S
    b = 1
    for i in range(lg[L]):
        st0 = st[i+1] = [p if depth[p] <= depth[q] else q for p, q in zip(st0, st0[b:])]
        b <<= 1

    # LCA O(1)
    def LCA(u, v):
        x = FS[u]; y = FS[v]
        if x > y:
            x, y = y, x
        l = lg[y - x + 1]
        px = st[l][x]; py = st[l][y - (1 << l) + 1]
        return px if depth[px] <= depth[py] else py

    def dist(u, v):
        return abs(depth[u]-depth[v])

    ans = 0
    for i in range(n):
        if not is_leaf[i]:
            continue
        lca = LCA(u, i)
        if lca == v:
            continue
        if dist(lca, u) >= dist(lca, v):
            continue
        tmp = 0
        d = dist(u, lca) + dist(lca, i)
        if d != 0:
            tmp = 2*d
            aoki = d
        else:
            aoki = 0
        tak = depth[i]
        m = tak-aoki
        if m%2==1:
            tmp += 2*m -1
        else:
            tmp += 2*(m-1)
        ans = max(ans, tmp)
    print(ans//2)

main()

Submission status: Time Limit Exceeded

Solution code:

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())


N,T,A = inpl()
T -= 1
A -= 1
lines = defaultdict(set)
for _ in range(N-1):
    a,b = inpl()
    lines[a-1].add(b-1)
    lines[b-1].add(a-1)

def dfs(s,b,d):
    global depthes
    depthes[s] = d
    for t in lines[s]:
        if t !=b:
            dfs(t,s,d+1)
    return

depthes = [-1]*N
dfs(A,-1,0)

aoki_nodes = [set() for _ in range(N)]
for i,d in enumerate(depthes):
    aoki_nodes[d].add(i)


turn = 0
nexts = set([T])
while True:
    takahashi = nexts.copy()
    nexts = set()

    for s in takahashi:
        if s in aoki_nodes[turn]:
            continue

        for t in lines[s]:
            if t not in aoki_nodes[turn]:
                nexts.add(t)

    if len(nexts) == 0:
        print(turn)
        break

    turn += 1

    assert turn<N+5, "error"

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2000000)
n,u,v=map(int,input().split())
u=u-1
v=v-1
edge=[]
for i in range(n-1):
    a,b=map(int,input().split())
    edge.append((a-1,b-1))
dp1=[-1]*n
dp1[u]=0
dp2=[-1]*n
dp2[v]=0

root=[[] for i in range(n)]
for a,b in edge:
    root[a].append(b)
    root[b].append(a)

def dfs(node,depth,par,dp):
    for vertex in root[node]:
        if vertex == par:
            continue
        dp[vertex]=depth+1
        dfs(vertex,depth+1,node,dp)
dfs(u,0,u,dp1)
dfs(v,0,v,dp2)
buf=-1
buf1=0
#print(dp1,dp2,root)
for i in range(n):
    if dp1[i]<dp2[i] and dp2[i]>buf:
        buf=dp2[i]
        buf1=dp1[i]
print(buf-1)

Submission status: Time Limit Exceeded

Solution code:
n,u,v=map(int,input().split())
u-=1
v-=1
d=[[]for _ in range(n)]
inf=float('inf')
aoki=[inf]*n
for i in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  d[a].append(b)
  d[b].append(a)
Q=d[v]
aoki[v]=0
dis=1
visited={v}
while Q:
  P=[]
  for i in Q:
    visited.add(i)
    for j in d[i]:
      if j not in visited:P.append(j)
    aoki[i]=dis
  dis+=1
  Q=P
chokudai=[-1]*n
chokudai[u]=0
dis=1
cant=set()
Q=d[u]
while Q:
  P=[]
  visited=set()
  for i in Q:
    if i in cant:
      continue
    if dis>=aoki[i]:
      if dis==aoki[i]:chokudai[i]=dis
      cant.add(i)
      continue
    else:
      chokudai[i]=dis
    for j in d[i]:
      if j not in visited:
        P.append(j)
        visited.add(j)
  dis+=1
  Q=P
#ans=0
#for i in range(n):
#  if chokudai[i]!=-1:ans=max(ans,chokudai[i])
#print(ans)
print(max(chokudai))

Submission status: Time Limit Exceeded

Solution code:

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())


N,T,A = inpl()
T -= 1
A -= 1
lines = defaultdict(set)
for _ in range(N-1):
    a,b = inpl()
    lines[a-1].add(b-1)
    lines[b-1].add(a-1)

def dfs(s,b,d):
    global depthes
    depthes[s] = d
    for t in lines[s]:
        if t !=b:
            dfs(t,s,d+1)
    return

depthes = [-1]*N
dfs(A,-1,0)

aoki_nodes = [set() for _ in range(N)]
for i,d in enumerate(depthes):
    aoki_nodes[d].add(i)


turn = 0
nexts = set([T])
while True:
    takahashi = nexts.copy()
    nexts = set()

    # print(takahashi,aoki_nodes[turn])

    for s in takahashi:
        if s in aoki_nodes[turn]:
            continue

        for t in lines[s]:
            if t not in aoki_nodes[turn]:
                nexts.add(t)

    if len(nexts) == 0:
        print(turn)
        break

    turn += 1

Submission status: Time Limit Exceeded

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

class LCA1():
    def __init__(self, l, start):
        self.n = len(l)
        self.dep=[0]*self.n
        self.par=[[-1]*self.n for i in range(18)]
        self.is_leaf = [0]*self.n

        def dfs(p,v,d):
            self.dep[v]=d
            self.par[0][v]=p
            f = True
            for w in l[v]:
                if w!=p:
                    dfs(v,w,d+1)
                    f = False
            if f:
                self.is_leaf[v] = 1
        dfs(-1,start,0)
        for i in range(17):
            for j in range(self.n):
                self.par[i+1][j]=self.par[i][self.par[i][j]]

    def lca(self,a,b):
        if self.dep[a]>self.dep[b]:
            a,b=b,a
        for i in range(18):
            if (self.dep[b]-self.dep[a]) & 1<<i:
                b=self.par[i][b]
        if a==b:
            return a
        for i in range(18)[::-1]:
            if self.par[i][a]!=self.par[i][b]:
                a=self.par[i][a]
                b=self.par[i][b]
        return self.par[0][a]

    def dist(self, a,b):
        return abs(self.dep[a]-self.dep[b])

def main():
    n, u, v = map(int, input().split())
    u, v = u-1, v-1
    G = [[] for i 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)

    LCA = LCA1(G, v)
    ans = 0
    for i in range(n):
        if not LCA.is_leaf[i]:
            continue
        lca = LCA.lca(u, i)
        if lca == v:
            continue
        if LCA.dist(lca, u) >= LCA.dist(lca, v):
            continue
        tmp = 0
        d = LCA.dist(u, lca) + LCA.dist(lca, i)
        if d != 0:
            tmp = 2*d
            aoki = d
        else:
            aoki = 0
        tak = LCA.dep[i]
        m = tak-aoki
        if m%2==1:
            tmp += 2*m -1
        else:
            tmp += 2*(m-1)
        ans = max(ans, tmp)
    print(ans//2)

main()

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, V, U = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]

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

# 深い方に逃げるべき
# 子どものうち一番深い場所の深さ
children_depths = [-1 for _ in range(N)]
parents = [None for _ in range(N)]


def dfs(v, parent):
    ret = 0
    for u in graph[v]:
        if u == parent:
            continue
        ret = max(ret, dfs(u, v) + 1)
    children_depths[v] = ret
    parents[v] = parent
    return ret


dfs(U, None)

v = V
dist = 1
while parents[v] != U:
    v = parents[v]
    dist += 1

# 何回親側に上がるか
p_cnt = 0
v = V
ans = 0
while dist > 0:
    ans = max(ans, dist - 1 + children_depths[v] + p_cnt)
    v = parents[v]
    p_cnt += 1
    dist -= 2
print(ans)

Submission status: Time Limit Exceeded

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

class LCA1():
    def __init__(self, l, start):
        self.n = len(l)
        self.dep=[0]*self.n
        self.par=[[-1]*self.n for i in range(18)]
        self.is_leaf = [0]*n

        def dfs(p,v,d):
            self.dep[v]=d
            self.par[0][v]=p
            f = True
            for w in l[v]:
                if w!=p:
                    dfs(v,w,d+1)
                    f = False
            if f:
                self.is_leaf[v] = 1
        dfs(-1,start,0)
        for i in range(17):
            for j in range(self.n):
                self.par[i+1][j]=self.par[i][self.par[i][j]]

    def lca(self,a,b):
        if self.dep[a]>self.dep[b]:
            a,b=b,a
        for i in range(18):
            if (self.dep[b]-self.dep[a]) & 1<<i:
                b=self.par[i][b]
        if a==b:
            return a
        for i in range(18)[::-1]:
            if self.par[i][a]!=self.par[i][b]:
                a=self.par[i][a]
                b=self.par[i][b]
        return self.par[0][a]

    def dist(self, a,b):
        return abs(self.dep[a]-self.dep[b])

n, u, v = map(int, input().split())
u, v = u-1, v-1
G = [[] for i 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)

LCA = LCA1(G, v)
ans = 0
for i in range(n):
    if not LCA.is_leaf[i]:
        continue
    lca = LCA.lca(u, i)
    if lca == v:
        continue
    if LCA.dist(lca, u) >= LCA.dist(lca, v):
        continue
    turn = 0
    tmp = 0
    d = LCA.dist(u, lca) + LCA.dist(lca, i)
    if d != 0:
        tmp = 2*d
        aoki = d
    else:
        aoki = 0
    tak = LCA.dep[i]
    m = tak-aoki
    if m%2==1:
        tmp += 2*m -1
    else:
        tmp += 2*(m-1)
    ans = max(ans, tmp)
print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
N, u, v = map(int, input().split())
G = [[] for _ 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)
v-=1
u-=1
que = [v]
par = [-1]*N
depth = [-1]*N
depth[v] = 0
while que:
    i = que.pop()
    d = depth[i]
    for nv in G[i]:
        if depth[nv]>=0:
            continue
        depth[nv] = d+1
        par[nv] = i
        que.append(nv)
d = depth[u]
now = u
m = 0
que = [now]
while que:
    i = que.pop()
    m = max(m, depth[i])
    for nv in G[i]:
        if depth[nv]<depth[i]:
            continue
        que.append(nv)
for i in range(d//2):
    now = par[now]
    que = [now]
    while que:
        i = que.pop()
        m = max(m, depth[i])
        for nv in G[i]:
            if depth[nv]<depth[i]:
                continue
            que.append(nv)
print(m-1)

Submission status: Accepted

Solution code:
from collections import deque
 
N,u,v=map(int,input().split())
G=[[] for _ 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)
 
def bfs(s):
    seen = [0]*N
    d = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    while len(todo):
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
    return d
  
d1 = bfs(u-1)
d2 = bfs(v-1)
 
print(max([d2[i] for i in range(N) if d1[i]<=d2[i]])-1)

Submission status: Accepted

Solution code:
"""
高橋君はとりあえず、青木君から最も遠い木の端を目指すのがベスト。
また、目指すべき木の端までの距離に関しては、高橋くんよりも自分の方が近くなくてはならない。
また、高橋君が捕まるときは、必ず木の端の一歩手前のノードになる。
つまり、青木君が移動しなくてはいけない最大距離は、高橋君が目指す木の端までの距離-1、ということになる。
とりま、高橋くん、青木君の初期位置から各ノードまでの距離を調べて、上記の条件にマッチする端を見つける。
"""
from collections import deque
N,u,v = map(int,input().split())
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
    a,b = map(int,input().split())
    edges[a].append(b)
    edges[b].append(a)

takahashi = [None]*(N+1)
que = deque([(0,u,0)])
while que:
    step,cur,par = que.popleft()
    takahashi[cur] = step
    for nx in edges[cur]:
        if nx == par:
            continue
        que.append((step+1,nx,cur))

aoki = [None]*(N+1)
que = deque([(0,v,0)])
while que:
    step,cur,par = que.popleft()
    aoki[cur] = step
    for nx in edges[cur]:
        if nx == par:
            continue
        que.append((step+1,nx,cur))
ans = 0
for i in range(1,N+1):
    if takahashi[i] < aoki[i]:
        ans = max(ans,aoki[i]-1)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
I=lambda:int(input())
MI=lambda:map(int,input().split())
LI=lambda:list(map(int,input().split()))
from collections import deque

res=0
INF=10**9


N,u,v=MI()
G=[[] for _ in [0]*(N+1)]
for i in range(N-1):
    a,b=MI()
    G[a].append(b)
    G[b].append(a)


def bfs(a):
    q=deque()
    q.append(a)
    d=[INF]*(N+1)
    d[a]=0
    res=0
    while q:
        r=q.popleft()
        for nr in G[r]:
            if d[nr]==INF:
                q.append(nr)
                d[nr]=d[r]+1
                res+=1
    return d

aoki=bfs(v)
taka=bfs(u)

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

N, u, v = map(int, input().split())
G = defaultdict(lambda: [])

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


if G[u] == [v]:
    print(0)
    exit()


def bfs(v):
    seen = [0]*(N+1)
    queue = deque()
    dist = [-1]*(N+1)
    dist[v] = 0
    seen[v] = 1
    queue.append(v)
    while queue:
        q = queue.popleft()
        for nx in G[q]:
            if seen[nx]:
                continue
            dist[nx] = dist[q] + 1
            seen[nx] = 1
            queue.append(nx)
    return dist

d_u = bfs(u)
d_v = bfs(v)
ans = 0
for node in range(1, N+1):
    if d_u[node] < d_v[node] and len(G[node]) == 1:
        ans = max(ans, d_v[node]-1)
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    n, u, v = map(int,input().split())
    if u == v:
        print(0)
        sys.exit()

    graph = [[] for _ in range(n)]
    depth_u = [-1] * (n) #頂点iのuから見た深さ
    depth_v = [-1] * (n) #頂点iのvから見た深さ
    u -= 1 #高橋
    v -= 1 #青木
    for i in range(n-1):
        a, b = map(int,input().split())
        graph[a - 1].append(b - 1)
        graph[b - 1].append(a - 1)
    
    # bfsで高橋から見た各頂点の深さをメモる。
    queue = deque([u])
    visited = [False]*n
    visited[u] = True
    depth_u[u] = 0
    while queue:
        node = queue.popleft()
        for xnode in graph[node]:
            if not visited[xnode]:
                visited[xnode] = True
                depth_u[xnode] = depth_u[node] + 1
                queue.append(xnode)
    # bfsで青木から見た各頂点の深さをメモる。
    queue = deque([v])
    visited = [False]*n
    visited[v] = True
    depth_v[v] = 0
    while queue:
        node = queue.popleft()
        for xnode in graph[node]:
            if not visited[xnode]:
                visited[xnode] = True
                depth_v[xnode] = depth_v[node] + 1
                queue.append(xnode)
    ans = 0
    max_d_v = 0
    for i in range(n):
        if depth_u[i] < depth_v[i]:
            max_d_v = max(max_d_v, depth_v[i])
    print(max_d_v - 1)



if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n,u,v=map(int,input().split())
ki=[[] for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  ki[a].append(b)
  ki[b].append(a)
# 次数
dn=[len(ki[i]) for i in range(n)]
inf=float('inf')
dt=[inf]*n
da=[inf]*n
u,v=u-1,v-1
from collections import deque
todo=deque([u])
dt[u]=0
while todo:
  x=todo.popleft()
  for nx in ki[x]:
    if dt[nx]>dt[x]+1:
      dt[nx]=dt[x]+1
      todo.append(nx)
todo=deque([v])
da[v]=0
while todo:
  x=todo.popleft()
  for nx in ki[x]:
    if da[nx]>da[x]+1:
      da[nx]=da[x]+1
      todo.append(nx)
ans=0
for i in range(n):
  if dn[i]>1 and dt[i]<=da[i]:ans=max(ans,da[i])
print(ans)
exit()
print(dn)
print(dt)
print(da)

Submission status: Accepted

Solution code:
from collections import deque
n, u, v = map(int, input().split())
u -= 1
v -= 1
edges = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
def bfs(u):
    visited = [-1] * n
    Q = deque()
    visited[u] = 0
    Q.append(u)
    while Q:
        p = Q.popleft()
        for v in edges[p]:
            if visited[v] == -1:
                visited[v] = visited[p] + 1
                Q.append(v)
    return visited
tak_dist = bfs(u)
aok_dist = bfs(v)
ans = []
for i in range(n):
    if tak_dist[i] < aok_dist[i]:
        ans.append(aok_dist[i])
print(max(ans) - 1)

Submission status: Accepted

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

ABs = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]

#%%
roots = [[] for _ in range(N)]

for AB in ABs:
    roots[AB[0]].append(AB[1])
    roots[AB[1]].append(AB[0])

#BFS
def BFS(roots, start):
    from collections import deque
    seen = [-1 for _ in range(N)]
    seen[start] = 0
    todo = deque([start])
    while len(todo) > 0:
        checking = todo.pop()
        for root in roots[checking]:
            if seen[root] == -1:
                seen[root] = seen[checking] +1
                todo.append(root)
    return seen

from_u = BFS(roots, u)
from_v = BFS(roots, v)

from collections import deque
todo = deque([u])
max_distance = from_v[u]
position = u
seen = [False for _ in range(N)]
seen[u] = True
while len(todo) > 0:
    checking = todo.pop()
    for root in roots[checking]:
        if from_u[root] < from_v[root] and seen[root] == False:
            seen[root] = True
            todo.append(root)

            if max_distance < from_v[root]:
                max_distance = from_v[root]
                position = root
            
print(max_distance-1)

Submission status: Accepted

Solution code:
from collections import deque

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

distA = {}
que = deque([(u,0)])
while que:
    n,step = que.popleft()
    if n not in distA:
        distA[n] = step
        for nx in edges[n]:
            que.append((nx,step+1))

distB = {}
que = deque([(v,0)])
while que:
    n,step = que.popleft()
    if n not in distB:
        distB[n] = step
        for nx in edges[n]:
            que.append((nx,step+1))
ans = 0
for i in range(1,N+1):
    dist = distB[i]-distA[i]
    if dist > 0:
        ans = max(ans,distB[i]-1)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque


def main():
    N, p, q, *AB = map(int, sys.stdin.buffer.read().split())
    p -= 1
    q -= 1

    G = [[] for _ in range(N)]
    for a, b in zip(*[iter(AB)] * 2):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

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

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

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

    max_d = 0
    for d1, d2 in zip(dist1, dist2):
        if d1 < d2 and max_d < d2:
            max_d = d2

    print(max_d - 1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

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


def main():
    N, p, q, *AB = map(int, read().split())
    p -= 1
    q -= 1

    G = [[] for _ in range(N)]
    for a, b in zip(*[iter(AB)] * 2):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

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

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

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

    max_d = 0
    for d1, d2 in zip(dist1, dist2):
        if d1 < d2 and max_d < d2:
            max_d = d2

    print(max_d - 1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

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


def main():
    N, ta, ao, *AB = map(int, read().split())
    ta -= 1
    ao -= 1

    G = [[] for _ in range(N)]
    for a, b in zip(*[iter(AB)] * 2):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    dist_ta = [-1] * N
    dist_ta[ta] = 0
    queue = deque([ta])
    while queue:
        v = queue.popleft()
        for nv in G[v]:
            if dist_ta[nv] == -1:
                dist_ta[nv] = dist_ta[v] + 1
                queue.append(nv)

    dist_ao = [-1] * N
    dist_ao[ao] = 0
    queue = deque([ao])
    while queue:
        v = queue.popleft()
        for nv in G[v]:
            if dist_ao[nv] == -1:
                dist_ao[nv] = dist_ao[v] + 1
                queue.append(nv)

    d_ao = 0
    for d1, d2 in zip(dist_ta, dist_ao):
        if d1 < d2 and d_ao < d2:
            d_ao = d2

    if d_ao == 0:
        if dist_ta[ao] == 1:
            print(0)
        else:
            print(1)

    print(d_ao - 1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, U, V, AB):
    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)
        g[b].append(a)

    def dfs(u):
        s = [u]
        d = {u: 0}
        while s:
            u = s.pop()
            for v in g[u]:
                if v in d:
                    continue
                d[v] = d[u] + 1
                s.append(v)
        return d

    du = dfs(U)
    dv = dfs(V)

    ans = 0
    for v in sorted(du.keys()):
        if du[v] < dv[v]:
            ans = max(ans, dv[v] - 1)

    return ans


def main():
    N, U, V = read_int_n()
    AB = [read_int_n() for _ in range(N-1)]
    print(slv(N, U, V, AB))


if __name__ == '__main__':
    main()