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


n,u,v = [int(_) for _ in input().split()]
dic = {}
for i in range(n-1):
    a,b = [int(_) for _ in input().split()]
    if a in dic:
        dic[a].append(b)
    else:
        dic[a] = [b]
    if b in dic:
        dic[b].append(a)
    else:
        dic[b] = [a]
# print(dic)
que = []
seen = {}
dic2 = {}
way = {}
ans_l = []
for i in range(1,n+1):
    seen[i] = 0
    dic2[i] = 0
    way[i] = 0
# print(seen)
que.append(v)
seen[v] = 1
while len(que) != 0:
    tem_v = que.pop()
    d = dic2[tem_v]
    if len(dic[tem_v]) == 1 and seen[dic[tem_v][0]] == 1:
        ans_l.append((tem_v, d))
        # print(tem_v, dic[tem_v])
    for node in dic[tem_v]:
        if seen[node] == 0:
            que.append(node)
            seen[node] = 1
            dic2[node] = d + 1
# print(dic2)
# print(seen)
ans_l = sorted(ans_l, reverse=True, key=lambda x: x[1])
# print(ans_l)
d_taka = dic2[u]
# print(d_taka)
que.append(u)
way[u] = 1
while len(que) != 0:
    tem_u = que.pop()
    d = dic2[tem_u]
    for node in dic[tem_u]:
        if dic2[node] < d:
            que.append(node)
            way[node] = 1
# print(way)
for i in range(len(ans_l)):
    node, tem_d = ans_l[i]
    que.append(node)
    while len(que) != 0:
        tem_u = que.pop()
        d = dic2[tem_u]
        if way[tem_u] == 1:
            ans = tem_u
        else:
            for node2 in dic[tem_u]:
                if way[node2] == 1:
                    ans = node2
                if dic2[node2] < d and way[node2] == 0:
                    que.append(node2)
    # print('ans', ans)
    if dic2[ans] * 2 > d_taka:
        print(tem_d - 1)
        sys.exit()

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())
data = list(zip(m,m))

graph = [[] for _ in range(n+1)]
for a,b in data:
    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
res = 0
du, dv = dfs(u), dfs(v)
for i in range(1, n+1):
    dvi = dv[i]
    if du[i] <= dvi:
        if dvi > res:
            res = dvi
print(res - 1)

Submission status: Accepted

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

u -= 1
v -= 1

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

def calcDepth(root):
  depth = [-1] * N
  stack = [(root, 0)]

  while stack:
    cur, curD = stack.pop()
    depth[cur] = curD
    for c in edge[cur]:
      if depth[c] != -1: continue
      stack.append((c, curD+1))
  
  return depth

Adepth = calcDepth(v)
Ddepth = calcDepth(u)

ans = 0
for i in range(N):
  if Adepth[i] >= Ddepth[i]:
    ans = max(ans, Adepth[i])
print(ans-1)

Submission status: Accepted

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

n, u, v = map(int, readline().split())
m = map(int,read().split())
data = list(zip(m,m))

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

for a,b in data:
    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
res = 0
du, dv = dfs(u), dfs(v)
for i in range(1, n+1):
    dvi = dv[i]
    if du[i] <= dvi:
        if dvi > res:
            res = dvi
print(res - 1)

Submission status: Accepted

Solution code:
import sys
import queue
from collections import defaultdict

input = sys.stdin.readline
sys.setrecursionlimit(20000000)

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

path_u = [0] * n
path_v = [0] * n

# u
checked = [False] * n
checked[u] = True
q = queue.Queue()
q.put((u, 0))
while not q.empty():
    cur, count = q.get()
    path_u[cur] = count
    for i in ab[cur]:
        if not checked[i]:
            q.put((i, count+1))
            checked[i] = True

# v
checked = [False] * n
checked[v] = True
q = queue.Queue()
q.put((v, 0))
while not q.empty():
    cur, count = q.get()
    path_v[cur] = count
    for i in ab[cur]:
        if not checked[i]:
            q.put((i, count+1))
            checked[i] = True

ans = 0
for u_, v_ in zip(path_u, path_v):
    if u_ < v_:
        ans = max(ans, v_ - 1)
