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: Runtime Error

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

dist=[[-1, -1] for _ in range(n)]
dist[v][0]=0
dist[u][1]=0
 
def dfs(graph,v,k):
    ver=graph[v]
    for vers in ver:
        if dist[vers][k]==-1:
            dist[vers][k]=dist[v][k]+1
            dfs(graph,vers,k)
 
 
dfs(graph,v,0)
dfs(graph,u,1)
dist.sort(reverse=True)
 
for i in range(10**6):
    if dist[i][0]-dist[i][1]>=1:
        print(dist[i][0]-1)
        break

Submission status: Runtime Error

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+1)]
for vs in ab:
    graph[vs[0]].append(vs[1])
    graph[vs[1]].append(vs[0])

depth=[[-1,-1] for _ in range(n+1)]
depth[v][0]=0
depth[v][1]=0

def dfs1(graph,v):
    vv=graph[v]
    for vvv in vv:
        if depth[vvv][0]==-1:
            depth[vvv][0]=depth[v][0]+1
            dfs1(graph,vvv)

def dfs2(graph,v):
    vv=graph[v]
    for vvv in vv:
        if depth[vvv][1]==-1:
            depth[vvv][1]=depth[v][1]+1
            dfs2(graph,vvv)

dfs1(graph,v)
dfs2(graph,u)
depth=sorted(depth,reverse=True)

for i in range(10**6):
    if depth[i][0]-depth[i][1]>=1:
        print(depth[i][0]-1)
        break

Submission status: Runtime Error

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+1)]
for vs in ab:
    graph[vs[0]].append(vs[1])
    graph[vs[1]].append(vs[0])

depth=[[-1,-1] for _ in range(n+1)]
depth[v][0]=0
depth[v][1]=0

def dfs1(graph,v):
    vv=graph[v]
    for vvv in vv:
        if depth[vvv][0]==-1:
            depth[vvv][0]=depth[v][0]+1
            dfs1(graph,vvv)

def dfs2(graph,v):
    vv=graph[v]
    for vvv in vv:
        if depth[vvv][1]==-1:
            depth[vvv][1]=depth[v][1]+1
            dfs2(graph,vvv)

dfs1(graph,v)
dfs2(graph,u)
depth=sorted(depth,reverse=True)

for i in range(10**5):
    if depth[i][0]-depth[i][1]>=1:
        print(depth[i][0]-1)
        break

Submission status: Runtime Error

