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 sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
write = sys.stdout.write
def ii(): return int(readline())
def mi(): return map(int, readline().rstrip().split())
def li(): return list(readline().rstrip())
def lmi(): return list(map(int, readline().rstrip().split()))
def end(*arg): print(*arg); sys.exit()
# template

class edge():
    def __init__(self, src, to):
        self.src = src
        self.to = to
    def __str__(self):
        return "(" + str(self._from) + ", " + str(self._to) + ")"

from queue import Queue as queue
class rootedtree():
    def __init__(self, n):
        _l = 0
        while pow(2, _l) < n:
            _l += 1
        self._l = _l
        self.size = n
        self.par = [[-1 for i in range(n + 1)] for i in range(_l)]
        self.graph = [[] for i in range(n)]
        self.depth = [-1 for i in range(n)]
        self.root = -1

    def add_edge(self, src, to):
        self.graph[src].append(edge(src, to))
        self.graph[to].append(edge(to, src))

    def parent(self, i):
        return self.par[0][i]

    def bfs(self, s: int) -> list:
        dist = [10**9] * self.size
        que = queue()
        que.put(s)
        dist[s] = 0
        while not que.empty():
            v = que.get()
            for e in self.graph[v]:
                if dist[e.to] != 10**9:
                    continue
                dist[e.to] = dist[e.src] + 1
                que.put(e.to)
        return dist

    def __dfs1(self, r) -> None:
        root = r
        self.depth[r] = 0
        que = queue()
        que.put((0, root))
        while not que.empty():
            v = que.get()
            for u in self.graph[v[1]]:
                if u.to != self.parent(v[1]):
                    self.par[0][u.to] = v[1]
                    self.depth[u.to] = v[0] + 1
                    que.put((v[0] + 1, u.to))

    def build(self, _root=0) -> None:
        assert(self.root == -1)
        self.root = _root
        self.__dfs1(self.root)
        for i in range(self._l - 1):
            for j in range(self.size):
                if(self.par[i][j] == -1):
                    self.par[i + 1][j] = -1
                else:
                    self.par[i + 1][j] = self.par[i][self.par[i][j]]

    def lca(self, x: int, y: int) -> int:
        assert(self.root != -1)
        if self.depth[x] > self.depth[y]:
            x, y = y, x
        dif = self.depth[y] - self.depth[x]
        for i in range(self._l - 1, -1, -1):
            if dif & (1 << i):
                y = self.par[i][y]
        if x == y:
            return x
        for i in range(self._l - 1, -1, -1):
            nx = self.par[i][x]
            ny = self.par[i][y]
            if nx != ny:
                x = nx; y = ny
        return self.par[0][x]

    def depth_dif(self, x: int, y: int) -> int:
        assert(self.root != -1)
        z = self.lca(x, y)
        return self.depth[x] + self.depth[y] - 2 * self.depth[z]