# print(path_u, path_v)
print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
#import numpy as np
from collections import deque



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

	q = deque()
	a = [None] * (n + 1)
	b=[None] * (n + 1)
	q=[(u,0)]
	while q:
		now,cnt= q.pop()
		a[now]=cnt
		b[cnt]=now
		if now==v:
			za=b[(cnt-1)//2]
			ccnt=cnt
		for r in A[now]:
			if a[r] == None:
				q.append((r,cnt+1))
			else:
				continue
	
	q = deque()
	c = [None] * (n + 1)
	q=[(za,0)]
	while q:
		now,cnt= q.pop()
		c[now]=cnt
		for r in A[now]:
			if c[r] == None:
				q.append((r,cnt+1))
			else:
				continue
	
	
	zza=za
	q = deque()
	q = [v]
	while q:
		now=q.pop()
		if now==za:
			A[za]=[]
		c[now]=0
		for i in A[now]:
			if c[i]!=0:
				q.append(i)
			else:
				continue
				
	syoki=a[zza]
	
	ans=syoki+max(c[1:])
	if ccnt%2==0:
		ans+=1
	print(ans)
	
	



	
if __name__ == "__main__":
	main()

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)]
oks = set()

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[:]
                    continue
                dps[u] = dps[v] + 1
                oks.add(u)
                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 u not in oks:
                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)

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

Submission status: Accepted

Solution code:
class Tree:
    def __init__(self, N):
        self.N = N # #vertices
        self.D = (self.N-1).bit_length() # #iterations in doubling
        self.E = [{} for _ in range(N)]
    
    def add_edge(self, init, end, weight, undirected=False):
        self.E[init][end] = weight
        if undirected: self.E[end][init] = weight
    
    def dfs(self, root):
        # parents[v]: the parent of the vertex v
        # depth[v]: the depth of the vertex v from the root
        # dist[v]: the distance of the vertex v from the root.
        self.parent = [None] * self.N
        self.depth = [None] * self.N
        self.dist = [float('inf')] * self.N
        self.parent[root] = -1; self.depth[root] = 0; self.dist[root] = 0;
        stack = [root]
        while stack:
            v = stack.pop()
            for u, d in self.E[v].items():
                if self.depth[u] is not None: continue
                self.parent[u] = v
                self.depth[u] = self.depth[v] + 1
                self.dist[u] = self.dist[v] + d
                stack.append(u)

N, u, v = map(int, input().split())
tr = Tree(N)
for _ in range(N-1):
    a, b = map(int, input().split())
    tr.add_edge(a-1, b-1, 1, undirected=True)
tr.dfs(v-1)
dist_v = tr.dist
tr.dfs(u-1)
dist_u = tr.dist
ans = 0
for du, dv in zip(dist_u, dist_v):
    if du < dv:
        ans = max(ans, dv - 1)