Solution code:
n,u,v = map(int,input().split())
u -= 1
v -= 1
G = [[] for _ 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 = [-1]*n
dist[v] = 0
prev = [-1]*n
def dfs(now):
    for nxt in G[now]:
        if dist[nxt] != -1: continue
        dist[nxt] = dist[now]+1
        prev[nxt] = now
        dfs(nxt)
dfs(v)

color = [0]*n
now = u
while now >= 0:
    color[now] = 1
    now = prev[now]

def dfs2(now,prev,dist,cnt):
    if dist == 0: return cnt
    if dist == -1: return cnt-1
    if G[now] == [prev]: return cnt+dist-1
    res = 0
    for nxt in G[now]:
        if nxt == prev: continue
        if color[nxt]: res = max(res,dfs2(nxt,now,dist-2,cnt+1))
        else: res = max(res,dfs2(nxt,now,dist,cnt+1))
    return res

print(dfs2(u,-1,dist[u]-dist[v],0))

Submission status: Runtime Error

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

def bfs1(pos, before_pos):
    for next_pos in ab[pos]:
        if next_pos == before_pos:
            continue
        if next_pos == u:
            return True, [pos]
        tf, root = bfs1(next_pos, pos)
        if tf:
            root.append(pos)
            return True, root
    return False, []
    
root = bfs1(v, -1)[1]
root = root[::-1]
root.append(v)
n = (len(root)) // 2

max_len = 0

def bfs2(pos, before_pos, cnt):
    global max_len
    cnt += 1
    max_len = max(max_len, cnt)
    if cnt < n - 1:
        bfs2(root[cnt + 1], pos, cnt)
    else:
        for next_pos in ab[pos]:
            if next_pos == before_pos:
                continue
            bfs2(next_pos, pos, cnt)


bfs2(v, -1, -1)
ans = max_len - 1
ans = max(ans, 0)
print(ans)

Submission status: Runtime Error

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

def bfs1(pos, before_pos):
    for next_pos in ab[pos]:
        if next_pos == before_pos:
            continue
        if next_pos == u:
            return True, [pos]
        tf, root = bfs1(next_pos, pos)
        if tf:
            root.append(pos)
            return True, root
    return False, []
    
root = bfs1(v, -1)[1]
root = root[::-1]
n = (len(root) + 1) // 2

ans = (len(root)) // 2 * 2 - 1
ans = max(ans, 0)

max_len = 0

def bfs2(pos, before_pos, cnt):
    global max_len
    cnt += 1
    max_len = max(max_len, cnt)
    if cnt < n - 1:
        bfs2(root[cnt + 1], pos, cnt)
    else:
        for next_pos in ab[pos]:
            if next_pos == before_pos:
                continue
            bfs2(next_pos, pos, cnt)


bfs2(v, -1, -1)
ans = max_len - 1
ans = max(ans, 0)
print(ans)

Submission status: Runtime Error

Solution code:
def dfs_a(N,v,adjlist,cur):
    global depth_a
    depth_a[v]=cur
    for node in adjlist[v]:
        if depth_a[node]<0:
            dfs_a(N,node,adjlist,cur+1)
def dfs_t(N,v,adjlist,cur):
    global depth_t
    depth_t[v]=cur
    for node in adjlist[v]:
        if depth_t[node]<0:
            dfs_t(N,node,adjlist,cur+1)
    
    
    

from collections import deque

N,u,v=map(int,input().split())
adjlist=[[] for _ in range(N)]
for _ in range(N-1):
    a,b=map(int,input().split())
    adjlist[a-1].append(b-1)
    adjlist[b-1].append(a-1)
depth_a=[-1]*N
depth_t=[-1]*N
dfs_a(N,v-1,adjlist,0)
dfs_t(N,u-1,adjlist,0)
M=0
for i in range(N):
    if depth_a[i]>depth_t[i]:
        curm=depth_a[i]-1
        if curm>M:
            M=curm
print(M)

Submission status: Runtime Error

Solution code:
def resolve():
	
	n, u, v = map(int, input().split())
	u -= 1
	v -= 1
	adj = [[] for i in range(n)]
	for i in range(n-1):
		a, b = map(int, input().split())
		adj[a-1].append(b-1)
		adj[b-1].append(a-1)
		
	dist_t = [0 for i in range(n)]
	dist_a = [0 for i in range(n)]
	def dfs_t(now, prv, cnt):
#		print(f"{now=}, {prv=}, {cnt}")
		for next in adj[now]:
			if next == prv:
				dist_t[now] = cnt
				continue
			dfs_t(next, now, cnt+1)
	def dfs_a(now, prv, cnt):
#		print(f"{now=}, {prv=}, {cnt}")
		for next in adj[now]:
			if next == prv:
				dist_a[now] = cnt
				continue
			dfs_a(next, now, cnt+1)
#	print(f"{adj=}\n")
	dfs_t(u, u, 0)
	dfs_a(v, v, 0)
	
	tmp = [dt for da, dt in zip(dist_t, dist_a) if dt > da]
	print(max(tmp) -1)
	
resolve()

Submission status: Runtime Error

Solution code:
import sys
import math
import bisect
def input():
    return sys.stdin.readline()[:-1]

n,u,v = map(int,input().split())
u-=1
v-=1
g = [[]for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
seen = [-1 for i in range(n)]
taka = []
aok = []
def dfs(s,lis):
    nec = g[s]
    if len(nec)==1:
        lis.append(s)
    for i in nec:
        if seen[i]!=-1:
            continue
        seen[i] = seen[s]+1
        dfs(i,lis)

seen[u]=0
dfs(u,taka)
takadist = [i for i in seen]
seen = [-1 for i in range(n)]
seen[v]=0
dfs(v,aok)
ans = 0
for i in aok:
    if takadist[i]<seen[i]:
        ans = max(ans,seen[i])
if g[u]==[v]:
    print(0)
else:
    print(ans-1)

Submission status: Runtime Error

Solution code:
n,g,s = map(int,input().split())
G = [[] for _ in range(n)]
for i in range(n):
  a,b = map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  
def dfs(V,v,d):
  if V[v] != -1:
    return
  V[v] = d
  for nv in G[v]:
    dfs(V,nv,d+1)
  
if len(G[g-1])==1 and G[g-1][0]==s-1:
  print(0)
else:
  vs = [-1]*n
  vg = [-1]*n
  dfs(vs,s-1,0)
  dfs(vg,g-1,0)
  
  ans = 0
  for i in range(n):
    if vs[i]>vg[i]:
      ans = max(ans,vs[i])
      
  print(ans-1)

Submission status: Runtime Error

Solution code:
n,g,s = map(int,input().split())
G = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  
def dfs(V,v,d):
  if V[v] != -1:
    return
  V[v] = d
  for nv in G[v]:
    dfs(V,nv,d+1)
  
if len(G[g-1])==1 and G[g-1][0]==s-1:
  print(0)
else:
  vs = [-1]*n
  vg = [-1]*n
  dfs(vs,s-1,0)
  dfs(vg,g-1,0)
  
  ans = 0
  for i in range(n):
    if vs[i]>vg[i]:
      ans = max(ans,vs[i])
      
  print(ans-1)

Submission status: Runtime Error

Solution code:
n,g,s = map(int,input().split())
G = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  
def dfs(v,d):
  if vs[v] != -1:
    return
  vs[v] = d
  for nv in G[v]:
    dfs(nv,d+1)

def dfs2(v,d):
  if vg[v] != -1:
    return
  vg[v] = d
  if d >= vs[v]:
    return  
  for nv in G[v]:
    dfs2(nv,d+1)
  
vs = [-1]*n
vg = [-1]*n

dfs(s-1,0)
dfs2(g-1,0)

print(max(vg))

Submission status: Runtime Error

Solution code:
n, u, v = map(int, input().split())
u -= 1
v -= 1
m_mat = [[] for i in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    m_mat[a].append(b)
    m_mat[b].append(a)
u_map = [-1]*n
v_map = [-1]*n
u_map[u] = 0
v_map[v] = 0
def dfs(current, depth, ma):
    for nex in m_mat[current]:
        if ma[nex] > -1:
            continue
        ma[nex] = depth
        dfs(nex, depth+1, ma)
dfs(u, 1, u_map)
dfs(v, 1, v_map)

ans = -1
for i in range(n):
    if u_map[i] < v_map[i] and v_map[i] > ans:
        ans = v_map[i]

print(ans-1)

Submission status: Runtime Error

Solution code:
n, u, v = map(int, input().split())
u -= 1
v -= 1
m_mat = [[] for i in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    m_mat[a].append(b)
    m_mat[b].append(a)
u_map = [-1]*n
v_map = [-1]*n
u_map[u] = 0
v_map[v] = 0
def dfs(current, depth, ma):
    for nex in m_mat[current]:
        if ma[nex] > -1:
            continue
        ma[nex] = depth
        dfs(nex, depth+1, ma)
dfs(u, 1, u_map)
dfs(v, 1, v_map)


ans = max(v_map)-1

print(ans)

Submission status: Runtime Error

Solution code:
import heapq
INFTY = 10**6
N,u,v = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
dist1 = [INFTY for _ in range(N+1)]
hist = [0 for _ in range(N+1)]
heap = [(0,u)]
dist1[u] = 0
hist[u] = 1
while heap:
    d,x = heapq.heappop(heap)
    if d>dist1[x]:continue
    hist[x]=1
    for y in G[x]:
        if hist[y]==0 and dist1[y]>d+1:
            dist1[y] = d+1
            heapq.heappush((d+1,y))
dist2 = [INFTY for _ in range(N+1)]
hist = [0 for _ in range(N+1)]
heap = [(0,v)]
dist2[v] = 0
hist[v] = 1
while heap:
    d,x = heapq.heappop(heap)
    if d>dist2[x]:continue
    hist[x]=1
    for y in G[x]:
        if hist[y]==0 and dist2[y]>d+1:
            dist2[y] = d+1
            heapq.heappush((d+1,y))
cmax = 0
for i in range(1,N+1):
    if dist1[i]<dist2[i]:
        cmax = max(cmax,dist2[i])
print(cmax-1)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from scipy.sparse import csgraph, csr_matrix
    import numpy as np

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

    u = u-1
    v = v-1

    cost = [1]*(N-1)
    starts = [0]*(N-1)
    nexts = [0]*(N-1)
    for i, ab in enumerate(AB):
        starts[i] = ab[0]-1
        nexts[i] = ab[1]-1

    csr = csr_matrix((cost, (starts, nexts)), shape=(N, N))
    dd = csgraph.shortest_path(csr, method='D',directed=False)
    d=np.array([dd[u],dd[v]])
    # print(d)

    cand1 = (d[0]+1 == d[1]) + (d[0] == 0)
    cand2 = (d[0] == d[1])
    ans = 0
    # for a, b in zip(d[0][cand], d[1][cand]):

    # print(cand1)
    # print(cand2)
    # print(d[0][cand1])
    # print(d[1][cand2])
    if d[0][v] == 1:
        ans = 0
    else:
        ans = int(max(d[0][cand1]))
        try:
            ans = max(ans, int(min(d[1][cand2])))
        except:
            pass
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from scipy.sparse import csgraph, csr_matrix
    import numpy as np

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

    u = u-1
    v = v-1

    cost = [1]*(N-1)
    starts = [0]*(N-1)
    nexts = [0]*(N-1)
    for i, ab in enumerate(AB):
        starts[i] = ab[0]-1
        nexts[i] = ab[1]-1

    csr = csr_matrix((cost+cost, (starts+nexts, nexts+starts)), shape=(N, N))
    dd = csgraph.shortest_path(csr, method='D')
    d=np.array([dd[u],dd[v]])
    # print(d)

    cand1 = (d[0]+1 == d[1]) + (d[0] == 0)
    cand2 = (d[0] == d[1])
    ans = 0
    # for a, b in zip(d[0][cand], d[1][cand]):

    # print(cand1)
    # print(cand2)
    # print(d[0][cand1])
    # print(d[1][cand2])
    if d[0][v] == 1:
        ans = 0
    else:
        ans = int(max(d[0][cand1]))
        try:
            ans = max(ans, int(min(d[1][cand2])))
        except:
            pass
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from scipy.sparse import csgraph, csr_matrix
    import numpy as np

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

    u = u-1
    v = v-1

    cost = [1]*(N-1)
    starts = [0]*(N-1)
    nexts = [0]*(N-1)
    for i, ab in enumerate(AB):
        starts[i] = ab[0]-1
        nexts[i] = ab[1]-1

    csr = csr_matrix((cost+cost, (starts+nexts, nexts+starts)), shape=(N, N))
    d = csgraph.shortest_path(csr, indices=[u, v])
    # print(d)

    cand1 = (d[0]+1 == d[1]) + (d[0] == 0)
    cand2 = (d[0] == d[1])
    ans = 0
    # for a, b in zip(d[0][cand], d[1][cand]):

    # print(cand1)
    # print(cand2)
    # print(d[0][cand1])
    # print(d[1][cand2])
    if d[0][v] == 1:
        ans = 0
    else:
        ans = int(max(d[0][cand1]))
        try:
            ans = max(ans, int(min(d[1][cand2])))
        except:
            pass
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict as d

def dfs(adj, visited, count, tab, start):
	visited[start-1] = 1
	for v in adj[start]:
		if not visited[v-1]:
			tab[v-1] += count
			dfs(adj, visited, count+1, tab, v)
	return tab		

n, u, v = map(int, input().split())
adj = d(list)
for i in range(n-1):
	a, b = map(int, input().split())
	adj[a].append(b)
	adj[b].append(a)
	
takahashi = dfs(adj, [0] * n, 1, [0] * n, u)
aoki = dfs(adj, [0] * n, 1, [0] * n, v)

res = -1
for i in range(n):
	if takahashi[i] <= aoki[i]:
		res = max(res, aoki[i] - 1)

print(res)

Submission status: Runtime Error

Solution code:
N, u, v = (int(i) for i in input().split())
adj=[]
for i in range(N+1):adj.append([])
for i in range(N-1):
	a,b = map(int,input().split())
	adj[a]+=[b]
	adj[b]+=[a]
	
prof = [0]*(N+1)
haut = [0]*(N+1)
parent = [-1]*(N+1)

def enraciner(sommet):
	for s in adj[sommet]:
		if s!=parent[sommet]:
			parent[s] = sommet
			# ~ prof[s] = 1+prof[sommet]
			enraciner(s)
	haut[sommet] = 1
	# ~ tmp = [haut[s]for s in adj[sommet] if s!=parent[sommet]]
	# ~ if tmp: haut[sommet]+=max(tmp)

enraciner(v)

# ~ print("parent",parent)
# ~ print("haut",haut)
# ~ print("prof",prof)

ans = 0

#montee
pu = prof[u]
pv = prof[v]
m = (pu - pv -1)//2
pu-=m
pv+=m
# ~ print("m",m)
ans+=m
for i in range(m):
	u = parent[u]

mx = 0
if len(adj[u])>1:mx = max(haut[i] for i in adj[u] if i!= parent[u])
# ~ print("mx",mx)
ans+= mx

last = (pu-pv)//2
# ~ print("last",last)
ans+=last

print(ans)

Submission status: Runtime Error

Solution code:
N, u, v = (int(i) for i in input().split())
adj=[]
for i in range(N+1):adj.append([])
for i in range(N-1):
	a,b = map(int,input().split())
	adj[a]+=[b]
	adj[b]+=[a]
	
prof = [0]*(N+1)
haut = [0]*(N+1)
parent = [-1]*(N+1)

def enraciner(sommet):
	for s in adj[sommet]:
		if s!=parent[sommet]:
			# ~ parent[s] = sommet
			# ~ prof[s] = 1+prof[sommet]
			enraciner(s)
	haut[sommet] = 1
	# ~ tmp = [haut[s]for s in adj[sommet] if s!=parent[sommet]]
	if tmp: haut[sommet]+=max(tmp)

enraciner(v)

# ~ print("parent",parent)
# ~ print("haut",haut)
# ~ print("prof",prof)

ans = 0

#montee
pu = prof[u]
pv = prof[v]
m = (pu - pv -1)//2
pu-=m
pv+=m
# ~ print("m",m)
ans+=m
for i in range(m):
	u = parent[u]

mx = 0
if len(adj[u])>1:mx = max(haut[i] for i in adj[u] if i!= parent[u])
# ~ print("mx",mx)
ans+= mx

last = (pu-pv)//2
# ~ print("last",last)
ans+=last

print(ans)

Submission status: Runtime Error

Solution code:
N, u, v = (int(i) for i in input().split())
adj=[]
for i in range(N+1):adj.append([])
for i in range(N-1):
	a,b = map(int,input().split())
	adj[a]+=[b]
	adj[b]+=[a]
	
prof = [0]*(N+1)
haut = [0]*(N+1)
parent = [-1]*(N+1)

def enraciner(sommet):
	for s in adj[sommet]:
		if s!=parent[sommet]:
			parent[s] = sommet
			prof[s] = 1+prof[sommet]
			enraciner(s)
	haut[sommet] = 1
	# ~ tmp = [haut[s]for s in adj[sommet] if s!=parent[sommet]]
	# ~ if tmp: haut[sommet]+=max(tmp)

enraciner(v)

# ~ print("parent",parent)
# ~ print("haut",haut)
# ~ print("prof",prof)

ans = 0

#montee
pu = prof[u]
pv = prof[v]
m = (pu - pv -1)//2
pu-=m
pv+=m
# ~ print("m",m)
ans+=m
for i in range(m):
	u = parent[u]

mx = 0
if len(adj[u])>1:mx = max(haut[i] for i in adj[u] if i!= parent[u])
# ~ print("mx",mx)
ans+= mx

last = (pu-pv)//2
# ~ print("last",last)
ans+=last

print(ans)

Submission status: Runtime Error

Solution code:
N, u, v = (int(i) for i in input().split())
adj=[]
for i in range(N+1):adj.append([])
for i in range(N-1):
	a,b = map(int,input().split())
	adj[a]+=[b]
	adj[b]+=[a]
	
prof = [0]*(N+1)
haut = [0]*(N+1)
parent = [-1]*(N+1)

def enraciner(sommet):
	for s in adj[sommet]:
		if s!=parent[sommet]:
			parent[s] = sommet
			prof[s] = 1+prof[sommet]
			enraciner(s)
	haut[sommet] = 1
	tmp = [haut[s]for s in adj[sommet] if s!=parent[sommet]]
	if tmp: haut[sommet]+=max(tmp)

enraciner(v)

# ~ print("parent",parent)
# ~ print("haut",haut)
# ~ print("prof",prof)

ans = 0

#montee
pu = prof[u]
pv = prof[v]
m = (pu - pv -1)//2
pu-=m
pv+=m
# ~ print("m",m)
ans+=m
for i in range(m):
	u = parent[u]

mx = 0
# ~ if len(adj[u])>1:mx = max(haut[i] for i in adj[u] if i!= parent[u])
# ~ print("mx",mx)
ans+= mx

last = (pu-pv)//2
# ~ print("last",last)
ans+=last

print(ans)

Submission status: Runtime Error

Solution code:
N, u, v = (int(i) for i in input().split())
adj=[]
for i in range(N+1):adj.append([])
for i in range(N-1):
	a,b = map(int,input().split())
	adj[a]+=[b]
	adj[b]+=[a]
	
prof = [0]*(N+1)
haut = [0]*(N+1)
parent = [-1]*(N+1)

def enraciner(sommet):
	for s in adj[sommet]:
		if s!=parent[sommet]:
			parent[s] = sommet
			prof[s] = 1+prof[sommet]
			enraciner(s)
	haut[sommet] = 1
	tmp = [haut[s]for s in adj[sommet] if s!=parent[sommet]]
	if tmp: haut[sommet]+=max(tmp)

enraciner(v)

# ~ print("parent",parent)
# ~ print("haut",haut)
# ~ print("prof",prof)

ans = 0

#montee
pu = prof[u]
pv = prof[v]
m = (pu - pv -1)//2
pu-=m
pv+=m
# ~ print("m",m)
ans+=m
for i in range(m):
	u = parent[u]

mx = 0
if len(adj[u])>1:mx = max(haut[i] for i in adj[u] if i!= parent[u])
# ~ print("mx",mx)
ans+= mx

last = (pu-pv)//2
# ~ print("last",last)
ans+=last

print(ans)

Submission status: Runtime Error

Solution code:
N, u, v = (int(i) for i in input().split())
adj=[]
for i in range(N+1):adj.append([])
for i in range(N-1):
	a,b = map(int,input().split())
	adj[a]+=[b]
	adj[b]+=[a]
	
prof = [0]*(N+1)
haut = [0]*(N+1)
parent = [-1]*(N+1)

def enraciner(sommet):
	for s in adj[sommet]:
		if s!=parent[sommet]:
			parent[s] = sommet
			prof[s] = 1+prof[sommet]
			enraciner(s)
	haut[sommet] = 1
	if parent[sommet]==-1:haut[sommet]+=max(haut[s]for s in adj[sommet] if s!=parent[sommet])
	elif len(adj[sommet]) >1 : haut[sommet]+= max(haut[s]for s in adj[sommet] if s!=parent[sommet])

enraciner(v)

# ~ print("parent",parent)
# ~ print("haut",haut)
# ~ print("prof",prof)

ans = 0

#montee
pu = prof[u]
pv = prof[v]
m = (pu - pv -1)//2
pu-=m
pv+=m
# ~ print("m",m)
ans+=m
for i in range(m):
	u = parent[u]

mx = 0
if len(adj[u])>1:mx = max(haut[i] for i in adj[u] if i!= parent[u])
# ~ print("mx",mx)
ans+= mx

last = (pu-pv)//2
# ~ print("last",last)
ans+=last

print(ans)

Submission status: Runtime Error

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

def dfs(already, node, depth):
    depth += 1
    children = edges[node]
    for child in children:
        if already[child] == 0:
            already[child] = depth
            already = dfs(already, child, depth)
    return already

already_u = [0 for i in range(n)]
already_u[u] = -1
already_u = dfs(already_u, u, 0)
already_u[u] = 0
already_v = [0 for i in range(n)]
already_v[v] = -1
already_v = dfs(already_v, v, 0)
already_v[v] = 0

maxi = 0
for i in range(n):
    if already_u[i] < already_v[i]:
        maxi = max(maxi, already_v[i])
print(maxi-1)

Submission status: Runtime Error

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

def dfs(already, node, depth):
    depth += 1
    children = edges[node]
    for child in children:
        if already[child] == 0:
            already[child] = depth
            already = dfs(already, child, depth)
    return already

already_u = [0 for i in range(n)]
already_u = dfs(already_u, u, 0)
already_u[u] = 0
already_v = [0 for i in range(n)]
already_v = dfs(already_v, v, 0)
already_v[v] = 0

maxi = 0
for i in range(n):
    if already_u[i] < already_v[i]:
        maxi = max(maxi, already_v[i])
print(maxi-1)

Submission status: Runtime Error

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

dist = [0] * N
def dfs(v, d=0, p=-1):
    global dist
    dist[v] = d
    for u in edges[v]:
        if u == p:
            continue
        dfs(u, d + 1, v)

def calc_dist(s):
    global dist
    dist = [0] * N
    dfs(s)
    return dist

distS = calc_dist(u)
distT = calc_dist(v)

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

Submission status: Runtime Error

Solution code:
from collections import deque, defaultdict
from copy import deepcopy
import sys
import resource

resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))
sys.setrecursionlimit(10**5)

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

depth = dict(zip(list(range(1,N+1)),[-1]*N))

def bfs(s):
    if graph[s]:
        for v in graph[s]:
            if depth[v] == -1:
                depth[v] = depth[s] + 1
                bfs(v)

depth = dict(zip(list(range(1,N+1)),[-1]*N))
depth[v] = 0
bfs(v)
depth_v = deepcopy(depth)

depth = dict(zip(list(range(1,N+1)),[-1]*N))
depth[u] = 0
bfs(u)
depth_u = depth
depth_v = sorted(depth_v.items(), key = lambda x:x[0])
depth_u = sorted(depth_u.items(), key= lambda x:x[0])

MAX = 0
for v,u in zip(depth_v, depth_u):
    if u[1] < v[1]:
        MAX = max(MAX,v[1])
print(MAX-1)

Submission status: Runtime Error

Solution code:
from collections import deque, defaultdict
from copy import deepcopy

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

depth = dict(zip(list(range(1,N+1)),[-1]*N))

def bfs(s):
    if graph[s]:
        for v in graph[s]:
            if depth[v] == -1:
                depth[v] = depth[s] + 1
                bfs(v)

depth = dict(zip(list(range(1,N+1)),[-1]*N))
depth[v] = 0
bfs(v)
depth_v = deepcopy(depth)

depth = dict(zip(list(range(1,N+1)),[-1]*N))
depth[u] = 0
bfs(u)
depth_u = depth
depth_v = sorted(depth_v.items(), key = lambda x:x[0])
depth_u = sorted(depth_u.items(), key= lambda x:x[0])

MAX = 0
for v,u in zip(depth_v, depth_u):
    if u[1] < v[1]:
        MAX = max(MAX,v[1])
print(MAX-1)

Submission status: Runtime Error

Solution code:
from collections import deque, defaultdict
from copy import deepcopy

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

depth = dict(zip(list(range(1,N+1)),[-1]*N))

def bfs(s):
    if graph[s]:
        for v in graph[s]:
            if depth[v] == -1:
                depth[v] = depth[s] + 1
                bfs(v)

depth = dict(zip(list(range(1,N+1)),[-1]*N))
depth[v] = 0
bfs(v)
depth_v = deepcopy(depth)

depth = dict(zip(list(range(1,N+1)),[-1]*N))
depth[u] = 0
bfs(u)
depth_u = depth
depth_v = sorted(depth_v.items(), key = lambda x:x[0])
depth_u = sorted(depth_u.items(), key= lambda x:x[0])
print(depth_v)
print(depth_u)
MAX = 0
for v,u in zip(depth_v, depth_u):
    print(v[1],u[1])
    if u[1] < v[1]:
        MAX = max(MAX,v[1])
print(MAX-1)

Submission status: Runtime Error

Solution code:
from collections import deque, defaultdict

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

depth = dict(zip(list(range(1,N+1)),[-1]*N))

def bfs(s):
    if graph[s]:
        for v in graph[s]:
            if depth[v] == -1:
                depth[v] = depth[s] + 1
                bfs(v)

depth[v] = 0
bfs(v)
MAX = 0

if depth[u] <= 2:
    print(depth[u]- 1)
else:
    print(max(depth.values())-1)

Submission status: Runtime Error

Solution code:
f=lambda:map(int,input().split())
n,st,sa=f()
st-=1
sa-=1
g=[[] for _ in range(n)]
for _ in range(n-1):
  a,b=f()
  g[a-1].append(b-1)
  g[b-1].append(a-1)
def dfs(v,p=-1,d=0):
  l[v]=d
  for c in g[v]:
    if c==p: continue
    dfs(c,v,d+1)
def dist(s):
  global l
  l=[0]*n
  dfs(s)
  return l
lt=dist(st)
la=dist(sa)
m=0
for i in range(n):
  if lt[i]<la[i]: m=max(m,la[i])
print(m-1)

Submission status: Runtime Error

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

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

dist = [-1 for _ in range(100005)]
def dfs(p, d=0, q=-1):
  global dist
  dist[p] = d
  for branch in branches[p]:
    # 親に戻ってくるのを避ける
    if branch == q:
      continue
    dfs(branch, d+1, p)

def calcDist(x):
  global dist
  dist = [-1 for _ in range(100005)]
  dfs(x)
  return dist

udist = calcDist(u)
vdist = calcDist(v)

# print(udist[0:10])
# print(vdist[0:10])

maxdist = 0
for i in range(1, n + 1):
  if udist[i] < vdist[i]:
    maxdist = max(maxdist, vdist[i])

print(maxdist - 1)

Submission status: Runtime Error

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

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

dist = [-1 for _ in range(100005)]
def dfs(p, d=0, q=-1):
  global dist
  dist[p] = d
  for branch in branches[p]:
    # 親に戻ってくるのを避ける
    if branch == q:
      continue
    dfs(branch, d+1, p)

def calcDist(x):
  global dist
  dist = [-1 for _ in range(100005)]
  dfs(x)
  return dist

udist = calcDist(u)
vdist = calcDist(v)

print(udist[0:10])
print(vdist[0:10])

maxdist = 0
for i in range(1, n + 1):
  if udist[i] < vdist[i]:
    maxdist = max(maxdist, vdist[i])

print(maxdist - 1)

Submission status: Runtime Error

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

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


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

depth = [0]*n
GT = copy.deepcopy(g)
GT[T].append(-1)
root = T
dfs(GT, root, -1, 0)
dt = depth.copy()

depth = [0]*n
GA = copy.deepcopy(g)
GA[A].append(-1)
root = A
dfs(GA, root, -1, 0)
da = depth.copy()

def dfs2(G, v, p):
    for nv in G[v]:
        if nv == p:
            continue
        if dt[nv] <= da[nv]:
            maxd[0] = max(maxd[0], da[nv])
        else:
            continue
        dfs2(G, nv, v)


maxd = [-float('inf')]
root = T
dfs2(GT, root, -1)
if maxd[0] == -float('inf'):
    print(0)
else:
    print(maxd[0]-1)

Submission status: Runtime Error

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

from collections import deque, defaultdict

#以下０オリジンで考える

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

G = defaultdict(lambda:deque([])) #連結リスト

#以下０オリジンで考える
for _ in range(n-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    
#start位置から繋がる全ノードへの距離を求める関数、幅優先探索
#dst_dict[player][node]がplayerとnodeの距離
def bfs(start, player):
    que = deque([start, -1, 0])
    while que:
        node, par, dst = que.popleft() #par:親, dst:距離
        if len(G[node]) == 1:
            dst_dict[player][node] = dst
            
        for nxt in graph[node]:
            if nxt == par:
                continue
            que.append((nxt, node, dst+1))
            
dst_dict = [{}, {}]

bfs(u, 0)
bfs(v, 1)

max_time = 0
for k in dst_dict[0]:
    if dst_dict[0][k] < dst_dict[1][k]:
        max_time = max(max_time, dst_dict[1][k]-1)
    
print(max_time)