def main():
    n, u, v = mi()
    u -= 1; v -= 1
    g = rootedtree(n)
    for _ in range(n - 1):
        a, b = mi()
        g.add_edge(a - 1, b - 1)
    du = g.bfs(u)
    dv = g.bfs(v)
    ans = -1
    for i in range(n):
        if du[i] < dv[i]:
            ans = max(ans, dv[i])
    print(ans - 1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def treeDist(u, E):
    D = [-1]*len(E)
    q = [(u, 0)]
    while q:
        i, d = q.pop()
        if D[i] != -1:
            continue
        D[i] = d
        for j in E[i]:
            q.append((j, d+1))
    return D


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

    D1 = treeDist(u-1, E)
    D2 = treeDist(v-1, E)
    ans = 0
    for d1, d2 in zip(D1, D2):
        if d1 < d2:
            ans = max(ans, d2)
    print(ans-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
write = sys.stdout.write
def ii(): return int(readline())
def mi(): return map(int, readline().rstrip().split())
def li(): return list(readline().rstrip())
def lmi(): return list(map(int, readline().rstrip().split()))
def end(*arg): print(*arg); sys.exit()
# template

class edge():
    def __init__(self, src, to):
        self.src = src
        self.to = to
    def __str__(self):
        return "(" + str(self._from) + ", " + str(self._to) + ")"

import collections
class rootedtree():
    def __init__(self, n):
        _l = 0
        while pow(2, _l) < n:
            _l += 1
        self._l = _l
        self.size = n
        self.par = [[-1 for i in range(n + 1)] for i in range(_l)]
        self.graph = [[] for i in range(n)]
        self.depth = [-1 for i in range(n)]
        self.root = -1

    def add_edge(self, src, to):
        self.graph[src].append(edge(src, to))
        self.graph[to].append(edge(to, src))

    def parent(self, i):
        return self.par[0][i]

    def bfs(self, s: int) -> list:
        dist = [10**9] * self.size
        que = collections.deque()
        que.append(s)
        dist[s] = 0
        while len(que):
            v = que.popleft()
            for e in self.graph[v]:
                if dist[e.to] != 10**9:
                    continue
                dist[e.to] = dist[e.src] + 1
                que.append(e.to)
        return dist

    def __dfs1(self, r) -> None:
        root = r
        self.depth[r] = 0
        que = collections.deque()
        que.append((0, root))
        while len(que) != 0:
            v = que.pop()
            for u in self.graph[v[1]]:
                if u.to != self.parent(v[1]):
                    self.par[0][u.to] = v[1]
                    self.depth[u.to] = v[0] + 1
                    que.append((v[0] + 1, u.to))

    def build(self, _root=0) -> None:
        assert(self.root == -1)
        self.root = _root
        self.__dfs1(self.root)
        for i in range(self._l - 1):
            for j in range(self.size):
                if(self.par[i][j] == -1):
                    self.par[i + 1][j] = -1
                else:
                    self.par[i + 1][j] = self.par[i][self.par[i][j]]

    def lca(self, x: int, y: int) -> int:
        assert(self.root != -1)
        if self.depth[x] > self.depth[y]:
            x, y = y, x
        dif = self.depth[y] - self.depth[x]
        for i in range(self._l - 1, -1, -1):
            if dif & (1 << i):
                y = self.par[i][y]
        if x == y:
            return x
        for i in range(self._l - 1, -1, -1):
            nx = self.par[i][x]
            ny = self.par[i][y]
            if nx != ny:
                x = nx; y = ny
        return self.par[0][x]

    def depth_dif(self, x: int, y: int) -> int:
        assert(self.root != -1)
        z = self.lca(x, y)
        return self.depth[x] + self.depth[y] - 2 * self.depth[z]

def main():
    n, u, v = mi()
    u -= 1; v -= 1
    g = rootedtree(n)
    for _ in range(n - 1):
        a, b = mi()
        g.add_edge(a - 1, b - 1)
    du = g.bfs(u)
    dv = g.bfs(v)
    ans = -1
    for i in range(n):
        if du[i] < dv[i]:
            ans = max(ans, dv[i])
    print(ans - 1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
write = sys.stdout.write
def ii(): return int(readline())
def mi(): return map(int, readline().rstrip().split())
def li(): return list(readline().rstrip())
def lmi(): return list(map(int, readline().rstrip().split()))
def end(*arg): print(*arg); sys.exit()
# template

import collections
class edge():
    def __init__(self, src, to):
        self.src = src
        self.to = to
    def __str__(self):
        return "(" + str(self._from) + ", " + str(self._to) + ")"

class rootedtree():
    def __init__(self, n):
        l = 0
        while pow(2, l) < n:
            l += 1
        self._l = l
        self.size = n
        self.par = [[-1 for i in range(n + 1)] for i in range(l)]
        self.graph = [[] for i in range(n)]
        self.depth = [-1 for i in range(n)]
        self.root = -1

    def add_edge(self, src, to):
        self.graph[src].append(edge(src, to))
        self.graph[to].append(edge(to, src))

    def parent(self, i):
        return self.par[0][i]

    def __dfs1(self, r) -> None:
        root = r
        self.depth[r] = 0
        que = collections.deque()
        que.append((0, root))
        while len(que) != 0:
            v = que.pop()
            for u in self.graph[v[1]]:
                if u.to != self.parent(v[1]):
                    self.par[0][u.to] = v[1]
                    self.depth[u.to] = v[0] + 1
                    que.append((v[0] + 1, u.to))

    def build(self, _root=0) -> None:
        assert(self.root == -1)
        self.root = _root
        self.__dfs1(self.root)
        for i in range(self._l - 1):
            for j in range(self.size):
                if(self.par[i][j] == -1):
                    self.par[i + 1][j] = -1
                else:
                    self.par[i + 1][j] = self.par[i][self.par[i][j]]

    def lca(self, x: int, y: int) -> int:
        assert(self.root != -1)
        if self.depth[x] > self.depth[y]:
            x, y = y, x
        dif = self.depth[y] - self.depth[x]
        for i in range(self._l - 1, -1, -1):
            if dif & (1 << i):
                y = self.par[i][y]
        if x == y:
            return x
        for i in range(self._l - 1, -1, -1):
            nx = self.par[i][x]
            ny = self.par[i][y]
            if nx != ny:
                x = nx; y = ny
        return self.par[0][x]

    def depth_dif(self, x: int, y: int) -> int:
        assert(self.root != -1)
        z = self.lca(x, y)
        return self.depth[x] + self.depth[y] - 2 * self.depth[z]

def main():
    n, u, v = mi()
    u -= 1; v -= 1
    g = rootedtree(n)
    for _ in range(n - 1):
        a, b = mi()
        g.add_edge(a - 1, b - 1)
    g.build(v)
    ans = -1
    for i in range(n):
        x = g.lca(u, i)
        if g.depth_dif(u, x) < g.depth_dif(v, x):
            ans = max(ans, g.depth_dif(v, i))
    print(ans - 1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def dfs(v):
    dist = [-1 for _ in range(N+1)]
    stack = [v]
    dist[v] = 0
    while stack:
        v = stack.pop()
        dist_x = dist[v] + 1
        for child in graph[v]:
            if 0 <= dist[child]:
                continue
            dist[child] = dist_x
            stack.append(child)
    return dist


def solve():
    dist_u, dist_v = dfs(u), dfs(v)
    
    ans = 0
    for a, b in zip(dist_u[1:], dist_v[1:]):
        if a < b:
            ans = max(ans, b-1)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

    # x,y それぞれの depth を計算する
    dx=[None]*n
    dx[x]=0
    Q=[(x,-1)]
    while(Q):
        v,p=Q.pop()
        for nv in E[v]:
            if(nv==p): continue
            dx[nv]=dx[v]+1
            Q.append((nv,v))

    dy=[None]*n
    dy[y]=0
    Q=[(y,-1)]
    while(Q):
        v,p=Q.pop()
        for nv in E[v]:
            if(nv==p): continue
            dy[nv]=dy[v]+1
            Q.append((nv,v))

    # x の方が y より近い点 v に対して、その1つ手前で捕まる
    ans=0
    for v in range(n):
        if(dx[v]<dy[v]):
            ans=max(ans,dy[v]-1)

    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip()
na = lambda: list(map(int, stdin.readline().split()))
ni = lambda: int(ns())
sys.setrecursionlimit(200000)

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

g = [[] for _ in range(n)]

for i in range(0, n-1):
    (a, b) = na()
    g[a-1].append(b-1)
    g[b-1].append(a-1)


dep1 = [0] * n
dep2 = [0] * n
def dfs(now, pre, d, dep):
    dep[now] = d
    for nex in g[now]:
        if pre == nex:
            continue
        dfs(nex,now,d+1,dep)


dfs(u, -1, 0, dep1)
dfs(v, -1, 0, dep2)

ret = 0
for i in range(n):
    if dep1[i] < dep2[i]:
        ret = max(ret, dep2[i]-1)
print(ret)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    N, u, v, *AB = map(int, open(0).read().split())

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

    def game(s):
        D = [-1] * (N + 1)
        D[s] = 0

        Q = deque([s])
        while Q:
            a = Q.popleft()
            for b in E[a]:
                if D[b] != -1:
                    continue
                D[b] = D[a] + 1
                Q.append(b)

        return D[1:]

    taka = game(u)
    aoki = game(v)

    print(-1 + max(a for t, a in zip(taka, aoki) if t < a))

main()

Submission status: Accepted

Solution code:
def f(s):
  d=[-1]*-~n
  d[s]=0
  q=[s]
  while q:
    v=q.pop()
    c=d[v]+1
    for w in e[v]:
      if d[w]<0:
        d[w]=c
        q+=w,
  return d
n,u,v,*t=map(int,open(0).read().split())
e=[[]for _ in range(n+1)]
for a,b in zip(*[iter(t)]*2):
  e[a]+=b,
  e[b]+=a,
m=0
for a,b in zip(*map(f,(u,v))):
  if a<b:m=max(m,b-1)
print(m)

Submission status: Accepted

Solution code:
N,U,V = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
U,V = U-1,V-1

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

if len(es[U]) == 1 and es[U][0] == V:
    print(0)
    exit()

dv = [N] * N
dv[V] = 0
stack = [V]
while stack:
    v = stack.pop()
    for to in es[v]:
        if dv[to] != N: continue
        dv[to] = dv[v]+1
        stack.append(to)

ok = dv[U] - (dv[U]-1) // 2

visited = [0] * N
visited[U] = 1
stack = [U]
while stack:
    v = stack.pop()
    for to in es[v]:
        if visited[to]: continue
        if dv[to] < ok: continue
        visited[to] = 1
        stack.append(to)

mx = -1
for i in range(N):
    if not visited[i]: continue
    mx = max(mx, dv[i])
print(mx - 1)

Submission status: Accepted

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

def bfs(s):
    dist = [-1]*N
    q = deque([s])
    dist[s] = 0
    
    while q:
        v = q.popleft()
        
        for nv in adj_list[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+1
                q.append(nv)
    
    return dist

N, u, v = map(int, input().split())
adj_list = [[] for _ in range(N)]
degree = [0]*N

for _ in range(N-1):
    Ai, Bi = map(int, input().split())
    adj_list[Ai-1].append(Bi-1)
    adj_list[Bi-1].append(Ai-1)
    degree[Ai-1] += 1
    degree[Bi-1] += 1
    
d1 = bfs(u-1)
d2 = bfs(v-1)
ans = 0

for i in range(N):
    if degree[i]==1 and d1[i]<d2[i]:
        ans = max(ans, d2[i]-1)
        
    #if d1[i]==d2[i] and d1[i]+d2[i]==d1[v-1]:
        #ans = max(ans, d1[i])
    
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500*500) # default 1000

class neighborList():
    def __init__(self,N):
        self.to=[[] for j in range(N)] # N points

def calcDist(v_,p=-1,dist=0): # vertices & parent idx
    distList[v_]=dist
    lst=neighborList.to[v_] # children list
    for child in lst:
        if child==p:
            continue
        calcDist(child,v_,dist+1)
    return distList

# input
N, u, v = map(int, input().strip().split()) # t,a
u-=1
v-=1
neighborList = neighborList(N)
for i in range(N-1):
    A, B = map(int, input().strip().split())
    A-=1 # start from 0
    B-=1
    neighborList.to[A].append(B)
    neighborList.to[B].append(A)

distList=[0]*N
distT = calcDist(u)
distList=[0]*N
distA = calcDist(v)

mx=0
for i in range(N):
    if distT[i] < distA[i]:
        mx=max(mx,distA[i])
print(mx-1)

Submission status: Accepted

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

def bfs(s):
    dist = [-1]*N
    q = deque([s])
    dist[s] = 0
    
    while q:
        v = q.popleft()
        
        for nv in adj_list[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+1
                q.append(nv)
    
    return dist

N, u, v = map(int, input().split())
adj_list = [[] for _ in range(N)]
degree = [0]*N

for _ in range(N-1):
    Ai, Bi = map(int, input().split())
    adj_list[Ai-1].append(Bi-1)
    adj_list[Bi-1].append(Ai-1)
    degree[Ai-1] += 1
    degree[Bi-1] += 1
    
d1 = bfs(u-1)
d2 = bfs(v-1)
ans = 0

for i in range(N):
    if degree[i]==1 and d1[i]<d2[i]:
        ans = max(ans, d2[i]-1)
        
    if d1[i]==d2[i] and d1[i]+d2[i]==d1[v-1]:
        ans = max(ans, d1[i])
    
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N, u, v = IL()
ab = [IL() for _ in range(N-1)]

aoki = [0]*(N+1)
aoki_visited = [False]*(N+1)
choku = [0]*(N+1)
choku_visited = [False]*(N+1)

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

d = deque([[v,0]])
while d:
  n,cnt = d.popleft()
  aoki_visited[n] = True
  aoki[n] = cnt
  for x in edge[n]:
    if aoki_visited[x] == False:
      d.append([x, cnt+1])

dd = deque([[u,0]])
while dd:
  n,cnt = dd.popleft()
  choku_visited[n] = True
  if cnt <= aoki[n]:
    choku[n] = cnt
  for x in edge[n]:
    if choku_visited[x] == False:
      dd.append([x, cnt+1])

#print(aoki)
#print(choku)

ans = 0
for i in range(N+1):
  if choku[i] == 0 and i != u:
    continue
  if aoki[i] > choku[i]:
    ans = max(ans, aoki[i] - 1)

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(200000)
n,u,v = map(int,input().split())
edge = [[] for i in range(n+1)]
distt = [0 for i in range(n+1)]
dista = [0 for i in range(n+1)]

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

def tdfs(x, last = -1):
    for to in edge[x]:
        if(to == last):continue
        distt[to] = distt[x] + 1
        tdfs(to, x)

def adfs(x, last = -1):
    for to in edge[x]:
        if(to == last):continue
        dista[to] = dista[x] + 1
        adfs(to, x)

tdfs(u)
adfs(v)
ans = 0

for i in range(1, n+1):
    if distt[i] >= dista[i]:continue
    l = distt[i]
    k = dista[i] - distt[i]
    ans = max(ans, k - 1 + l)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,U,V = map(int, input().split())
d = [set() for _ in range(N+1)]
dps = [0 for _ in range(N+1)]
dpss = [0 for _ in range(N+1)]

def it(v):
    stack = [v]
    vs = set()
    path = []
    while True:
        if not len(stack):
            break
        v = stack.pop()
        if v > 0:
            path.append(v)
            vs.add(v)
            for u in d[v]:
                if u in vs:
                    continue
                if u == V:
                    r = path[:]
                dps[u] = dps[v] + 1
                stack.append(-v)
                stack.append(u)
        else:
            path.pop()
    return r

def it2(v, path):
    stack = [v]
    vs = set()
    while True:
        if not len(stack):
            break
        v = stack.pop()
        vs.add(v)
        for u in d[v]:
            if u in vs:
                continue
            if dps[v] >= dpss[v] and u not in path:
                continue
            dpss[u] = dpss[v] + 1
            stack.append(u)

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

path = set(it(U))
it2(V, path)
print(max(dpss)-1)

Submission status: Accepted

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

n,u,v = map(int, input().split())
adjacent_list = [[] for i in range(n+1)]
aoki = [0 for i in range(n+1)]
takahashi = [0 for i in range(n+1)]
for i in range(n-1):
    a,b = map(int ,input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)

def dfs(node, count,li):
    li[node] = count
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i, count + 1,li)
def dfs_par(node, count,li):
    global node_par
    li[node] = count
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            node_par[i] = node
            dfs_par(i, count + 1,li)
        
node_par = [0 for i in range(n+1)]

finished = set()
dfs(u,0,takahashi)

#辿って親保存しとく
finished = set()
dfs_par(v,0,aoki)

#さかのぼれるとこまで行く,startがさかのぼれる最大のノーど
par = u
start = u
while takahashi[par] < aoki[par]:
    start = par
    par = node_par[start]

ans_height = [0 for i in range(n+1)]
finished = set([node_par[start]])
dfs(start,0,ans_height)
print(max(ans_height) + aoki[start] - 1)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
import heapq
input = sys.stdin.readline
N, u, v = map(int, input().split())
e = dd(list)
for _ in range(N - 1):
  a, b = map(int, input().split())
  e[a].append((b, 1))
  e[b].append((a, 1))
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 6)
      v0 = v // (10 ** 6)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 6) + p[0])
    return d
d = dijkstra(N, e)
p = d.path(v, 0)
pp = d.path(u, 0)
#print(p)
#print(pp)
res = 0
for i in range(1, N + 1):
  if p[i] > pp[i]: res = max(p[i], res)
print(res - 1)

Submission status: Accepted

Solution code:
from collections import deque
N,u,v = map(int,input().split())
edge = [[] for i 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)

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

ud,vd = bfs(u),bfs(v)
ans = 0
for ud_i,vd_i in zip(ud,vd): ans = max(ans, vd_i-1) if ud_i<vd_i else ans
print(ans)

Submission status: Accepted

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)

isLeaf, dU, dV = [len(g) == 1 for g in G], [-1] * N, [-1] * N

for D, P in [(dU, u - 1), (dV, v - 1)]:
    S = [(P, 0)]
    while len(S) > 0:
        p, d = S.pop()
        D[p] = d
        for g in G[p]:
            if D[g] == -1:
                S.append((g, d + 1))

ans = 0
for i in range(N):
    if isLeaf[i] and dU[i] < dV[i]:
        ans = max(ans, dV[i] - 1)

print(ans)

Submission status: Accepted

Solution code:
n, u, v = map(int, input().split())
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)
  
  
dt = [-1]*n
da = [-1]*n

from collections import deque
def dfs(g, s, d_list):
  stack = deque()
  stack.append(s)
  d_list[s] = 0
  while stack:
    x = stack.pop()
    for new_x in g[x]:
      if d_list[new_x] == -1:
        stack.append(new_x)
        d_list[new_x] = d_list[x]+1
  return d_list

dt = dfs(g, u, dt)
da = dfs(g, v, da)

d = 0
for i in range(n):
  if dt[i] < da[i]:
    d = max(d, da[i])
    
print(d-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
N, u, v = map(int, input().split())
G = {k: [] for k in range(N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    # 無向グラフ
    G[a].append(b)
    G[b].append(a)


def dfs(ci, d, p, dist):
    dist[ci] = d
    for ni in G[ci]:
        if ni == p:
            continue
        dfs(ni, d+1, ci, dist)


def calcDist(start):
    dist = [-1]*(N+1)
    dfs(start, 0, -1, dist)
    return dist


distU = calcDist(u)
distV = calcDist(v)

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

graph = [ [] for _ in range(N+1) ]

#双方向だから両矢印に。
for a, b in ab_list:
  graph[a].append(b)
  graph[b].append(a)
  
def dfs(v):
  dist = [-1] * (N+1)
  stack = [v]
  dist[v] = 0
  while stack:
    v = stack.pop()
    dw = dist[v] + 1
    for w in graph[v]:
      if dist[w] >= 0:
        continue
      dist[w] = dw
      stack.append(w)
  return dist

#到達できる最小回数
DU = dfs(u)
DV = dfs(v)

answer = 0
for u, v in zip(DU[1:], DV[1:]):
  if u < v:
    #　到達できちゃう天を洗い出し
    x = v - 1
    answer = max(answer, x)

print(answer)

Submission status: Accepted

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


import heapq
def dijkstra(s, E):
    inf = float("inf")
    d = [inf for i in range(len(E))]
    d[s] = 0
    q = [(0, s)]
    while q:
        c, p = heapq.heappop(q)
        if d[p] < c:
            continue
        for cost, to in E[p]:
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q, (d[to], to))
    return d


def main():
    N, u, v = map(int, input().split())
    E = [[] for i in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        E[a-1].append((1, b-1))
        E[b-1].append((1, a-1))
    du = dijkstra(u-1, E)
    dv = dijkstra(v-1, E)
    ans = 0
    for i, j in zip(du, dv):
        if i < j:
            ans = max(ans, j)
    print(ans - 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline
N, u, v = [int(x) for x in input().strip().split()]

m = [[] for n in range(N)]
f_aokikun = [False for n in range(N)]
f_takahashikun = [False for n in range(N)]
aokikun = [0 for n in range(N)]
takahashikun = [0 for n in range(N)]
takahashikun_enable = [1 for n in range(N)]
for n in range(N-1):
    a, b = [int(x) for x in input().strip().split()]
    m[a-1].append(b)
    m[b-1].append(a)

def aokifunc(c, f, p, cost):
    c[p-1] = cost
    f[p-1] = True
    for p_next in m[p-1]:
        if f[p_next-1]:
            continue
        aokifunc(c, f, p_next, cost+1)

def takahashifunc(c, f, p, cost, aokikun, takahashikun_enable):
    if aokikun[p-1] <= cost:
        takahashikun_enable[p-1] = 0
    c[p-1] = 0
    f[p-1] = True
    for p_next in m[p-1]:
        if f[p_next-1]:
            continue
        takahashifunc(c, f, p_next, cost+1, aokikun, takahashikun_enable)

aokifunc(aokikun, f_aokikun, v, 0)
takahashifunc(takahashikun, f_takahashikun, u, 0, aokikun, takahashikun_enable)
print(max([i * j for i, j in zip(aokikun, takahashikun_enable)])-1)

Submission status: Accepted

Solution code:
n,u,v=[int(j) for j in input().split()]
u,v=u-1,v-1
l=[[] for i in range(n)]
for i in range(n-1):
    a,b=[int(j)-1 for j in input().split()]
    l[a].append(b)
    l[b].append(a)
k=[10**18 for i in range(n)]
from collections import deque
q=deque([u])
k[u]=0
s=set()
while q:
    p=q.popleft()
    s.add(p)
    for i in l[p]:
        if i not in s:
            q.append(i)
            k[i]=k[p]+1

k2=[10**18 for i in range(n)]
from collections import deque
q=deque([v])
k2[v]=0
s=set()
while q:
    p=q.popleft()
    s.add(p)
    for i in l[p]:
        if i not in s:
            q.append(i)
            k2[i]=k2[p]+1
ans=0
for i in range(n):
    if k[i]<=k2[i]:
        if ans<k2[i]:
            ans=k2[i]

print(ans-1)

Submission status: Accepted

Solution code:
N,U,V = map(int, input().split())

"""
高橋くんの戦略
最も遠くに行けるなら言って往復
そのためには、遠くに行くときのポイントに青木より早く到達しなければいけない
青木くん -> 最も遠くに向かって進んでいく
"""

from collections import deque
# 木構造を作る
G = [[] for i in range(N)]
for i in range(N-1):
    # グラフに頂点を追加(距離があるときは,u,vの後に入れる)
    u,v = map(int,input().split())
    G[u-1].append((v-1))
    G[v-1].append((u-1))


## aoki
used_a = [-1] * N
used_a[V-1] = 0 
q = deque([V-1])
while len(q) > 0:
    a = q.popleft()
    Vs = G[a]
    for u in Vs:
        if used_a[u] == -1:
            q.append(u)
            used_a[u] = used_a[a] + 1

## takahashi
used_t = [-1] * N
used_t[U-1] = 0 
q = deque([U-1])
while len(q) > 0:
    a = q.popleft()
    Vs = G[a]
    for u in Vs: 
        if used_t[u] == -1:
            q.append(u)
            used_t[u] = used_t[a] + 1

ans = 0
# print("aoki",used_a)
# print("taka",used_t)
for a,t in zip(used_a,used_t):
    if a > t: # 高橋くんのほうが近い=先に達することができる
        ans = max(ans,a-1)
print(ans)