Problem:


Score : 600 points

Problem Statement

We have a tree with N vertices. The i-th edge connects Vertex A_i and B_i bidirectionally.

Takahashi is standing at Vertex u, and Aoki is standing at Vertex v.

Now, they will play a game of tag as follows:

1. If Takahashi and Aoki are standing at the same vertex, the game ends. Otherwise, Takahashi moves to a vertex of his choice that is adjacent to his current vertex.

2. If Takahashi and Aoki are standing at the same vertex, the game ends. Otherwise, Aoki moves to a vertex of his choice that is adjacent to his current vertex.

3. Go back to step 1.

Takahashi performs his moves so that the game ends as late as possible, while Aoki performs his moves so that the game ends as early as possible.

Find the number of moves Aoki will perform before the end of the game if both Takahashi and Aoki know each other's position and strategy.

It can be proved that the game is bound to end.

Constraints

2 \leq N \leq 10^5

1 \leq u,v \leq N

u \neq v

1 \leq A_i,B_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N u v
A_1 B_1
:
A_{N-1} B_{N-1}

Output

Print the number of moves Aoki will perform before the end of the game.

Sample Input 1

5 4 1
1 2
2 3
3 4
3 5

Sample Output 1

2

If both players play optimally, the game will progress as follows:

Takahashi moves to Vertex 3.

Aoki moves to Vertex 2.

Takahashi moves to Vertex 5.

Aoki moves to Vertex 3.

Takahashi moves to Vertex 3.

Here, Aoki performs two moves.

Note that, in each move, it is prohibited to stay at the current vertex.

Sample Input 2

5 4 5
1 2
1 3
1 4
1 5

Sample Output 2

1

Sample Input 3

2 1 2
1 2

Sample Output 3

0

Sample Input 4

9 6 1
1 2
2 3
3 4
4 5
5 6
4 7
7 8
8 9

Sample Output 4

5



Sample input:
5 4 1
1 2
2 3
3 4
3 5


Sample output:
2

Submission status: Accepted

Solution code:
from 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)

dist_a=[-1 for i in range(n)]
dist_a[v]=0

dist_t=[-1 for i in range(n)]
dist_t[u]=0


def BFS(dist,s):
  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_a=BFS(dist_a,v)
dist_t=BFS(dist_t,u)

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:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, u, v = mapint()
query = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = mapint()
    query[a-1].append(b-1)
    query[b-1].append(a-1)

from collections import deque
def dfs(start):
    Q = deque([start])
    dist = [10**18]*N
    dist[start] = 0
    while Q:
        now = Q.pop()
        for nx in query[now]:
            if dist[nx]>=10**18:
                dist[nx] = dist[now] + 1
                Q.append(nx)
    return dist

taka = dfs(u-1)
aoki = dfs(v-1)
ans = 0

for i in range(N):
    t, a = taka[i], aoki[i]
    if t<=a:
        ans = max(ans, a-1)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque

