Problem:


Score : 600 points

Problem Statement

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

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

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

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

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

3. Go back to step 1.

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

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

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

Constraints

2 \leq N \leq 10^5

1 \leq u,v \leq N

u \neq v

1 \leq A_i,B_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

5 4 1
1 2
2 3
3 4
3 5

Sample Output 1

2

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

Takahashi moves to Vertex 3.

Aoki moves to Vertex 2.

Takahashi moves to Vertex 5.

Aoki moves to Vertex 3.

Takahashi moves to Vertex 3.

Here, Aoki performs two moves.

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

Sample Input 2

5 4 5
1 2
1 3
1 4
1 5

Sample Output 2

1

Sample Input 3

2 1 2
1 2

Sample Output 3

0

Sample Input 4

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

Sample Output 4

5



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


Sample output:
2

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,U,V = map(int,readline().split())
m = map(int,read().split())
AB = zip(m,m)

graph = [[] for _ in range(N+1)]
for a,b in AB:
    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,DV = dfs(U),dfs(V)

answer = 0
for u,v in zip(DU[1:],DV[1:]):
    if u < v:
        x = v - 1
        if answer < x:
            answer = x

print(answer)

Submission status: Accepted

Solution code:
from collections import deque

N, u, v = map(int, input().split())
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  A, B = map(int, input().split())
  vec[A - 1].append(B - 1)
  vec[B - 1].append(A - 1)

du = [0] * N
pu = [-1] * N
q = [(u - 1, -1)]
while q :
  cur, pre = q.pop()
  for nex in vec[cur] :
    if nex != pre :
      du[nex] = du[cur] + 1
      pu[nex] = cur
      q.append((nex, cur))

dv = [0] * N
pv = [-1] * N
q = [(v - 1, -1)]
while q :
  cur, pre = q.pop()
  for nex in vec[cur] :
    if nex != pre :
      dv[nex] = dv[cur] + 1
      pv[nex] = cur
      q.append((nex, cur))

# du[u - 1] = 2
# dv[v - 1] = 2

ret = 0
for i, (u, v) in enumerate(zip(du, dv)) :
  if u < v or (u == v and pu[i] != pv[i]) :
    if u == v :
      ret = max(ret, u)
    else :
      ret = max(ret, v - 1)
print(ret)

Submission status: Accepted

Solution code:
import sys

n, u, v, *ab = map(int, sys.stdin.read().split())
graph = [[] for _ in range(n+1)]
for a, b in zip(*[iter(ab)] * 2):
    graph[a].append(b)
    graph[b].append(a)

def dfs(v):
    dist = [None] * (n + 1)
    dist[v] = 0
    stack = [v]
    while stack:
        x = stack.pop()
        for y in graph[x]:
            if dist[y] is None:
                dist[y] = dist[x] + 1
                stack.append(y)
    return dist

def main():
    dist_u = dfs(u)
    dist_v = dfs(v)

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

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(200000)

N, ko, oni = map(int, input().split())


class Node:
    def __init__(self):
        self.parent = -1
        self.child = []
        self.depth = -1

    def add_child(self, num):
        self.child.append(num)

    def set_parent(self, num):
        self.parent = num

    def set_depth(self, num):
        self.depth = num

    def children(self):
        for i in self.child:
            if i != self.parent:
                yield i


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


def get_most_deep(parent_node):
    ret = -1

    if len(node_list[parent_node].child) == 1:
        return node_list[parent_node].depth

    for child_node in node_list[parent_node].children():
        ret = max(ret, get_most_deep(child_node))

    return ret


for _ in range(N - 1):
    A, B = map(int, input().split())
    node_list[A].add_child(B)
    node_list[B].add_child(A)

q = deque()
q.append([oni, 0])

while len(q) > 0:
    val = q.pop()
    parent = val[0]
    gen = val[1]
    node_list[parent].set_depth(gen)
    for child in node_list[parent].children():
        q.append([child, gen + 1])
        node_list[child].set_parent(parent)

ko_gen = node_list[ko].depth
up_count = (ko_gen - 1) // 2

point = ko

for _ in range(up_count):
    point = node_list[point].parent

ans = 0
ans += get_most_deep(point) - ko_gen
ans += ko_gen - 1

print(ans)

Submission status: Accepted

Solution code:
import sys

n, u, v, *ab = map(int, sys.stdin.read().split())
ab = list(zip(*[iter(ab)] * 2))
graph = [[] for _ in range(n+1)]
for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)