print(ans)

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, u, v = list(map(int, readline().split()))
    tmd = collections.defaultdict(list)
    for i in range(n-1):
        tma, tmb = list(map(int, readline().split()))
        tmd[tma-1] += [tmb-1]
        tmd[tmb-1] += [tma-1]

    qlt = [[0, u-1]]
    qlt = collections.deque(qlt)
    fqt = collections.defaultdict(int)
    fqt[u-1]
    while True:
        if len(qlt) != 0:
            cost, tmp = qlt.popleft()
            for tmv in tmd[tmp]:
                if tmv not in fqt:
                    qlt.append([cost + 1, tmv])
                    fqt[tmv] = cost + 1
        else:
            break

    qla = [[0, v-1]]
    qla = collections.deque(qla)
    fqa = collections.defaultdict(int)
    fqa[v-1]
    while True:
        if len(qla) != 0:
            cost, tmp = qla.popleft()
            for tmv in tmd[tmp]:
                if tmv not in fqa:
                    qla.append([cost + 1, tmv])
                    fqa[tmv] = cost + 1
        else:
            break
    mt = 0
    for kt, vt in sorted(fqt.items(), key=lambda x: x[1], reverse=True):
        if vt < fqa[kt]:
            mt = max(mt, fqa[kt])
    print(mt - 1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

n, u, v = [int(i) for i in sys.stdin.readline().split()]
u -= 1
v -= 1
graph = {i: [] for i in range(n)}
for i in range(n - 1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

distance = 0
stack = [(u, 0)]
already = set()
parent = [i for i in range(n)]
while len(stack) > 0:
    cur, dis = stack.pop(-1)
    already.add(cur)
    for _next in graph[cur]:
        if _next in already:
            continue
        parent[_next] = cur
        if _next == v:
            distance = dis + 1
            break
        stack.append((_next, dis + 1))
cur = v
path = []
while cur != u:
    path.append(cur)
    cur = parent[cur]

path_dict = {j: i for i, j in enumerate(path)}
already = set()
ls = []
stack = [(u, 0, 0)]
while len(stack) > 0:
    ind, cur_dis, minus = stack.pop(-1)
    already.add(ind)
    ls.append(cur_dis - minus)
    for _next in graph[ind]:
        parent[_next] = ind
        if _next in already:
            continue
        if _next in path:
            if path_dict[_next] <= cur_dis + 1:
                continue
            else:
                stack.append((_next, cur_dis + 1, minus + 2))
        else:
            stack.append((_next, cur_dis + 1, minus))

res = max(ls)

if res == 0:
    print(distance - 1)
else:
    print(distance + res - 1)

Submission status: Accepted

Solution code:
from collections import deque
def main():
    N, u, v = [int(i) for i in input().split()]
    u -= 1
    v -= 1
    graph = [[] for _ in range(N)]
    for i in range(N-1):
        a,b = [int(i) for i in input().split()]
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)
    atree, aparents, adistances = maketree(v, graph, N)
    ttree, tparents, tdistances = maketree(u, graph, N)
    res = 0
    # print(adistances)
    # print(tdistances)
    for i in range(N):
        a = adistances[i]
        t = tdistances[i]
        if(a > t):
            res = max(res, a - 1)
    print(res)

def maketree(v, graph, N):
    tree = [[] for _ in range(N)]
    parents = [-1] * N
    distances = [0]*N
    
    stack = deque([(v, -1, 0)])
    while len(stack) > 0:
        current, parent, distance = stack.pop()
        distances[current] = distance
        parents[current] = parent
        for n in graph[current]:
            if parent == n:
                continue
            stack.append((n, current, distance+1))
            tree[current].append(n)
    return tree, parents, distances
    
main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5+1)

def cur(p):
    for i in x[p]:
        if rank[i]==-1:
            rank[i]=rank[p]+1
            par[i]=p
            cur(i)

def cur2(p):
    if spar[p]==-1:
        spar[p]=cur2(par[p])
    return spar[p]




n,u,v=map(int,input().split())
u,v=u-1,v-1
x=[[] for i in range(n)]

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

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

cur(u)

spar=[-1 for i in range(n)]
i=v
while i!=u:
    spar[i]=i
    i=par[i]
spar[u]=u


for p in range(n):
    cur2(p)

ans=rank[v]-1
for i in range(n):
    z=rank[v]-rank[spar[i]]*2
    if z>0:
        ans=max(ans,rank[i]+z-1)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
INF = 10 ** 9 + 7

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

edges = [[] for _ in range(N)]
for x, y in X:
    edges[x - 1].append(y - 1)
    edges[y - 1].append(x - 1)
    
def bfs(s):
    d = [INF] * N
    d[s] = 0

    visited = [False] * N
    visited[s] = True
    
    q = deque()
    q.append(s)
    
    while q:
        u = q.popleft()
        for v in edges[u]:
            if visited[v]:
                continue
            
            visited[v] = True
            d[v] = d[u] + 1
            q.append(v)
            
    return d

ans = 0
for x, y in zip(bfs(u - 1), bfs(v - 1)):
    if x <= y:
        ans = max(ans, y - 1)
        
print(ans)

Submission status: Accepted

Solution code:
N,u,v = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N-1)]
import numpy as np
x = [[] for _ in range(N)]
for ab in AB:
  a = ab[0]
  b = ab[1]
  x[a-1].append(b-1)
  x[b-1].append(a-1)
  
flag1 = [False]*N
flag2 = [False]*N
length1 = [0]*N
length2 = [0]*N
go = [v-1]
while go!=[]:
  a = go.pop()
  if flag1[a]:
    continue
  else:
    flag1[a]=True
    for i in x[a]:
      if flag1[i]:
        continue
      else:
        length1[i]=length1[a]+1
        go.append(i)