def main():
    N, u, v = map(int, input().split())
    s = u-1
    t = v-1
    adj = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(lambda x: int(x)-1, input().split())
        adj[a].append(b)
        adj[b].append(a)
    
    # aoki BFS
    queue = deque([t])
    visit = [-1] * N
    visit[t] = 0
    
    while queue:
        now = queue.popleft()
        for u in adj[now]:
            if visit[u] < 0:
                queue.append(u)
                visit[u] = visit[now] + 1
                # parent[u] = now

    # takahashi BFS
    queue = deque([s])
    visit2 = [-1] * N
    # parent = [-1] * N
    visit2[s] = 0
    
    
    while queue:
        now = queue.popleft()
        for u in adj[now]:
            if visit2[u] < 0:
                queue.append(u)
                visit2[u] = visit2[now] + 1

    ans = [-1,-1]
    # print(visit, visit2)
    for i in range(N):
        if visit[i] >= visit2[i] and visit[i] > ans[0]:
            ans = [visit[i], i]
    
    print(visit[ans[1]]-1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N,u,v = MI()
Graph = [[] for _ in range(N+1)]

for i in range(N-1):
    a,b = MI()
    Graph[a].append(b)
    Graph[b].append(a)

dist_T = [-1]*(N+1)  # uからの最短距離
dist_A = [-1]*(N+1)  # vからの最短距離
dist_T[u] = 0
dist_A[v] = 0

from collections import deque
q1 = deque([u])
q2 = deque([v])
while q1:
    n = q1.pop()
    for d in Graph[n]:
        if dist_T[d] == -1:
            dist_T[d] = dist_T[n] + 1
            q1.appendleft(d)
while q2:
    n = q2.pop()
    for d in Graph[n]:
        if dist_A[d] == -1:
            dist_A[d] = dist_A[n] + 1
            q2.appendleft(d)

ans = 0
for i in range(1,N+1):
    if dist_T[i] < dist_A[i]:
        ans = max(ans,dist_A[i]-1)

print(ans)

Submission status: Accepted

Solution code:
n,u,v=map(int,input().split())
u-=1;v-=1
edge=[[]*n for _ 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)
  
  
# from u 逃げる
# uはvからみた距離が大きい方に進むのかな
# from v 追う
# v始点でBFSして各頂点への距離を持つ
dist=[-1]*n

from collections import deque
q=deque()
q.append(v)
dist[v]=0
while q:
  p=q.popleft()
  d=dist[p]
  for i in edge[p]:
    if dist[i]==-1:
      dist[i]=d+1
      q.append(i)

# print(dist)

far=[-1]*n
q=deque()
q.append(u)
far[u]=0
while q:
  p=q.popleft()
  d=far[p]
  for i in edge[p]:
    if far[i]==-1:
      if dist[i]>d+1:
        far[i]=d+1
        q.append(i)

# print(far)
  

far_mx=max(far)
if far_mx==-1:
  print(0)
  exit()
  
ind=[i for i,v in enumerate(far) if v!=-1]

to=max(dist[i] for i in ind)
ans=(to-1)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10**7)

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

graph = defaultdict(list)

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


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


dist_u = dfs(u)
dist_v = dfs(v)

# 高橋くん（u）の方が近い頂点のうち、青木くん（v）から最も遠い頂点の一つ手前
ans = 0
for x, y in zip(dist_u, dist_v):
    if x < y:
        ans = max(ans, y - 1)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N,u,v = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
distT = [0 for _ in range(N+1)]
heap = deque([(u,0)])
distT[u] = 0
hist = [0 for _ in range(N+1)]
hist[u] = 1
while heap:
    x,d = heap.popleft()
    for y in G[x]:
        if hist[y]==0:
            distT[y] = d+1
            heap.append((y,d+1))
            hist[y]=1
heap = deque([(v,0)])
distA = [0 for _ in range(N+1)]
heap = deque([(v,0)])
distA[v] = 0
hist = [0 for _ in range(N+1)]
hist[v] = 1
while heap:
    x,d = heap.popleft()
    for y in G[x]:
        if hist[y]==0:
            distA[y]=d+1
            heap.append((y,d+1))
            hist[y] = 1
cmax = 0
for i in range(1,N+1):
    if distT[i]<=distA[i] and distA[i]>cmax:
        cmax = distA[i]
print(cmax-1)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N,u,v = MI()
Graph = [[] for _ in range(N+1)]

for i in range(N-1):
    a,b = MI()
    Graph[a].append(b)
    Graph[b].append(a)

dist_T = [-1]*(N+1)
dist_A = [-1]*(N+1)
dist_T[u] = 0
dist_A[v] = 0

from collections import deque
q1 = deque([u])
q2 = deque([v])
while q1:
    n = q1.pop()
    for d in Graph[n]:
        if dist_T[d] == -1:
            dist_T[d] = dist_T[n] + 1
            q1.appendleft(d)
while q2:
    n = q2.pop()
    for d in Graph[n]:
        if dist_A[d] == -1:
            dist_A[d] = dist_A[n] + 1
            q2.appendleft(d)

ans = 0
for i in range(1,N+1):
    if dist_T[i] < dist_A[i]:
        ans = max(ans,dist_A[i]-1)

print(ans)

Submission status: Accepted

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