def dfs(v):
    dist = [None] * (n + 1)
    dist[v] = 0
    stack = [v]
    while stack:
        x = stack.pop()
        for y in graph[x]:
            if dist[y] is None:
                dist[y] = dist[x] + 1
                stack.append(y)
    return dist

def main():
    dist_u = dfs(u)
    dist_v = dfs(v)

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

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

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


def dfs4t(a, par):
    for child in edge[a]:
        if child == par:
            continue
        else:
            cost4t[child] = cost4t[a] + 1
            dfs4t(child, a)
    return

def dfs4a(a, par):
    for child in edge[a]:
        if child == par:
            continue
        else:
            cost4a[child] = cost4a[a] + 1
            dfs4a(child, a)
    return


N, u, v = map(int, input().split())
edge = [[] for _ in range(N)]
cost4t = [10**5 for i in range(N)]
cost4a = [10**5 for i in range(N)]

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

u -= 1
v -= 1
cost4t[u] = 0
cost4a[v] = 0
dfs4t(u, 10**5)
dfs4a(v, 10**5)

ans = 0
for t, a, in zip(cost4t, cost4a):
    if a  >= t:
        ans = max(ans, t + a - (t + 1))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

vds = [-1]*n

qp = deque([])

qp.append(v-1)

vds[v-1] = 0

while qp:
    now = qp.pop()
    for nxt in neighbors[now]:
        if vds[nxt] == -1:
            qp.appendleft(nxt)
            vds[nxt] = vds[now] + 1

uds = [-1]*n
ucost = [-1]*n

qp.append(u-1)

uds[u-1] = 1
ucost[u-1] = 0

while qp:
    now = qp.pop()
    for nxt in neighbors[now]:
        if uds[nxt] == -1 and nxt != v-1:
            qp.appendleft(nxt)
            uds[nxt] = 1
            ucost[nxt] = ucost[now] + 1

ans = 0

for i in range(n):
    if uds[i] != -1 and ucost[i] <= vds[i] and ans < vds[i]:
        ans = vds[i]

            
print(ans-1)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
import heapq

g = defaultdict(list)
input = sys.stdin.buffer.readline
N,u,v= map(int,input().split())
for i in [0]*(N-1):
    A,B = map(int,input().split())
    g[A].append(B)
    g[B].append(A)

def dijkstra(start):
    inf = 10**10
    d = [inf]*(N+1)
    d[start] = 0
    que = []
    heapq.heappush(que,(start,0))
    while que:
        s, dist = heapq.heappop(que)
        if d[s] < dist:
            continue
        for t in g[s]:
            if d[t] > d[s] + 1:
                d[t] = d[s] + 1
                heapq.heappush(que,(t,d[t]))
    return d

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

Submission status: Accepted

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

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


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


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


def read_str_n():
    return list(map(str, input().split()))


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


def mt(f):
    import time

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

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

    return wrap


@mt
def slv(N, u, v, AB):
    ans = 0
    g = defaultdict(set)
    for a, b in AB:
        g[a].add(b)
        g[b].add(a)


    def f(start):
        s = [(start, 0)]
        d = {}
        d[start] = 0
        while s:
            c, l = s.pop()
            for n in g[c]:
                if n not in d:
                    s.append((n, l+1))
                    d[n] = l+1
        return d

    vd = f(v)
    t = u
    a = v
    s = [(t, 0)]
    d = {}
    d[t] = 0
    while s:
        u, l = s.pop()
        for v in g[u]:
            if v not in d and l + 1 < vd[v]:
                s.append((v, l+1))
                tmp = vd[v] - (l+1)
                tmp = (tmp//2) * 2
                d[v] = tmp + (l+1)

    d[t] = (vd[t] // 2) * 2
    dest = (0, -1)
    for k, v in d.items():
        dest = max(dest, (v, k))

    ans = dest[0]
    # error_print(dest)
    # error_print(d)
    # error_print(vd)
    if vd[dest[1]] == dest[0]:
        ans -= 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:
from collections import deque
import copy

n,u,v = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n-1)]
tree = [list() for i in range(n)]
depth = [0] * n
depth2 = [0] * n
already = [1] * n
already[v-1] = 0
q = deque([v-1])
for a,b in ab:
  a,b = a-1,b-1
  tree[a].append(b)
  tree[b].append(a)
d = 0
last = [0] * n
for key,i in enumerate(tree):
  if len(i) == 1:
    last[key] = 1