go = [u-1]
while go!=[]:
  a = go.pop()
  if flag2[a]:
    continue
  else:
    flag2[a]=True
    for i in x[a]:
      if flag2[i]:
        continue
      else:
        length2[i]=length2[a]+1
        go.append(i)
        
length1 = np.array(length1)
length2 = np.array(length2)
print(max(length1[length1>length2])-1)

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np


def bfs(N, u, path):
    d = [-1] * N
    d[u-1] = 0
    q = deque([])
    q.append(u-1)

    while(len(q) != 0):
        p = q.popleft()

        rs = path[p]

        for r in rs:
            if d[r] == -1:
                d[r] = d[p] + 1
                q.append(r)

    return d


def bfs2(N, u, path, d):
    e = [-1] * N
    e[u-1] = 0
    q = deque([])
    q.append(u-1)
    far_p = u-1

    while(len(q) != 0):
        p = q.popleft()

        if (d[p] - e[p]) >= 1:
            rs = path[p]

            is_end = len(rs)
            for r in rs:
                if e[r] == -1:
                    e[r] = e[p] + 1
                    q.append(r)
                else:
                    is_end -= 1

            if is_end == 0:
                if d[p] >= d[far_p]:
                    far_p = p

    return e, far_p


N, u, v = map(int, input().split())
path = [[] * N for i in range(N)]

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

d = bfs(N, v, path)
e, far_p = bfs2(N, u, path, d)

print(d[far_p]-1)

Submission status: Accepted

Solution code:
from collections import deque

di_lst = []
N, U, V = map(int, input().split())
edges = {tuple(map(int, input().split())) for i in range(N - 1)}

stack = deque()


def BFS(X, edges, N):
    roots = [set() for _ in range(N + 1)]
    for a, b in edges:
        roots[a].add(b)
        roots[b].add(a)
    dist = {}
    stack = deque()
    stack.append(X)
    dist[X] = 0
    while stack:
        parent = stack.pop()
        for child in roots[parent]:
            if not child in dist:
                dist[child] = dist[parent] + 1
                stack.append(child)
    return dist


U_dist = BFS(U, edges, N)
V_dist = BFS(V, edges, N)

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

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=[]
for i in range(n):
  if x[i]<y[i]:
    ans.append(y[i]-1)
print(max(ans))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)
def input():
    return sys.stdin.readline()[:-1]
N,u,v = map(int,input().split(' '))
l = [None]*N
for i in range(N-1):
    l[i] = list(map(int, input().split()))

MAP = {}
for i in range(N):
    if l[i]==None:
        continue
    a,b = l[i]
    if a in MAP:
        MAP[a].append(b)
    else:
        MAP[a] = [b]
    if b in MAP:
        MAP[b].append(a)
    else:
        MAP[b] = [a]

#Tがたどり着くのにかかる手数
t_MAP = [0]*(N+1)
cost = 0

def t_dfs(n,c):
    t_MAP[n] = c
    c += 1
    if n in MAP:
        for j in MAP[n]:
            if t_MAP[j]==0 and j!=u:
                t_dfs(j,c)
t_dfs(u,cost)

a_visited = [False]*(N+1)
break_even = False
pre_tcost = 10**5
ANS = [0]
def a_dfs(n,c,pre_c):
    a_visited[n] = True
    t_cost = t_MAP[n]
    if t_cost>c:
        if t_cost>pre_c:
            return
    ANS[0] = max(c,ANS[0])
    c += 1
    if n in MAP:
        for j in MAP[n]:
            if not a_visited[j]:
                a_dfs(j,c,t_cost)
a_visited[v] = True
a_dfs(v,cost,pre_tcost)
print(ANS[0]-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

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

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

memo = [[0, 0] for i in range(n)]

def dfs(cur, pre, p):
    stack = deque([[cur, pre]])
    while stack:
        cur, pre = stack.pop()
        if pre != -1:
            memo[cur][p] = memo[pre][p] + 1
        for e in E[cur]:
            if e != pre:
                stack.append([e, cur])

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

# print(memo)
ans = 0
for a, b in memo:
    if a <= b:
        ans = max(ans, b - 1)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
import math
from collections import deque, defaultdict
import heapq
INF = float("inf")


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)
        pass

    def add_edge(self, from_, to_, weight=1):
        self.E[from_].append((to_, weight))
        self.E[to_].append((from_, weight))