n, u, v = map(int, input().split())
# よりたかはしくんが早く辿り着ける葉のうち、青木君から最も遠いで
u -= 1
v -= 1

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

INF = 1 << 30
t = [INF] * n
a = [INF] * n

t[u] = 0
a[v] = 0


def dfs(v, p, d):
    for nv in g[v]:
        if nv == p:
            continue
        if d[nv] == INF:
            d[nv] = d[v] + 1
            dfs(nv, v, d)


dfs(u, -1, t)
dfs(v, -1, a)

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

Submission status: Accepted

Solution code:
from collections import deque
def bfs(start, g, visited):
    q = deque([start])
    visited[start] = 0
    while q:
        curr_node = q.popleft()
        for next_node in g[curr_node]:
            if visited[next_node] >= 0: continue
            visited[next_node] = visited[curr_node] + 1
            q.append(next_node)
    

def main():
    n,u,v = map(int, input().split())
    gl = [ [] for _ in range(n+1)]
    visited_u = [-1] * (n+1)
    visited_v = [-1] * (n+1)
    for i in range(n-1):
        a, b = map(int, input().split()) 
        gl[a].append(b)
        gl[b].append(a)
    bfs(u, gl, visited_u)
    bfs(v, gl, visited_v)

    # print(visited_u)
    # print(visited_v)

    # target_i = 0
    # max_diff_v = 0
    ans = 0
    for i in range(1,n+1):
        if visited_u[i] < visited_v[i] and visited_v[i]:
            # if (visited_v[i]-visited_u[i])%2 == 0:
            val = visited_v[i]-1
            ans = max(ans,val)
            # else:
                # val = visited_v[i]
                # ans = max(ans,val)
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
N,U,V = map(int,input().split())
U,V = U-1,V-1
AB = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for _ in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

dist1 = [N] * N
dist1[V] = 0
def dfs1(v,p=-1):
    for to in es[v]:
        if to==p: continue
        dist1[to] = dist1[v] + 1
        dfs1(to,v)
dfs1(V)

D = dist1[U]

dist2 = [N] * N
dist2[U] = 0
def dfs2(v,p=-1):
    for to in es[v]:
        if to==p: continue
        if (D+1)//2 > dist1[to]: continue
        dist2[to] = dist2[v] + 1
        dfs2(to,v)
dfs2(U)

ans = 0
for a,b in zip(dist1,dist2):
    if b==N: continue
    ans = max(ans, a-1)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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)

q = deque()
q.append((u, 0))
depth = [0] * n

visited = set()
while q:
    p, d = q.popleft()
    depth[p] = d
    visited.add(p)
    for x in tree[p]:
        if not x in visited:
            q.append((x, d+1))


q.append((v, 0))
visited.clear()
max_case = max(depth[v] - 1, 0)
while q:
    p, d = q.popleft()
    visited.add(p)
    is_leaf = True
    for x in tree[p]:
        if not x in visited:
            q.append((x, d+1))
            is_leaf = False
    if is_leaf and depth[p] < d:
        max_case = max(max_case, d - 1)
print(max_case)

Submission status: Accepted

Solution code:
class Tree():
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - indexed].append(e[1] - indexed)
            self.tree[e[1] - indexed].append(e[0] - indexed)

    def setroot(self, root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.order = []
        self.order.append(root)
        self.size = [1 for _ in range(self.n)]
        stack = [root]
        while stack:
            node = stack.pop()
            for adj in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node] + 1
                    self.order.append(adj)
                    stack.append(adj)
        for node in self.order[::-1]:
            for adj in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                self.size[node] += self.size[adj]

import sys
input = sys.stdin.readline

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

t = Tree(N, E)
t.setroot(u); dist1 = t.depth
t.setroot(v); dist2 = t.depth

tmp = 0
for i in range(N):
    if dist1[i] < dist2[i]:
        tmp = max(tmp, dist2[i])

print(tmp - 1)

Submission status: Accepted