while True:
  q2 = deque()
  while q:
    now = q.popleft()
    depth[now] = d
    for i in tree[now]:
      if already[i]:
        q2.append(i)
        already[i] = 0
  if q2:
    q = copy.copy(q2)
    d += 1
  else:
    break
# print(depth)
q = deque([u-1])
d = 0
ans = 0
already = [1] * n
already[v-1] = 0
while True:
  q2 = deque()
  while q:
    now = q.popleft()
    if depth[now] == d:
      ans = max(ans,d)
      continue
    elif depth[now] < d:
      ans = max(ans,d-1)
      continue
    if last[now]:
      if depth[now] % 2 == d % 2:
        ans = max(ans,depth[now]-1)
      else:
        ans = max(ans,depth[now]-1)
    for i in tree[now]:
      if already[i]:
        q2.append(i)
        already[i] = 0
  if q2:
    q = copy.copy(q2)
    d += 1
  else:
    break
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
N, u, v = map(int, input().split())
es = dd(dict)
for _ in range(N-1):
    a, b = map(int, input().split())
    es[a-1][b-1] = es[b-1][a-1] = 1

d_ao = [None] * N
q = set([v-1])
dist = 0
dist_taka_ao = None
while q:
    nq = set()
    for node in q:
        d_ao[node] = dist
        if node == v-1:
            dist_taka_ao = dist
        for child in es[node].keys():
            if d_ao[child] is None:
                nq.add(child)
    dist += 1
    q = nq

d_taka = [None] * N
q = set([u-1])
dist = 0
ans = 0
while q:
    nq = set()
    for node in q:
        if d_ao[node] <= dist:
            continue
        d_taka[node] = dist
        ans = ans if ans > d_ao[node] else d_ao[node]
        for child in es[node].keys():
            if d_taka[child] is None:
                nq.add(child)
    dist += 1
    q = nq

#if dist_taka_ao % 2 == 1:
#    ans += 1
print(ans-1)

Submission status: Accepted

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

class LCA:
    def __init__(self,v,Edges,root=0):
        self.v=v
        self.Edges=Edges
        self.maxLog=18
        self.Parent=[[-1]*v for _ in range(self.maxLog+1)]
        self.Depth=[0]*v
        self.__bfs(root)
        for i in range(self.maxLog):
            for j in range(v):
                if self.Parent[i][j]!=-1:
                    self.Parent[i+1][j]=self.Parent[i][self.Parent[i][j]]
    def __bfs(self,root):
        Visited=[False]*self.v
        Visited[root]=True
        q=deque([root])
        while q:
            fr=q.pop()
            for to in self.Edges[fr]:
                if Visited[to]:
                    continue
                self.Parent[0][to]=fr
                self.Depth[to]=self.Depth[fr]+1
                Visited[to]=True
                q.append(to)
    def lca(self,a,b):
        if self.Depth[a]>self.Depth[b]:
            a,b=b,a
        for i in range(self.maxLog):
            if (self.Depth[b]-self.Depth[a])&(1<<i):
                b=self.Parent[i][b]
        if a==b:
            return b
        for i in reversed(range(self.maxLog-1)):
            if self.Parent[i][a]!=self.Parent[i][b]:
                a=self.Parent[i][a]
                b=self.Parent[i][b]
        return self.Parent[0][a]
    def dist(self,a,b):
        lca=self.lca(a,b)
        return self.Depth[a]+self.Depth[b]-2*self.Depth[lca]

def main():
    n,u,v=map(int,input().split())
    u-=1; v-=1
    Edges=[[] for _ in range(n)]
    for _ in range(n-1):
        x,y=map(lambda i: int(i)-1,input().split())
        Edges[x].append(y)
        Edges[y].append(x)
    L=[]
    for i in range(n):
        if len(Edges[i])==1:
            L.append(i)
    lca=LCA(n,Edges,v)
    ans=0
    for l in L:
        if lca.dist(u,l)>=lca.dist(v,l):
            continue
        ans=max(ans,lca.dist(v,l)-1)
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

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

from collections import deque

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

        def bfs(start):
            is_leaf = [0]*n
            que = deque()
            que.append((start, -1, 0))
            while que:
                c,p,d = que.pop()
                self.dep[c]=d
                self.par[0][c]=p
                cnt = 0
                for to in G[c]:
                    if to != p:
                        que.append((to,c,d+1))
                        cnt += 1
                if not cnt:
                    is_leaf[c] = 1
            return is_leaf

        self.is_leaf = bfs(start)

        for i in range(17):
            for j in range(self.n):
                self.par[i+1][j]=self.par[i][self.par[i][j]]

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

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

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

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