INF = float("inf")


def solve(N: int, u: int, v: int, A: "List[int]", B: "List[int]"):
    g = Graph(N)
    for a, b in zip(A, B):
        g.add_edge(a-1, b-1)

    ddhouse = [0]*N

    def dfs(f_, pre, dep):
        ddhouse[f_] = dep

        for t_, w in g.E[f_]:
            if t_ == pre:
                continue
            dfs(t_, f_, dep+1)
        return

    dfs(v-1, -1, 0)

    ffhouse = [0]*N

    def dfs(f_, pre, dep):
        ffhouse[f_] = dep

        for t_, w in g.E[f_]:
            if t_ == pre:
                continue
            dfs(t_, f_, dep+1)
        return

    dfs(u-1, -1, 0)
    m = 0
    for d, f in zip(ddhouse, ffhouse):
        if f >= d:
            continue
        else:
            m = max(d, m)
    print(max(m-1, 0))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    u = int(next(tokens))  # type: int
    v = int(next(tokens))  # type: int
    A = [int()] * (N - 1)  # type: "List[int]"
    B = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, u, v, A, B)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

N, u, v = map(int, input().split())
u -= 1
v -= 1
adj = defaultdict(list)
for i in range(N - 1):
    Ai, Bi = map(lambda x: int(x) - 1, input().split())
    adj[Ai].append(Bi)
    adj[Bi].append(Ai)

A = [0] * N
stack = deque()
stack.append(v)
while len(stack) > 0:
    e = stack.popleft()
    for a in adj[e]:
        if a == v or A[a] != 0:
            continue
        A[a] = A[e] + 1
        stack.append(a)

T = [0] * N
stack = deque()
stack.append(u)
while len(stack) > 0:
    e = stack.popleft()
    for a in adj[e]:
        if a == u or T[a] != 0 or A[a] < T[e] + 1:
            continue
        T[a] = T[e] + 1
        stack.append(a)

print(max([A[i] for i in range(N) if T[i] != 0 or i == u]) - 1)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,s,t = LI()
    s -= 1
    t -= 1
    v = [[] for i in range(n)]
    f = [0]*n
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
        f[a] += 1
        f[b] += 1
    l = []
    for i in range(n):
        if f[i] == 1:
            l.append(i)
    depth = [-1]*n
    depth[t] = 0
    q = deque([t])
    while q:
        x = q.popleft()
        for y in v[x]:
            if depth[y] < 0:
                depth[y] = depth[x]+1
                q.append(y)
    d = [-1]*n
    d[s] = 0
    q = deque([s])
    while q:
        x = q.popleft()
        for y in v[x]:
            if d[y] < 0:
                d[y] = d[x]+1
                q.append(y)
    l.sort(key = lambda x:-depth[x])
    for i in l:
        if d[i] < depth[i]:
            break
    print(depth[i]-1)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N,u,v = II()
A,B = Line(N-1,2)

def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if directed==False:
            pt[t[i]-1].append(s[i]-1)
    return pt

def bfs(pt,v):
    n = len(pt)
    d = [-1]*n
    d[v] = 0
    q = [v]
    c = 1
    while q:
        q1 = []
        for i in q:
            for j in pt[i]:
                if d[j]==-1:
                    d[j] = c
                    q1.append(j)
        q = q1
        c += 1
    return d

pt = edges_to_pt(A,B,N)
du = bfs(pt,u-1)
dv = bfs(pt,v-1)

ans = 0
for i in range(N):
    if du[i]>=dv[i]:
        continue
    elif len(pt[i])>=2:
        continue
    else:
        ans = max(ans,dv[i]-1)

print(ans)

Submission status: Accepted

Solution code:
import math
import sys

m=10**9 + 7 
sys.setrecursionlimit(1000010)
(N, u, v ) = list(map(int,input().split()))
A=[]
B=[]
D=[] 
INF = 10 ** 10

for i in range(0,N-1):
    (a, b) =  list(map(int,input().split()))
    A.append(a)
    B.append(b)
    