Solution code:
class Tree():
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - indexed].append(e[1] - indexed)
            self.tree[e[1] - indexed].append(e[0] - indexed)

    def setroot(self, root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.order = []
        self.order.append(root)
        self.size = [1 for _ in range(self.n)]
        stack = [root]
        while stack:
            node = stack.pop()
            for adj in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node] + 1
                    self.order.append(adj)
                    stack.append(adj)
        for node in self.order[::-1]:
            for adj in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                self.size[node] += self.size[adj]

    def heavylight_decomposition(self):
        self.order = [None for _ in range(self.n)]
        self.head = [None for _ in range(self.n)]
        self.head[self.root] = self.root
        self.next = [None for _ in range(self.n)]
        stack = [self.root]
        order = 0
        while stack:
            node = stack.pop()
            self.order[node] = order
            order += 1
            maxsize = 0
            for adj in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                if maxsize < self.size[adj]:
                    maxsize = self.size[adj]
                    self.next[node] = adj
            for adj in self.tree[node]:
                if self.parent[node] == adj or self.next[node] == adj:
                    continue
                self.head[adj] = adj
                stack.append(adj)
            if self.next[node] is not None:
                self.head[self.next[node]] = self.head[node]
                stack.append(self.next[node])

    def range_hld(self, u, v, edge=False):
        res = []
        while True:
            if self.order[u] > self.order[v]: u, v = v, u
            if self.head[u] != self.head[v]:
                res.append((self.order[self.head[v]], self.order[v] + 1))
                v = self.parent[self.head[v]]
            else:
                res.append((self.order[u] + edge, self.order[v] + 1))
                return res

    def subtree_hld(self, u):
        return self.order[u], self.order[u] + self.size[u]

    def lca_hld(self, u, v):
        while True:
            if self.order[u] > self.order[v]: u, v = v, u
            if self.head[u] != self.head[v]:
                v = self.parent[self.head[v]]
            else:
                return u

class SegmentTree():
    def __init__(self, arr, func=min, ie=2**63):
        self.h = (len(arr) - 1).bit_length()
        self.n = 2**self.h
        self.ie = ie
        self.func = func
        self.tree = [ie for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.tree[self.n + i] = arr[i]
        for i in range(1, self.n)[::-1]:
            self.tree[i] = func(self.tree[2 * i], self.tree[2 * i + 1])

    def set(self, idx, x):
        idx += self.n
        self.tree[idx] = x
        while idx:
            idx >>= 1
            self.tree[idx] = self.func(self.tree[2 * idx], self.tree[2 * idx + 1])

    def query(self, lt, rt):
        lt += self.n
        rt += self.n
        vl = vr = self.ie
        while rt - lt > 0:
            if lt & 1:
                vl = self.func(vl, self.tree[lt])
                lt += 1
            if rt & 1:
                rt -= 1
                vr = self.func(self.tree[rt], vr)
            lt >>= 1
            rt >>= 1
        return self.func(vl, vr)

import sys
input = sys.stdin.readline

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

t = Tree(N, E)
t.setroot(v)
t.heavylight_decomposition()

d = t.depth[u]
k = (d + 1) // 2 - 1

for _ in range(k):
    u = t.parent[u]

arr = [None for _ in range(N)]
for i in range(N):
    arr[t.order[i]] = t.depth[i]

st = SegmentTree(arr, max, -1)
lt, rt = t.subtree_hld(u)
maxdep = st.query(lt, rt)

print(maxdep - 1)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]
def adjacency_list(N, edges):
    g = make_list(N, 0)
    for a, b in edges: g[a].append(b), g[b].append(a)
    return g
def tree_utils(start, g):
    parent, children, depth, q = [-1]*len(g), make_list(len(g), 0), [-1]*len(g), deque([start]); depth[start] = 0
    while q:
        i = q.popleft()
        for j in g[i]:
            if depth[j] != -1: parent[i] = j
            else: depth[j] = depth[i] + 1; children[i].append(j), q.append(j)
    return parent, children, depth
def graph_distance(start, g):
    dist, q = [-1] * len(g), deque([start]); dist[start] = 0
    while q:
        i = q.popleft()
        for j in g[i]:
            if dist[j] == -1: dist[j] = dist[i] + 1; q.append(j)
    return dist