Submission status: Accepted

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

graph = [[] for _ in range(N)]
for Ai, Bi in AB:
    graph[Ai - 1].append(Bi - 1)
    graph[Bi - 1].append(Ai - 1)

import heapq

# tak table
d_tak = [10 ** 9 + 7] * N
p_tak = [None] * N
d_tak[u - 1] = 0
q = [(u - 1, 0)]
while len(q) > 0:
    src, pen = heapq.heappop(q)
    for dst in graph[src]:
        if d_tak[dst] > pen + 1:
            d_tak[dst] = pen + 1
            p_tak[dst] = src
            heapq.heappush(q, (dst, pen + 1))

# aok table
d_aok = [10 ** 9 + 7] * N
p_aok = [None] * N
d_aok[v - 1] = 0
q = [(v - 1, 0)]
while len(q) > 0:
    src, pen = heapq.heappop(q)
    for dst in graph[src]:
        if d_aok[dst] > pen + 1:
            d_aok[dst] = pen + 1
            p_aok[dst] = src
            heapq.heappush(q, (dst, pen + 1))

# where for tak to escape
i_ans = None
ans_tmp = 0
for i in range(N):
    if d_tak[i] < d_aok[i] and ans_tmp < d_aok[i]:
        ans_tmp = d_aok[i]
        i_ans = i

# where is aok when tak stops
pos_aok = i_ans
for j in range(d_aok[i_ans] - d_tak[i_ans]):
    pos_aok = p_aok[pos_aok]

# aok table 2
d_aok2 = [10 ** 9 + 7] * N
p_aok2 = [None] * N
d_aok2[v - 1] = 0
q = [(v - 1, 0)]
while len(q) > 0:
    src, pen = heapq.heappop(q)
    for dst in graph[src]:
        if d_aok2[dst] > pen + 1:
            d_aok2[dst] = pen + 1
            p_aok2[dst] = src
            heapq.heappush(q, (dst, pen + 1))

print(max(0, d_aok2[i_ans] - 1))

Submission status: Accepted

Solution code:
def main():
    n, u, v = map(int, raw_input().split())
    u -= 1
    v -= 1
    tree = {i: [] for i in xrange(n)}
    for _ in xrange(n - 1):
        a, b = map(int, raw_input().split())
        a -= 1
        b -= 1
        tree[a].append(b)
        tree[b].append(a)
    dist = [None] * n
    dist[v] = 0
    stack = [[v, 0]]
    while stack:
        node, d = stack.pop()
        d += 1
        for nex in tree[node]:
            if dist[nex] is None:
                dist[nex] = d
                stack.append([nex, d])
    
    stack = [[u, 0]]
    visited = [False] * n
    visited[u] = True
    best = 0
    while stack:
        node, d = stack.pop()
        d += 1
        for nex in tree[node]:
            if dist[nex] >= d and not visited[nex]:
                if dist[nex] > d:
                    stack.append([nex, d])
                visited[nex] = True
                if dist[nex] < dist[node]:
                    best = max(best, dist[node] - 1)
                else:
                    best = max(best, dist[node])
    print best


main()

Submission status: Accepted

Solution code:
import sys

n, u, v, *ab = map(int, sys.stdin.read().split())
ab = list(zip(*[iter(ab)] * 2))
graph = [[] for _ in range(n+1)]
for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)


