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:
# -*- 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()

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)

    s = [U]
    prev = {}
    prev[U] = -1
    while s:
        u = s.pop()
        for v in g[u]:
            if v in prev:
                continue
            prev[v] = u
            s.append(v)

    p = [V]
    v = V
    while v != U:
        v = prev[v]
        p.append(v)
    p.reverse()
    nu = p[len(p)//2-1]
    ans = len(p)//2-1
    if len(p) % 2 == 1:
        ans += 1

    done = set(p[len(p)//2-1:])

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

    return ans + max(d.values())





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()

Submission status: Accepted

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, u, v = read_values()
    u -= 1
    v -= 1
    F = [set() for _ in range(N)]
    for _ in range(N - 1):
        a, b = read_index()
        F[a].add(b)
        F[b].add(a)

    D = [-1] * N
    S = deque()
    S.append((0, v))
    D[v] = 0
    while S:
        c, p = S.popleft()
        for q in F[p]:
            if D[q] != -1:
                continue
            D[q] = c + 1
            S.append((c + 1, q))

    E = [-1] * N
    S.append((0, u))
    E[u] = 0
    while S:
        c, p = S.popleft()
        for q in F[p]:
            if E[q] != -1  or D[q] < c + 1:
                continue
            E[q] = c + 1
            S.append((c + 1, q))
    
    res = 0
    for i in range(N):
        if E[i] < 0:
            continue
        res = max(res, D[i])
    print(res - 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

"""
最初から高橋くんが葉にいる&その隣接に青木くん，というパターン以外は
葉の1個手前で終わるかな，
ある点に対しての距離を見ればいい，ゴールがそこなら青木くんはそこに最短で行くので．
ある点が青木くんよりの場合，そこはゴールにならない
"""
def main():

    ##########################################
    import heapq
    class Dijkstra():
        """
        ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
        ・負のコストがない場合のみ
        ・計算量はO(E log|V|)　
        ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
        ・復元なし
        """

        #最短のpathをたす


        class Edge():
            #重み付き有向辺

            def __init__(self, _to, _cost):
                self.to =_to
                self.cost = _cost

        def __init__(self, V):
            #引数Vは頂点数
            self.inf=10**20
            self.G = [[] for _ in range(V)] #隣接リストG[u][i]が頂点uのi番目の辺
            self. _E = 0 #辺の数
            self._V = V #頂点数

        #proparty - 辺の数
        def E(self):
            return self._E

        #proparty - 頂点数
        def V(self):
            return self._V

        def add(self, _from, _to, _cost):
            #2頂点と辺のコストを追加
            self.G[_from].append(self.Edge(_to,_cost))
            self._E +=1

        def add2(self, _from, _to, _cost):
            #2頂点と辺のコスト（無向）を追加
            self.G[_from].append(self.Edge(_to, _cost))
            self.G[_to].append(self.Edge(_from, _cost))
            self._E +=2

        def shortest_path(self,s):#,g):
            #始点sから頂点iまでの最短経路長のリストを返す
            que = [] #priority queue
            d = [self.inf] * self.V()

            #prev = [None]*self.V() #prev[j]は，sからjへ最短経路で行くときのjの一つ前の場所
            #復元で使う

            d[s] = 0
            heapq.heappush(que,(0,s)) #始点の距離と頂点番号をヒープに追加

            while len(que)!=0:
                #キューに格納されてある中で一番コストが小さい頂点を取り出す
                cost,v = heapq.heappop(que)

                #キューに格納された最短経路長候補がdの距離よりも大きい場合に処理をスキップ
                if d[v] < cost:
                    continue

                #頂点vに隣接する各頂点iに対して，vを経由した場合の距離を計算して，これがd[i]よりも小さい場合に更新
                for i in range(len(self.G[v])):
                    e = self.G[v][i] #vのi個目の隣接辺
                    if d[e.to] > d[v] + e.cost:
                        d[e.to] = d[v] + e.cost #更新

                        #prev[e.to] = v
                        #復元で使う

                        heapq.heappush(que,(d[e.to],e.to)) #queに新たな最短経路長候補を追加

            """#sからgまでの最短経路
            path = []
            pos = g #今いる場所，ゴールで初期化
            for _ in range(self.V()+1):
                path.append(pos)
                if pos == s:
                    break
                #print("pos:",format(pos))
                pos = prev[pos]
            path.reverse()
            #print(path)"""

            return d#,path
    ########################
    mod=10**9+7
    N,u,v=MI()
    u-=1
    v-=1
    
    dim=[0]*N
    adj=[[]for _ in range(N)]
    
    djk=Dijkstra(N)
    for _ in range(N-1):
        a,b=MI()
        a-=1
        b-=1
        djk.add2(a,b,1)
        dim[a]+=1
        dim[b]+=1
        adj[a].append(b)
        adj[b].append(a)
        
    if dim[u]==1:
        if adj[u][0]==v:
            print(0)
            exit()
            
    L=[]
    for i in range(N):
        if dim[i]==1:
            L.append(adj[i][0])
        
    ans=0
    lt=djk.shortest_path(u)
    la=djk.shortest_path(v)
    
    for i in L:
        if lt[i]<=la[i]:
            ans=max(ans,la[i])
            
    print(ans)
            
            
    

main()

Submission status: Accepted

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

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

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

#u-v間の単純pathを用意する
path = []
def connected(v, tv, p=-1):
  if v == tv:
    return True
  for w in Tree[v]:
    if w == p:
      continue
    elif connected(w, tv, v):
      path.append(w)
      return True
  return False

connected(v, u)
path.append(v)

#u-v間の点からvとは逆方向にdfs
#u-vの中点から調べれば十分(中点よりvに寄ると、青木君は捕まってしまう)

def dfs(v, p):
  d = -1
  for w in Tree[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)

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:
"""
シミュレートしてみればわかるが、高橋君は青木君よりも自分の方が近いようなノードのうち、青木君から最も遠いノードに向かって逃げるのが最善手。
そのようなノードをXとおくと、青木君と高橋君が鉢合わせるノードはXの一つ手前のノードになる。
したがって、青木君が動かす手の数はXまでの手数-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)

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


aokiDist = [None]*(N+1)
que = deque([(v,0)])
while que:
    n,step = que.popleft()
    aokiDist[n] = step
    for nx in edges[n]:
        if aokiDist[nx] == None:
            que.append((nx,step+1))
ans = 0
for i in range(1,N+1):
    if aokiDist[i] > takahashiDist[i]:
        ans = max(ans,aokiDist[i]-1)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,u,v=map(int, input().split())
u-=1
v-=1
es=[[] for i in range(n)]
for i in range(n-1):
    a0,b0=map(int, input().split())
    es[a0-1].append(b0-1)
    es[b0-1].append(a0-1)
aoki=[-1]*n
aoki[v]=0
choku=[-1]*n
choku[u]=0
from collections import deque
que=deque([])
que.append(u)
while que:
    now=que.popleft()
    step=choku[now]
    for e in es[now]:
        if choku[e]==-1:
            choku[e]=step+1
            que.append(e)

que=deque([])
que.append(v)
while que:
    now=que.popleft()
    step=aoki[now]
    for e in es[now]:
        if aoki[e]==-1:
            aoki[e]=step+1
            que.append(e)

end=None
for i in range(n):
    if len(es[i])==1: 
        if choku[i]==0 and aoki[i]==1:
            print(0)
            exit()
        elif end==None and aoki[i]>choku[i]:
            end=(i, aoki[i])
        elif aoki[i]>choku[i] and end[1]<aoki[i]:
            end=(i, aoki[i])
print(end[1]-1)

Submission status: Accepted

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

d_from_u = [float('inf') for _ in range(N)]
d_from_v = [float('inf') for _ in range(N)]
d_from_u[u] = 0
d_from_v[v] = 0
#print(tonari)
now = [v] #追いかける方
d = 0
while now:
  d += 1
  nextvisit = []
  for n in now:
    for t in tonari[n]:
      if d_from_v[t] > d:
        d_from_v[t] = d
        nextvisit.append(t)
  now = nextvisit



now = [u] #逃げる方
d = 0
while now:
  d += 1
  nextvisit = []
  for n in now:
    for t in tonari[n]:
      if d_from_v[t] <= d: #追いかける方より遠い地点は排除
        continue
      elif d_from_u[t] > d:
        d_from_u[t] = d
        nextvisit.append(t)
  now = nextvisit


distance = []
ans = 0
for U, V in zip(d_from_u, d_from_v):
  if U < N+1: #infを排除
    ans = max(ans, V-1)
print(ans)

Submission status: Accepted

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

d_from_u = [float('inf') for _ in range(N)]
d_from_v = [float('inf') for _ in range(N)]
d_from_u[u] = 0
d_from_v[v] = 0
#print(tonari)
now = [v] #追いかける方
d = 0
while now:
  d += 1
  nextvisit = []
  for n in now:
    for t in tonari[n]:
      if d_from_v[t] > d:
        d_from_v[t] = d
        nextvisit.append(t)
  now = nextvisit



now = [u] #逃げる方
d = 0
while now:
  d += 1
  nextvisit = []
  for n in now:
    for t in tonari[n]:
      if d_from_v[t] <= d: #追いかける方より遠い地点は排除
        continue
      elif d_from_u[t] > d:
        d_from_u[t] = d
        nextvisit.append(t)
  now = nextvisit


distance = []
for U, V in zip(d_from_u, d_from_v):
  if U < N+1: #infを排除
    distance.append((U, V))

if distance:
  ans = max(distance, key= lambda x: x[1])[1] - 1
else:
  ans = 0
print(ans)

Submission status: Accepted

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

d_from_u = [float('inf') for _ in range(N)]
d_from_v = [float('inf') for _ in range(N)]
d_from_u[u] = 0
d_from_v[v] = 0
#print(tonari)

now = [u]
d = 0
while now:
  d += 1
  nextvisit = []
  for n in now:
    for t in tonari[n]:
      if d_from_u[t] > d:
        d_from_u[t] = d
        nextvisit.append(t)
  now = nextvisit

now = [v]
d = 0
while now:
  d += 1
  nextvisit = []
  for n in now:
    for t in tonari[n]:
      if d_from_v[t] > d:
        d_from_v[t] = d
        nextvisit.append(t)
  now = nextvisit

#print(d_from_u)
#print(d_from_v)

distance = []
for U, V in zip(d_from_u, d_from_v):
  distance.append((U, V))

distance.sort(key = lambda x: x[1])

#print(distance)
ans = 0
while distance:
  d = distance.pop()
  if d[0] < d[1]:
    ans = d[1] - 1
    break
print(ans)

Submission status: Accepted

Solution code:
import collections

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)
q=collections.deque()
q.append((v,0))
checked=[0]*(n+1)
dist1=[0]*(n+1)
while len(q)!=0:
  tv,td=q.popleft()
  checked[tv]=1
  dist1[tv]=td
  for tu in g[tv]:
    if checked[tu]==1:
      continue
    q.append((tu,td+1))
q=collections.deque()
q.append((u,0))
checked=[0]*(n+1)
dist2=[0]*(n+1)
while len(q)!=0:
  tv,td=q.popleft()
  checked[tv]=1
  dist2[tv]=td
  for tu in g[tv]:
    if checked[tu]==1:
      continue
    q.append((tu,td+1))
ans=0
for tv in range(1,n+1):
  if dist1[tv]>dist2[tv]:
    ans=max(ans,dist1[tv]-1)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,u,v = map(int,input().split())
branch = [list(map(int,input().split())) for _ in range(n-1)]
link = [[] for _ in range(n)]
for i in branch:
    link[i[0]-1].append(i[1]-1)
    link[i[1]-1].append(i[0]-1)

q_a = deque([u-1])
q_b = deque([v-1])
dist_a = [-1 for _ in range(n)]
dist_b = [-1 for _ in range(n)]
dist_a[u-1] = 0
dist_b[v-1] = 0
while q_a:
    check = q_a.popleft()
    for j in link[check]:
        if dist_a[j] == -1:
            dist_a[j] = dist_a[check]+1
            q_a.append(j)
while q_b:
    check = q_b.popleft()
    for m in link[check]:
        if dist_b[m] == -1:
            dist_b[m] = dist_b[check]+1
            q_b.append(m)

ans = 0
for k in range(n):
    compare = 0
    if dist_b[k]>dist_a[k]:
        compare = dist_b[k]-1

    if compare > ans:
        ans = compare

print(ans)

Submission status: Accepted

Solution code:
class LCA(object):
    def __init__(self, n, root, edges, decrement=True):
        """
        :param n: 頂点数
        :param root: 木の根
        :param edges: 辺のリスト
        :param decrement:

        :param self.depth: rootを根とした時の各頂点の深さ
        """
        self.n = n
        self.decrement = decrement
        self.root = root - self.decrement
        self.edges = [set() for _ in range(self.n)]
        for x, y in edges:
            self.add_edge(x,y)
        self.k_max = (self.n - 1).bit_length()
        self.depth = [-1 if i != self.root else 0 for i in range(self.n)]
        self.doubling = [[-1] * self.n for _ in range(self.k_max)]
        self.parent = [-1]*self.n
        self.dfs()
        for i in range(1, self.k_max):
            for k in range(self.n):
                if self.doubling[i - 1][k] != -1:
                    self.doubling[i][k] = self.doubling[i - 1][self.doubling[i - 1][k]]

    def add_edge(self, x, y):
        """
        後から追加した場合は update() をする
        """
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        self.edges[y].add(x)

    def update(self):
        self.depth = [-1 if i != self.root else 0 for i in range(self.n)]
        self.doubling = [[-1] * self.n for _ in range(self.k_max)]
        self.dfs()
        for i in range(1, self.k_max):
            for k in range(self.n):
                if self.doubling[i - 1][k] != -1:
                    self.doubling[i][k] = self.doubling[i - 1][self.doubling[i - 1][k]]


    def dfs(self):
        next_set = [self.root]
        while next_set:
            p = next_set.pop()
            for q in self.edges[p]:
                if self.depth[q] == -1:
                    self.depth[q] = self.depth[p] + 1
                    self.doubling[0][q] = p
                    next_set += [q]

    def get(self, u, v):
        """
        :return: u と v の最近共通祖先の頂点番号を返す
        """
        if self.decrement:
            u -= 1
            v -= 1
        if self.depth[v] < self.depth[u]:
            u, v = v, u

        for i in range(self.k_max):
            """ v を u の位置まで遡らせる """
            if (self.depth[v] - self.depth[u]) >> i & 1:
                v = self.doubling[i][v]
        if v == u:
            """ v の祖先が u だった場合"""
            return u + self.decrement

        for i in range(self.k_max-1, -1, -1):
            """ k = 2**(k_max-1), ..., 2**0 について、 
            「k個先を確認して共通祖先でないなら u1,v1 をk個先に移動」ということを繰り返す"""
            parent_u, parent_v = self.doubling[i][u], self.doubling[i][v]
            if parent_u != parent_v:
                u, v = parent_u, parent_v
        return self.doubling[0][u] + self.decrement

    def distance(self, u, v):
        """
        :return: u と v の最短距離を求める
        備考: 経路復元をしようとすると O(E)かかるので、経路復元が必要な場合は dfs を用いるとよい
        """
        lca_at = self.get(u,v)
        if self.decrement:
            u -= 1
            v -= 1
            lca_at -= 1
        return self.depth[u] + self.depth[v] - 2*self.depth[lca_at]

    def distance_list(self, start=1, save=False):
        """
        :param start: スタート地点
        :return: スタート地点から各点への距離のリスト
        """
        dist = [-1]*self.n
        if self.decrement:
            start -= 1
        if not save:
            self.parent = [-1] * self.n
        p, t = start, 0
        self.parent[p] = -2
        dist[p] = 0
        next_set = deque([(p, t)])

        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                if self.parent[q] != -1:
                    continue
                if q == xx-1:
                    continue
                dist[q] = t + 1
                self.parent[q] = p
                next_set.append((q, t + 1))
        return dist

    def most_distant_point(self, start=1, save=False):
        """
        計算量　O(N)
        :return: (start から最も遠い頂点, 距離)
        """
        if not save:
            self.parent = [-1] * self.n
        res = (start - self.decrement, 0)
        temp = 0
        for i, dist in enumerate(self.distance_list(start, save=save)):
            if dist > temp:
                temp = dist
                res = (i + self.decrement, dist)
        return res

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

N, u, v = map(int, input().split())
edges = []
for _ in range(N-1):
    x, y = map(int, input().split())
    edges.append((x,y))
xx = -3
lca = LCA(N, 1, edges, decrement=True)
p = lca.get(u,v)
lu, lv = lca.depth[u-1] - lca.depth[p-1], lca.depth[v-1] - lca.depth[p-1]
if lu <= lv:
    q, _ = lca.most_distant_point(v)
    print(lca.distance(q,v)-1)
    exit()
else:
    L = (lu+lv)//2
    cnt = 0
    lca.distance_list()
    if lca.depth[u-1] >= lca.depth[v-1]:
        a = u-1
        while cnt < L:
            a = lca.parent[a]
            cnt += 1
        xx, s = lca.parent[a]+1, a+1
    else:
        a = v-1
        while cnt < L+1:
            a = lca.parent[a]
            cnt += 1
        xx, s = a+1, lca.parent[a]+1
    q, _ = lca.most_distant_point(s)
    print(lca.distance(q,v)-1)
    exit()

Submission status: Accepted

Solution code:
from collections import deque
N, u, v = map(int, input().split())

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


def bfs(s):
    dist = [-1] * (N + 1)
    dist[s] = 0
    d = deque([s])
    while len(d) > 0:
        v = d.popleft()
        for w in G[v]:
            if dist[w] < 0:
                dist[w] = dist[v] + 1
                d.append(w)
    return dist


tkhs = bfs(u)
aok = bfs(v)
ans = 0
for i in range(1, N + 1):
    if tkhs[i] < aok[i]:
        ans = max(ans, aok[i] - 1)
print(ans)

Submission status: Accepted

Solution code:
from collections import*
n,u,v=map(int,input().split())
e=[[]for _ in range(n+1)]
INF=10**18
d=[INF]*(n+1)
for _ in range(n-1):
  a,b=map(int,input().split())
  e[a]+=[b]
  e[b]+=[a]
q=deque([(v,0)])
while q:
  now,c=q.popleft()
  d[now]=c
  for to in e[now]:
    if d[to]!=INF:continue
    q.append((to,c+1))
q=[(u,0)]
ans=0
vis=[1]*(n+1)
while q:
  now,c=q.pop()
  vis[now]=0
  f=1
  for to in e[now]:
    if vis[to]:
      f=0
      if d[to]>c+1:q+=[(to,c+1)]
      if d[to]==c+1:ans=max(c+1,ans)
      else:ans=max(c,ans)
  if len(e[now])==1:ans=max(d[to],ans)
print(ans)

Submission status: Accepted

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

mt=[-1 for i in range(n)]
de=[-1 for i in range(n)]
dpl=[]
s=[v]
t=0
while s:
  dpl.append([])
  ns=[]
  for i in s:
    de[i]=t
    dpl[-1].append(i)
    for j in e[i]:
      if de[j]!=-1:
        continue
      ns.append(j)
      mt[j]=i
  s=ns
  t+=1

maxd=[de[i] for i in range(n)]
for i in dpl[:0:-1]:
  for j in i:
    maxd[mt[j]]=max(maxd[mt[j]],maxd[j])

t=de[u]//2+1
while de[u]!=t:
  u=mt[u]
print(maxd[u]-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

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

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

parent = [-1] * (N + 1)
children = [[] for _ in range(N+1)]
degree = [0] * (N + 1)
q = deque([v])
while len(q) > 0:
    node = q.popleft()
    node_d = degree[node]
    for i in g[node]:
        if i == parent[node]:
            continue
        parent[i] = node
        degree[i] = node_d + 1
        children[node].append(i)
        q.append(i)

ans = 0
# uができるとこまで登
tmp = (degree[u] - 1) // 2
for _ in range(tmp):
    u = parent[u]
max_deg = 0
q = deque([u])
while len(q) > 0:
    node = q.popleft()
    max_deg = max(max_deg, degree[node])
    for i in children[node]:
        q.append(i)
print(max_deg-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1<<30)
def dfs(x, dis):
    for y in Tree[x]:
        if parent[y] != x:
            parent[x] = y
            dis[y] = dis[x] + 1
            dfs(y, dis)
N, u, v = map(int,input().split())
Tree = [[] for _ in range(N+1)]
for i in range(N-1):
    A, B = map(int,input().split())
    Tree[A].append(B)
    Tree[B].append(A)
disT = [-1]*(N+1)
disA= [-1]*(N+1)
disT[u] = 0
disA[v] = 0
parent = [-1]*(N+1)
dfs(u, disT)
parent = [-1]*(N+1)
dfs(v, disA)
Ans = 0
for i in range(len(disA)):
    if disA[i] >= disT[i]:
        Ans = max(Ans, disA[i]-1)
print(Ans)

Submission status: Accepted

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

from collections import deque
def bfs(s):
  lis = [-1]*N
  d = deque([s])
  lis[s]=0
  while len(d)>0:
    v = d.popleft()
    for w in edge[v]:
      if lis[w]<0:
        lis[w]=lis[v]+1
        d.append(w)
  return lis

lis1 = bfs(target)
lis2 = bfs(v)
ans = 0
for i in range(N):
  if lis1[i]<lis2[i]:
    ans = max(ans, lis2[i]-1)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
N,T,A = map(int,input().split()); INF = float("inf")
T-=1;A-=1 #0index
G = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int,input().split())
  a-=1;b-=1 #0index
  G[a].append(b);G[b].append(a)

disT = [INF for _ in range(N)]; disT[T] = 0
disA = [INF for _ in range(N)]; disA[A] = 0

def dfs(v, L):
  for u in G[v]:
    if L[u] != INF:
      continue
    L[u] = L[v]+1
    dfs(u,L)
dfs(T,disT)
dfs(A,disA)
#print(disT)
#print(disA)
ans = 0
for i in range(N):
  if disT[i] < disA[i]:
    ans = max(ans,disA[i]-1)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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


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


def bfs(x):
  dist=[-1]*n
  dist[x]=0
  Q=deque()
  Q.append((x))

  while Q:
    q=Q.popleft()
    for i in a[q]:
      if dist[i]==-1:
        dist[i]=dist[q]+1
        Q.append((i))

  return dist

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

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


print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

def search(p):
    stack=deque([p])
    check = [-1]*N
    check[p] = 0

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

taka = search(u-1)
aoki = search(v-1)
ans = 0
for i in range(N):
    if taka[i] < aoki[i]:
        ans = max(ans, aoki[i]-1)
print(ans)

Submission status: Accepted

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

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



from collections import deque

q=deque([])
q.append((v-1,0))
done1=[-1]*N

while q:
    now, dist = q.popleft()
    done1[now]=dist
    for i in G[now]:
        if done1[i]!=-1:
            continue
        q.append((i,dist+1))

q=deque([])
q.append((u-1,0))
done2=[-1]*N

while q:
    now, dist = q.popleft()
    done2[now]=dist
    for i in G[now]:
        if done2[i]!=-1:
            continue
        q.append((i,dist+1))

goal=0
for i in range(N):
    if done1[i]>done2[i]:
        goal=max(goal, done1[i])

ans=goal-1
#print(goal, done1[u-1], done2[v-1])
#print(done1, done2)
print(ans)

Submission status: Accepted

Solution code:
nii=lambda:map(int,input().split())
from collections import deque

n,u,v=nii()
u-=1
v-=1

tree=[[] for i in range(n)]
for i in range(n-1):
  a,b=nii()
  a-=1
  b-=1
  tree[a].append(b)
  tree[b].append(a)

def BFS(s):
  dist=[-1 for i in range(n)]
  dist[s]=0

  que=deque()
  que.append(s)

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

dist_t=BFS(u)
dist_a=BFS(v)

ans=0
for i in range(n):
  if dist_a[i]>dist_t[i]:
    ans=max(ans,dist_a[i]-1)

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import deque

n,u,v=nii()
u-=1
v-=1

tree=[[] for i in range(n)]
for i in range(n-1):
  a,b=nii()
  a-=1
  b-=1
  tree[a].append(b)
  tree[b].append(a)

def BFS(s):
  dist=[-1 for i in range(n)]
  dist[s]=0

  que=deque()
  que.append(s)

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

dist_t=BFS(u)
dist_a=BFS(v)

ans=0
for i in range(n):
  if dist_a[i]>dist_t[i]:
    ans=max(ans,dist_a[i]-1)

print(ans)