sys.setrecursionlimit(1000000)
dire, dire8 = [[1, 0], [0, 1], [-1, 0], [0, -1]], [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets, ALPHABETS = "abcdefghijklmnopqrstuvwxyz", "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD, INF = 1000000007, float("inf")

def main():
    N, u, v = LI()
    AB = LIR1(N-1)
    max_dist = [None] * N
    g = adjacency_list(N, AB)
    udist = graph_distance(u-1, g)
    vdist = graph_distance(v-1, g)

    ans = vdist[u-1] - 1
    for ud, vd in zip(udist, vdist):
        if ud < vd:
            ans = max(ans, vd - 1)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]
def adjacency_list(N, edges):
    g = make_list(N, 0)
    for a, b in edges: g[a].append(b), g[b].append(a)
    return g
def tree_utils(start, g):
    parent, children, depth, q = [-1]*len(g), make_list(len(g), 0), [-1]*len(g), deque([start]); depth[start] = 0
    while q:
        i = q.popleft()
        for j in g[i]:
            if depth[j] != -1: parent[i] = j
            else: depth[j] = depth[i] + 1; children[i].append(j), q.append(j)
    return parent, children, depth
def graph_distance(start, g):
    dist, q = [-1] * len(g), deque([start]); dist[start] = 0
    while q:
        i = q.popleft()
        for j in g[i]:
            if dist[j] == -1: dist[j] = dist[i] + 1; q.append(j)
    return dist

sys.setrecursionlimit(1000000)
dire, dire8 = [[1, 0], [0, 1], [-1, 0], [0, -1]], [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets, ALPHABETS = "abcdefghijklmnopqrstuvwxyz", "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD, INF = 1000000007, float("inf")

def main():
    N, u, v = LI()
    AB = LIR1(N-1)
    max_dist = [None] * N
    g = adjacency_list(N, AB)
    udist = graph_distance(u-1, g)
    vdist = graph_distance(v-1, g)

    visit = [False] * N
    ans = vdist[u-1] - 1
    q = deque([u-1])
    while q:
        i = q.popleft()
        visit[i] = True
        if udist[i] < vdist[i]:
            ans = max(ans, vdist[i]-1)
            for j in g[i]:
                if not visit[j]:
                    q.append(j)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]
def parent_children(start, g):
    parent, children, depth, q = [-1]*len(g), make_list(len(g), 0), [-1]*len(g), deque([start]); depth[start] = 0
    while q:
        i = q.popleft()
        for j in g[i]:
            if depth[j] != -1: parent[i] = j
            else: depth[j] = depth[i] + 1; children[i].append(j), q.append(j)
    return parent, children, depth
def adjacency_list(N, edges):
    g = make_list(N, 0)
    for a, b in edges: g[a].append(b), g[b].append(a)
    return g