def main():
    dist_u = [None] * (n + 1)
    dist_u[u] = 0
    stack = [u]

    while stack:
        x = stack.pop()
        for y in graph[x]:
            if dist_u[y] is None:
                dist_u[y] = dist_u[x] + 1
                stack.append(y)

    dist_v = [None] * (n + 1)
    dist_v[v] = 0
    stack = [v]
    contain_v = [False] * (n + 1)
    contain_v[v] = True
    while stack:
        x = stack.pop()
        for y in graph[x]:
            if dist_v[y] is None:
                dist_v[y] = dist_v[x] + 1
                stack.append(y)

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

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
def main():
    n, u, v = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    u -= 1
    v -= 1
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    da = [-1]*n
    dt = [-1]*n
    dt[u] = 0
    da[v] = 0
    q = [u]
    cnt = 0
    while q:
        cnt += 1
        qq = []
        for i in q:
            for j in g[i]:
                if dt[j] == -1:
                    dt[j] = cnt
                    qq.append(j)
        q = qq
    q = [v]
    cnt = 0
    while q:
        cnt += 1
        qq = []
        for i in q:
            for j in g[i]:
                if da[j] == -1:
                    da[j] = cnt
                    qq.append(j)
        q = qq
    #print(da, dt)
    priority = sorted([[i, j] for i, j in enumerate(da)], key=lambda x: -x[1])
    # print(priority)
    # path = {u}
    # now = u
    # for i in range(da[v]):
    #    for j in g[now]:
    #        if da[j] > da[now] and dt[j] < dt[now]:
    #            now = j
    #            path.add(now)
    #            break
    for i, j in priority:
        if da[i] > dt[i]:
            #print(da[i], dt[i])
            print(da[i]-1)
            return 0


main()

Submission status: Accepted

Solution code:
n, u, v = map(int,input().split())
edges = [[] for i in range(n)]


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


ha = [0 for i in range(n)]
def dfs(v):
    d= [0] * n
    q=[v]
    visited = [0] * n
    while q:
        v=q.pop()
        visited[v] = 1
        visited.append(v)
        c = True
        for i in edges[v]:
            if not visited[i]:
                d[i] = d[v] + 1
                q.append(i)
                c = False
        if c:
            ha[v] = 1
    return d,ha

df_nige , ha= dfs(u-1)
df_oi ,ha =dfs(v-1)

moku = -1
dfsa_mo = []
for i in range(n):
    kos =  df_oi[i] - df_nige[i] 
    dfsa_mo.append(kos)

#print(dfsa_mo)

ako = []

for i in range(n):
    dfsa = dfsa_mo[i]
    moku = i
    if dfsa > 0 and ha[i] == 1:
        if dfsa%2 == 0:
            if dfsa > 3:
                ans = df_nige[moku] + dfsa - 2 + 1
            elif dfsa == 2:
                ans = df_nige[moku] + 1
            else:
                ans = df_nige[moku]
        else:
            if dfsa == 1:
                ans = df_nige[moku]
            else:
                ans = df_nige[moku] + dfsa - 3 + 2
        #print(ans)
        ako.append(ans)

    else:
        ako.append(-1)

#print(ako)
gege = max(ako)
print(gege)

Submission status: Accepted

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

class LCA:
    def __init__(self,v,Edges,root=0):
        self.v=v
        self.Edges=Edges
        self.maxLog=18
        self.Parent=[[-1]*v for _ in range(self.maxLog+1)]
        self.Depth=[0]*v
        self.__bfs(root)
        for i in range(self.maxLog):
            for j in range(v):
                if self.Parent[i][j]!=-1:
                    self.Parent[i+1][j]=self.Parent[i][self.Parent[i][j]]
    def __bfs(self,root):
        Visited=[False]*self.v
        Visited[root]=True
        q=deque([root])
        while q:
            fr=q.pop()
            for to in self.Edges[fr]:
                if Visited[to]:
                    continue
                self.Parent[0][to]=fr
                self.Depth[to]=self.Depth[fr]+1
                Visited[to]=True
                q.append(to)
    def lca(self,a,b):
        if self.Depth[a]>self.Depth[b]:
            a,b=b,a
        for i in range(self.maxLog):
            if (self.Depth[b]-self.Depth[a])&(1<<i):
                b=self.Parent[i][b]
        if a==b:
            return b
        for i in reversed(range(self.maxLog-1)):
            if self.Parent[i][a]!=self.Parent[i][b]:
                a=self.Parent[i][a]
                b=self.Parent[i][b]
        return self.Parent[0][a]
    def dist(self,a,b):
        lca=self.lca(a,b)
        return self.Depth[a]+self.Depth[b]-2*self.Depth[lca]

def main():
    n,u,v=map(int,input().split())
    u-=1; v-=1
    Edges=[[] for _ in range(n)]
    for _ in range(n-1):
        x,y=map(lambda i: int(i)-1,input().split())
        Edges[x].append(y)
        Edges[y].append(x)
    L=[]
    for i in range(n):
        if len(Edges[i])==1:
            L.append(i)
    lca=LCA(n,Edges,v)
    dist=lca.dist(u,v)
    ans=dist//2
    for l in L:
        m=lca.lca(u,l)
        if lca.dist(u,m)>=lca.dist(v,m):
            continue
        d_u=lca.dist(u,l)
        d_v=lca.dist(v,l)
        d=d_v-d_u
        cnt=d-1
        ans=max(ans,d_u+cnt)
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque


def solve(n, u, v, edge_list):
    # graph
    g = [[] for i in range(n)]
    for a, b in edge_list:
        g[a].append(b)
        g[b].append(a)

    # root at v
    parent = [0] * n
    depth = [0] * n
    parent[v] = -1
    queue = deque([v])
    while len(queue) > 0:
        p = queue.popleft()
        for q in g[p]:
            if parent[p] != q:
                parent[q] = p
                depth[q] = depth[p] + 1
                queue.append(q)

    # collect max_depth from leaf
    temp_list = [[i, -depth[i]] for i in range(n)]
    temp_list = list(sorted(temp_list, key=lambda x: x[1]))
    run_list = [temp_list[i][0] for i in range(n)]
    max_children_depth = depth.copy()
    for i in run_list[:-1]:
        max_children_depth[parent[i]] = max(max_children_depth[parent[i]], max_children_depth[i])
    # print(depth)
    # print(max_children_depth)
    du = depth[u]
    up = u
    res = 0
    if du > 2:
        for _ in range((du - 1) // 2):
            up = parent[up]
            res += 1
    res += max_children_depth[up] - depth[up]
    if du % 2 == 0:
        res += 1
    return res


def main():
    n, u, v = map(int, input().split())
    edge_list = [[0, 0] for _ in range(n - 1)]
    for i in range(n - 1):
        a, b = map(int, input().split())
        edge_list[i][0] = a - 1
        edge_list[i][1] = b - 1
    u -= 1
    v -= 1
    res = solve(n, u, v, edge_list)
    print(res)


def test():
    assert solve(5, 3, 0, [[0, 1], [1, 2], [2, 3], [2, 4]]) == 2
    assert solve(5, 3, 4, [[0, 1], [0, 2], [0, 3], [0, 4]]) == 1
    assert solve(2, 0, 1, [[0, 1]]) == 0


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)


def dfs(cur, par, g, d):
    pars[cur] = par
    for to in g[cur]:
        if to == par:
            continue
        d[to] = d[cur]+1
        md[cur] = max(md[cur], dfs(to, cur, g, d)+1)
    return md[cur]


n, u, v = map(int, input().split())
u -= 1
v -= 1
g = []
for i in range(n):
    g.append([])
for i in range(n-1):
    a, b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
d = []
md = []
pars = []
f = []
for i in range(n):
    d.append(-1)
    md.append(0)
    pars.append(-1)
    f.append(False)
d[u] = 0
dfs(u, -1, g, d)
cur = v
while cur != u:
    f[cur] = True
    cur = pars[cur]
f[u] = True
res = d[v]-1
for i in range(n):
    if f[i] and d[i]*2 < d[v]:
        for to in g[i]:
            if to == pars[i] or f[to]:
                continue
            res = max(res, md[to]+1+d[v]-d[i] - 1)
print(res)

Submission status: Accepted

Solution code:
import sys
n,u,v=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n-1)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)

def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

x=bfs(u-1)
y=bfs(v-1)
ans=[]
e=[]
ct0=0
for i in range(n):
  if x[i]<y[i] and x[i]!=0:
    ct0+=1
if ct0==0:
  if x[v-1]==1:
    print(0)
  else:
    print(1)
  sys.exit()
for i in range(n):
  if x[i]<y[i]:
    if abs(x[i]-y[i])%2==0:
      if x[i]%2==1:
        ans.append(y[i]-1)
      else:
        ans.append(y[i]-1)
    else:
      ans.append(y[i]-1)
print(max(ans))

Submission status: Accepted

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

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

dist_r = [0] * n
dist_t = [0] * n

def dfs(v, p, dist):
    dist_r[v] = dist
    ret = 0
    for nv in g[v]:
        if nv == p: continue
        ret = max(ret, dfs(nv, v, dist+1))
    dist_t[v] = ret
    return ret + 1

dfs(A, -1, 0)

init_dist = dist_r[T]
v = T
d1 = 0
d2 = init_dist
while init_dist - dist_r[v] < dist_r[v]:
    if d1 < dist_t[v]:
        d1 = dist_t[v]
        d2 = dist_r[v]
    for nv in g[v]:
        if dist_r[v] > dist_r[nv]:
            v = nv
            break

print(d1+d2-1)