C=[[] for _ in range(N)]
# print(N,u,v, A, B, C) 

for i in range(0,N-1):
    # print(i,A[i],B[i])
    C[A[i]-1].append(B[i])
    C[B[i]-1].append(A[i])

def initD():
    global D
    D=[INF for _ in range(N)]
    
def dist(n):
    global D
    initD()
    D[n-1] = 0 
    for x in C[n-1]:
        # print("x1:",x)
        if D[x-1] == INF:
            distR(x,1)
    
def distR(n,d):
    global D
    D[n-1] = d
    for x in C[n-1]:
        if D[x-1] == INF:
            # print("x1,x2:",n,x)
            distR(x,d+1)


# print(N,u,v, A, B, C) 
dist(u)
U = D 
dist(v)
V = D
# print(U,V)

max = 0

for i in range(0,N):
    if U[i] < V[i]:
        if (V[i] - U[i]) % 2 ==0:
            x = V[i] - 1
        else:
            x = V[i] - 1
    
        if x > max:
            max = x
 
print(max)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import copy
N,u,v=map(int,input().split())
l=[set()for i in range(N)]
info=[[-1,-1,-1,-1]for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    l[a-1].add(b-1)
    l[b-1].add(a-1)
terminal=set()

s={u-1}
info[u-1][0]=0
info[u-1][1]=0
k=1
while len(s)>0:
    new_s=set()
    for t in s:
        for t2 in l[t]:
            if info[t2][0]==-1:
                info[t2][0]=t
                info[t2][1]=k
                new_s.add(t2)
    s=new_s
    k+=1

s={v-1}
info[v-1][2]=0
info[v-1][3]=0
k=1
while len(s)>0:
    new_s=set()
    for t in s:
        for t2 in l[t]:
            if  info[t2][2]==-1:
                info[t2][2]=t
                info[t2][3]=k
                new_s.add(t2)
    s=new_s
    k+=1
ans=-1
d=0
for i in range(N):
    if not len(l[i])==1:continue
    if info[i][1]<info[i][3]:
        if d<info[i][3]:
            d=info[i][3]
print(d-1)

Submission status: Accepted

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


def main():
    n, u, v = map(int, input().split())
    u -= 1
    v -= 1
    connect = [[] for _ in range(n)]

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

    # 頂点xから見た全頂点の深度リストを取りたい
    def dfs(list, now, prev=-1, depth=0):
        list[now] = depth
        kids = connect[now]
        for kid in kids:
            if kid == prev:
                continue
            dfs(list, kid, now, depth+1)

    list_v, list_u = [None]*n, [None]*n

    dfs(list_v, v)
    dfs(list_u, u)

    tmp_list = [(depth, index) for index, depth in enumerate(list_v)]
    sorted_v = sorted(tmp_list, reverse=True)
    ans = -1

    for depth, index in sorted_v:
        if list_u[index] < depth:
            ans = depth-1
            break

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

class Tree:
  C, RL = {}, {}
  R, N, D, S, P = None, None, None, None, None
  def __init__(s, num):
    s.N = num
  def setC(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def makeRank(s, root):
    s.R = [0] * s.N
    s.R[root] = 1
    s.RL[1] = [root]
    s.S = {}
    s.P = {}
    F = [root]
    s.D = 2
    while F != []:
      Ft = []
      s.RL[s.D] = []
      for i in F:
        for j in s.C[i]:
          if s.R[j] == 0:
            s.R[j] = s.D
            Ft.append(j)
            s.RL[s.D].append(j)
            if i not in s.S:
              s.S[i] = [j]
            else:
              s.S[i].append(j)
            s.P[j] = i

      s.D += 1
      F = Ft
  def getDeep(s, x):
    ans = 0
    if x in s.S:
      for i in s.S[x]:
        ans = max(ans, s.getDeep(i))
      return ans + 1
    else:
      return 0
  def getParent(s, x, n):
    if n == 0:
      return x
    return s.getParent(s.P[x], n - 1)
    

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

T = Tree(N)
for a, b in AB:
  T.setC(a - 1, b - 1)

T.makeRank(v - 1)
t = (T.R[u - 1] // 2) - 1
f = T.R[u - 1] % 2
k = T.getDeep(T.getParent(u - 1, t))
print(t + k + f)