sys.setrecursionlimit(1000000)
dire, dire8 = [[1, 0], [0, 1], [-1, 0], [0, -1]], [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets, ALPHABETS = "abcdefghijklmnopqrstuvwxyz", "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD, INF = 1000000007, float("inf")

def main():
    N, u, v = LI()
    AB = LIR1(N-1)
    max_dist = [None] * N
    g = adjacency_list(N, AB)
    parent, children, depth = parent_children(v-1, g)

    def dfs(i):
        dist = max([0] + [dfs(j) for j in children[i]])
        max_dist[i] = dist
        return dist + 1
    mid = u-1
    for _ in range((depth[u-1] - 1)//2):
        mid = parent[mid]
    dfs(mid)
    print(depth[mid] + max_dist[mid] - 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, deque
    n, u, v = map(int, readline().split())
    edge = defaultdict(list)

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

    dist_first = defaultdict(lambda: float("INF"))
    dist_second = defaultdict(lambda: float("INF"))
    dist_first[u] = 0
    dist_second[v] = 0
    leaf = set()

    que = deque()
    que.append((v, 0))
    while que:
        cur, cost = que.popleft()
        new_cost = cost + 1
        is_leaf = True
        for nx in edge[cur]:
            if dist_second[nx] == INF:
                que.append((nx, new_cost))
                dist_second[nx] = new_cost
        if len(edge[cur]) == 1:
            leaf.add(cur)

    que.append((u, 0))
    while que:
        cur, cost = que.popleft()
        if cost < dist_second[cur]:
            new_cost = cost + 1
            for nx in edge[cur]:
                if dist_first[nx] == INF:
                    que.append((nx, new_cost))
                    dist_first[nx] = new_cost

    ans = 0
    for i in range(1, n + 1):
        if i in leaf:
            first = dist_first[i]
            second = dist_second[i]
            if first == INF:
                continue
            ans = max(ans, second - 1)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# F - Playing Tag on Tree
# https://atcoder.jp/contests/abc148/tasks/abc148_f

from heapq import heappop, heappush

INF = float("inf")

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    hq = [(0, s)]
    while hq:
        d, v = heappop(hq)
        if dist[v] < d:
            continue
        for child, child_d in G[v]:
            if dist[child] > dist[v] + child_d:
                dist[child] = dist[v] + child_d
                heappush(hq, (dist[child], child))
    return dist

n, u, v = map(int, input().split())
graph = [[] for _ in range(n)]

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

for a, b in edge:
    graph[a - 1].append((b - 1, 1))
    graph[b - 1].append((a - 1, 1))

from_u = dijkstra(n, graph, u - 1)
from_v = dijkstra(n, graph, v - 1)

# print(from_u)
# print(from_v)

fil = filter(lambda x : x[0] < x[1], [[fu, fv] for fu, fv in zip(from_u, from_v)])
sfil = sorted(list(fil), key=lambda x: [-x[1], -x[0]])  

# print(sfil)

print(sfil[0][1] - 1)

Submission status: Accepted

Solution code:

def resolve():
    def dfs(v):
        dist = [-1] * N
        stack = [v]
        dist[v] = 0
        while stack:
            v = stack.pop()
            for to in G[v]:
                if dist[to] != -1:
                    continue
                dist[to] = dist[v] + 1
                stack.append(to)
        return dist

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

    dist_Tk = dfs(taka)
    dist_Ao = dfs(aoki)

    ans = 0
    for i in range(N):
        if dist_Tk[i] < dist_Ao[i]:
            ans = max(ans, dist_Ao[i] - 1)

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#f
N,U,V = map(int,input().split())
U-=1
V-=1
tree =[[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    tree[a].append(b)
    tree[b].append(a)

from collections import deque
def shortest(tree,start):
    from_start=[None]*N
    q = deque([(-1,start,0)])
    while q:
        parent,x,time = q.popleft()
        if tree[x]==[parent] or (len(tree[x])==1 and parent==-1):#行き先が親しかない＝＝葉ノード
            from_start[x]=time
        for y in tree[x]:
            if y == parent:#親ノードを飛ばし
                continue
            q.append((x,y,time+1))#子ノードを追加
    return from_start

from_u = shortest(tree,U)
from_v = shortest(tree,V)

print( max([vv for uu,vv in zip(from_u,from_v) 
            if isinstance(uu, int) and isinstance(vv, int) and uu<vv])-1 )

Submission status: Accepted

Solution code:
def main():
    from collections import defaultdict,deque
    from math import ceil
    from sys import setrecursionlimit
    setrecursionlimit(10**6)
    f = lambda :map(int,input().split())
    n,u,v = f() # u:高橋
    edge = defaultdict(list)
    for i in range(n-1):
        a,b = f()
        edge[a].append(b)
        edge[b].append(a)
    
    distance = [[-1]*2 for _ in range(n+1)]
    distance[u][0] = 0
    distance[v][1] = 0
    def dfs(node,start):
        targets = deque([node])
        while targets:
            parent = targets.popleft()
            distance_parent = distance[parent][start]
            for child in edge[parent]:
                if distance[child][start] == -1:
                    distance[child][start] = distance_parent + 1
                    targets.append(child)
    dfs(u,0)
    dfs(v,1)
    ans = 0
    for u_d, v_d in distance:
        if u_d < v_d:
            ans = max(ans,v_d)
    print(ans-1)


        


main()