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: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
n,u,v=map(int,input().split())
node=[[]for _ in range(n)]
for _ in range(n-1):
	a,b=map(int,input().split())
	node[a-1].append(b-1)
	node[b-1].append(a-1)
def dfs(i):
	visited[i]=1
	for x in node[i]:
		if visited[x]==0:
			dis[x]=dis[i]+1
			dfs(x)
inf=10**9
dis=[inf]*n;dis[u-1]=0;visited=[0]*n
dfs(u-1)
dis2=[]
from copy import copy
dis_dash=copy(dis)
dis2.append(dis_dash)
dis[v-1]=0;visited=[0]*n
dfs(v-1)
dis2.append(dis)
cnt=0
for i in range(n):
	if dis2[0][i]<dis2[1][i]:
		cnt=max(cnt,dis2[1][i])
if cnt%2==1:
	cnt-=1
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
n,u,v=map(int,input().split())
node=[[]for _ in range(n)]
for _ in range(n-1):
	a,b=map(int,input().split())
	node[a-1].append(b-1)
	node[b-1].append(a-1)
def dfs(i):
	visited[i]=1
	for x in node[i]:
		if visited[x]==0:
			dis[x]=dis[i]+1
			dfs(x)
inf=10**9
dis=[inf]*n;dis[u-1]=0;visited=[0]*n
dfs(u-1)
dis2=[]
from copy import copy
dis_dash=copy(dis)
dis2.append(dis_dash)
dis[v-1]=0;visited=[0]*n
dfs(v-1)
dis2.append(dis)
cnt=0
for i in range(n):
	if dis2[0][i]<=dis2[1][i]:
		cnt=max(cnt,dis2[0][i]+dis2[1][i])
print(cnt//2)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
n,u,v=map(int,input().split())
node=[[]for _ in range(n)]
for _ in range(n-1):
	a,b=map(int,input().split())
	node[a-1].append(b-1)
	node[b-1].append(a-1)
def dfs(i):
	visited[i]=1
	for x in node[i]:
		if visited[x]==0:
			dis[x]=dis[i]+1
			dfs(x)
inf=10**9
dis=[inf]*n;dis[u-1]=0;visited=[0]*n
dfs(u-1)
dis2=[]
from copy import copy
dis_dash=copy(dis)
dis2.append(dis_dash)
dis[v-1]=0;visited=[0]*n
dfs(v-1)
dis2.append(dis)
cnt=0
for i in range(n):
	if dis2[0][i]<dis2[1][i]:
		cnt=max(cnt,dis2[0][i]+dis2[1][i])
print(cnt//2)

Submission status: Wrong Answer

Solution code:
N,u,v=map(int,input().split())
dist_v=[-1 for _ in range(N+1)]
dist_u=[-1 for _ in range(N+1)]
Graph=[[] for _ in range(N+1) for _ in range(N+1)]

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

def dfs(v,dist=0):
    dist_v[v]=dist
    for nv in Graph[v]:
        if dist_v[nv]!=-1:
            continue
        dfs(nv,dist+1)  

def dfs_u(u,dist=0):
    dist_u[u]=dist
    for nu in Graph[u]:
        if dist_u[nu]!=-1:
            continue
        if dist+1>=dist_v[nu]:
            continue
        dfs_u(nu,dist+1)
dfs(v)
dfs_u(u)
print(dist_v[dist_u.index(max(dist_u))]-1)

Submission status: Wrong Answer

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

parent={i:-1 for i in range(1,N+1)}
depth={i:-1 for i in range(1,N+1)}
parent[v]=0
depth[v]=0
q=set([v])
sub=set([])
while q:
    while q:
        x=q.pop()
        for i in edge[x]:
            if parent[i]==-1:
                parent[i]=x
                depth[i]=depth[x]+1
                sub.add(i)

        if not q:
            q=sub
            sub=set([])
            break

if depth[u]%2==1:
    i=depth[u]//2
    stand=u
    while i>0:
        stand=parent[stand]
        i-=1
    test=depth[stand]
    q=set([stand])
    sub=set([])
    while q:
        while q:
            x=q.pop()
            for i in edge[x]:
                if i!=parent[x]:
                    test=max(test,depth[i])
                    sub.add(i)

            if not q:
                q=sub
                sub=set([])
                break

    print(test-1)
else:
    print('FUCK')
    i=depth[u]//2-1
    stand=u
    while i>0:
        stand=parent[stand]
        i-=1
    test=depth[stand]
    q=set([stand])
    sub=set([])
    while q:
        while q:
            x=q.pop()
            for i in edge[x]:
                if i!=parent[x]:
                    test=max(test,depth[i])
                    sub.add(i)

            if not q:
                q=sub
                sub=set([])
                break

    print(test-1)

Submission status: Wrong Answer

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


def BFS(g, s, e):
    d = 1
    q = [s]
    visited = set()
    visited.add(s)
    if s == e:
        return 0

    while (len(q) != 0):
        qs = len(q)
        for _ in range(qs):
            qpop = q[0]
            q = q[1:]
            for v in g[qpop]:
                if v == e:
                    return d
                if v not in visited:
                    q.append(v)
                    visited.add(v)
        d += 1

    return d


def main():
    l = [int(e) for e in si().split()]
    n, u, v, ans, graph = l[0], l[1], l[2], 0, {}

    for _ in range(n-1):
        l = [int(e) for e in si().split()]
        if l[0] not in graph:
            graph[l[0]] = set()
        if l[1] not in graph:
            graph[l[1]] = set()
        graph[l[0]].add(l[1])
        graph[l[1]].add(l[0])

    while 1:
        T_options = {}
        for node in graph[u]:
            T_options[node] = BFS(graph, node, v)

        maxValue = max(T_options.values())
        print('T_options:')
        print(T_options)

        for (key, value) in T_options.items():
            if value == maxValue:
                u = key
                print('T is now at:')
                print(u)
                break

        if u == v:
            print(ans)
            break

        ans += 1
        A_options = {}
        for node in graph[v]:
            A_options[node] = BFS(graph, node, u)

        minValue = min(A_options.values())
        print('A_options:')
        print(A_options)

        for (key, value) in A_options.items():
            if value == minValue:
                v = key
                print('A is now at:')
                print(v)
                break

        if u == v:
            print(ans)
            break


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


def BFS(g, s, e):
    d = 1
    q = [s]
    visited = set()
    visited.add(s)
    if s == e:
        return 0

    while (len(q) != 0):
        qs = len(q)
        for _ in range(qs):
            for v in g[q[0]]:
                if v == e:
                    return d
                if v not in visited:
                    q.append(v)
                    visited.add(v)
                q = q[1:]
            d += 1

    return d


def main():
    l = [int(e) for e in si().split()]
    n, u, v, ans, graph = l[0], l[1]-1, l[2]-1, 0, {}

    for _ in range(n-1):
        l = [int(e) for e in si().split()]
        if l[0]-1 not in graph:
            graph[l[0]-1] = set()
        if l[1]-1 not in graph:
            graph[l[1]-1] = set()
        graph[l[0]-1].add(l[1]-1)
        graph[l[1]-1].add(l[0]-1)

    while 1:
        T_options = {}
        for node in graph[u]:
            T_options[node] = BFS(graph, node, v)

        maxValue = max(T_options.values())
        for (key, value) in T_options.items():
            if value == maxValue:
                u = key
                break

        if u == v:
            print(ans)
            break

        ans += 1
        A_options = {}
        for node in graph[v]:
            A_options[node] = BFS(graph, node, u)

        minValue = min(A_options.values())
        for (key, value) in A_options.items():
            if value == minValue:
                v = key
                break
        if u == v:
            print(ans)
            break

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(s):
    que = deque([(s, 0)])
    dist = [None]*n
    while que:
        cur, cst = que.popleft()
        if dist[cur] != None:
            continue
        dist[cur] = cst
        for nxt in es[cur]:
            que.append((nxt, cst+1))
    return dist

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

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, u, v = map(int, input().split())
d = defaultdict(list)
for _ in range(N-1):
    A, B = map(int, input().split())
    d[A].append(B)
    d[B].append(A)

def get_dist(s):
    dist = [-1]*(N+1)
    dist[s] = 0

    q = [s]
    while q:
        a = q.pop()
        for b in d[a]:
            if dist[b]!=-1:
                continue
            dist[b] = dist[a] + 1
            q.append(b)
    return dist

du, dv = get_dist(u), get_dist(v)
ds = [(i,j[0], j[1]) for i,j in enumerate(zip(du, dv)) if j[0]<j[1]]
ds.sort(key=lambda x:-x[1])
a, b, c = ds[0]
print(c-1)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import deque

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


def dfs(v):
    dist = [-1] * (n + 1)
    stack = deque([v])
    dist[v] = 0
    while stack:
        v = stack.popleft()
        memo = dist[v] + 1
        for w in graph[v]:
            if dist[w] >= 0:
                continue
            dist[w] = memo
            stack.append(w)
    return dist


U, V = dfs(u), dfs(v)
ans = 0
for x, y in zip(U[1:], V[1:]):
    print(x, y)
    if x < y:
        ans = max(ans, y - 1)
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
INF = 10 ** 18

def dijkstra(s):
    used = [1] * n
    dp = [INF] * n
    dp[s] = 0
    hq = []
    used[s] = 0
    for i in cost[s]:
        heappush(hq, i)

    while hq:
        minv = heappop(hq)
        if used[minv[1]] == 0:
            continue
        v = minv[1]
        dp[v] = minv[0]
        used[v] = 0
        for i in cost[v]:
            if used[i[1]]:
                heappush(hq, [i[0] + dp[v], i[1]])
    return dp

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

dp = dijkstra(v - 1)
print(max(dp) - 1)

Submission status: Wrong Answer

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

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

connect = [set() for _ in range(n)]
for a, b in edge:
    connect[a-1].add(b-1)
    connect[b-1].add(a-1)

du = [0] * n
dv = [0] * n

def dfs(v, dis, ng, d):
    d[v] = dis
    ng.add(v)
    for w in connect[v]:
        if w not in ng:
            dfs(w, dis+1, ng, d)

dfs(u, 0, set(), du)
dfs(v, 0, set(), dv)

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

Submission status: Wrong Answer

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

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

connect = [set() for _ in range(n)]
for a, b in edge:
    connect[a-1].add(b-1)
    connect[b-1].add(a-1)

du = [0] * n
dv = [0] * n

def dfs(v, dis, ng, d):
    d[v] = dis
    ng.add(v)
    for w in connect[v]:
        if w not in ng:
            dfs(w, dis+1, ng, d)

dfs(u, 0, set(), du)
dfs(v, 0, set(), dv)

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

Submission status: Wrong Answer

Solution code:
import queue

N, U, V = map(int, input().rstrip().split())
U -= 1
V -= 1

v2e = [set() for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().rstrip().split())
    v2e[a].add(b)
    v2e[b].add(a)
    
q = queue.Queue()
q.put(U)
p = [-1] * N
p[U] = U
while True:
    a = q.get()
    
    if a == V:
        break
    
    for b in v2e[a]:
        if p[b] == -1:
            p[b] = a
            q.put(b)
            
a = V
min_p = []
while True:
    min_p.append(a)
    if a == U:
        break
    a = p[a]

p = [-1] * N
p[min_p[(len(min_p)-1)//2]] = min_p[(len(min_p)-1)//2]
for a in v2e[min_p[(len(min_p)-1)//2]]:
    p[a] = a
p[min_p[-len(min_p)//2]] = min_p[-len(min_p)//2]

q = queue.Queue()
q.put((min_p[-len(min_p)//2], 0))
while q.qsize() > 0:
    a, d = q.get()
    
    for b in v2e[a]:
        if p[b] == -1:
            p[b] = a
            q.put((b, d + 1))
            
print(d + (len(min_p) - 2) // 2 + len(min_p) % 2)

Submission status: Wrong Answer

Solution code:
N, u, v = map(int,input().split())
u, v = u - 1, v - 1
path = [] 
for _ in range(N):
    path.append([])
for _ in range(N - 1):
    A, B = map(int,input().split())
    A, B = A - 1, B - 1
    path[A].append(B)
    path[B].append(A)
dep = [0] * N
dep[v] = 1
leaf = []
stack2 = [v]
cnt = 1
while stack2:
    stack = stack2[0:]
    stack2 = []
    while stack:
        s = stack.pop()
        for to in path[s]:
            judge = len(path[s])
            if dep[to]:
                judge -= 1
                if judge == 0:
                    leaf.append([cnt, s])
                continue
            dep[to] = cnt
            stack2.append(to)
            judge += 1 
    cnt += 1
leaf.sort(reverse=True)
depmax = [0] * N
for i in range(len(leaf)):
    depth, a = leaf[i][0], leaf[i][1] 
    depmax[a] = depth
    end = False
    for j in range(depth - 1, 0, -1):
        if end:
            break
        for b in path[a]:
            if dep[b] == j:
                if depmax[b] < depmax[a]:
                    depmax[b] = depmax[a]
                    a = b
                    break
                else:
                    end = True
                    break
dis = dep[u] - 2
leng = depmax[u]
a = u
for depth in range(dep[u] - 1, dep[u] - (dis // 2), -1):
    for to in path[a]:
        if depth == dep[to]:
            leng = depmax[to]
        a = to
print(leng - 2)

Submission status: Wrong Answer

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

n, u, v = [int(x) for x in input().split()]

import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

################################
n, w = n, n - 1 #n:頂点数　w:辺の数

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    x,y = map(int,input().split())
    z = 1
    edge[x - 1].append([z,y - 1])
    edge[y - 1].append([z,x - 1]) 

takahashi = dijkstra_heap(u - 1)
aoki = dijkstra_heap(v - 1)

ans = takahashi[v - 1] - 1 # 高橋君がいもる

idx = 0
for i, j in zip(takahashi, aoki):
    if idx == u - 1 or idx == v - 1:
        idx += 1
        continue
    if j - i > 0:
        ans = max(ans, i + (j - i) // 2)
    idx += 1

print(ans)

Submission status: Wrong Answer

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

n, u, v = [int(x) for x in input().split()]

import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

################################
n, w = n, n - 1 #n:頂点数　w:辺の数

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    x,y = map(int,input().split())
    z = 1
    edge[x - 1].append([z,y - 1])
    edge[y - 1].append([z,x - 1]) 

takahashi = dijkstra_heap(u - 1)
aoki = dijkstra_heap(v - 1)

ans = takahashi[v - 1] // 2

idx = 0
for i, j in zip(takahashi, aoki):
    if idx == u - 1 or idx == v - 1:
        idx += 1
        continue
    if j - i > 0:
        ans = max(ans, i + (j - i) // 2)
    idx += 1

print(ans)

Submission status: Wrong Answer

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

tree=[]
for i in range(N+1):
  tree.append([])

for i in range(N-1):
  A,B=map(int,input().split())
  tree[A].append(B)
  tree[B].append(A)
#print(u,v)
#print(tree)

dist_tak=[-1]*(N+1)
queue=[u]
d=0
while(len(queue)>0):
  new_queue=set()  
  for q in queue:
    if dist_tak[q]==-1:
      dist_tak[q]=d
      for q2 in tree[q]:
        new_queue.add(q2)
  d+=1
  queue=new_queue
#print(dist_tak)

dist_aok=[-1]*(N+1)
queue=[v]
d=0
while(len(queue)>0):
  new_queue=set()  
  for q in queue:
    if dist_aok[q]==-1:
      dist_aok[q]=d
      for q2 in tree[q]:
        new_queue.add(q2)
  d+=1
  queue=new_queue
#print(dist_aok)

if len(tree[u])==1 and tree[u][0]==v:
  print(0)
else:
  answer=0
  if dist_tak[v]%2==0:
    for i in range(1,N+1):
      if dist_tak[i]<dist_aok[i] and answer<dist_aok[i]:
        answer=dist_aok[i]
  else:
    for i in range(1,N+1):
      if dist_tak[i]<dist_aok[i] and answer<dist_aok[i]-1:
        answer=dist_aok[i]-1
  print(answer)

Submission status: Wrong Answer

Solution code:
N,u,v = map(int,input().split())
E = [[] for _ in range(N + 1)]
for i in range(N-1):
    a,b = map(int,input().split())
    E[a].append(b)
    E[b].append(a)
#print(E)
def bfs(start,N):
    d = [-1]*(N+1)
    d[start] = 0
    q = [start]
    while q:
        #print(d,q)
        v = q.pop()
        cnt = d[v]+1
        for i in E[v]:
            if(d[i] == -1):
                q.append(i)
                d[i] = cnt
    return d
taka = bfs(u,N)
aoki = bfs(v,N)
#print(taka,aoki)
fin = -1
for i in range(N+1):
    if(taka[i] < aoki[i]):
        fin = max(fin,aoki[i])
        ans = fin - (aoki[i]-taka[i]+1)//2
print(ans)

Submission status: Wrong Answer

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

def bfs(start,N,AB):
    d = [-1]*N
    d[start-1] = 0
    q = [start]
    while q:
        #print(d,q)
        v = q.pop()
        cnt = d[v-1]+1
        for j in AB:
            if(j[0] == v and d[j[1]-1] == -1):
                q.append(j[1])
                d[j[1]-1] = cnt
            if(j[1] == v and d[j[0]-1] == -1):
                q.append(j[0])
                d[j[0]-1] = cnt
    return d
taka = bfs(u,N,AB)#takahashi
aoki = bfs(v,N,AB)
#print(taka,aoki)
fin = -1
for i in range(N):
    if(taka[i] < aoki[i]):
        fin = max(fin,aoki[i])
        ans = fin - (aoki[i]-taka[i]+1)//2
print(ans)

Submission status: Wrong Answer

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

def bfs(start,N,AB):
    d = [-1]*N
    d[start-1] = 0
    q = [start]
    cnt = 1
    while q:
        #print(d,q)
        q1 = []
        for i in q:
            for j in AB:
                if(j[0] == i and d[j[1]-1] == -1):
                    q1.append(j[1])
                    d[j[1]-1] = cnt
                if(j[1] == i and d[j[0]-1] == -1):
                    q1.append(j[0])
                    d[j[0]-1] = cnt
        q = q1
        cnt += 1
    return d
taka = bfs(u,N,AB)#takahashi
aoki = bfs(v,N,AB)
#print(taka,aoki)
fin = -1
for i in range(N):
    if(taka[i] < aoki[i]):
        fin = max(fin,aoki[i])
        ans = fin - (aoki[i]-taka[i]+1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
import sys

input = sys.stdin.readline

def dijkstra_heap(s,edge,n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

def main():
    N, u, v = map(int, input().split())
    u -= 1
    v -= 1
    edge = [[] for i in range(N)]
    for _ in range(N-1):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        edge[A].append([1,B])
        edge[B].append([1,A])
    
    d1 = dijkstra_heap(u,edge, N)
    d2 = dijkstra_heap(v,edge, N)

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():
    N, u, v = map(int, input().split())
    adj = [set() for _ in range(N)]
    for _ in range(N-1):
        A, B = map(int, input().split())
        adj[A-1].add(B-1)
        adj[B-1].add(A-1)
    cost = [-1] * N
    q = deque([(v-1, 0)])
    while len(q):
        cur, c = q.popleft()
        cost[cur] = c
        for nxt in adj[cur]:
            if cost[nxt] == -1:
                q.append((nxt, c+1))
    reachable = [False] * N
    q = deque([(u-1, 0)])
    while len(q):
        cur, c = q.popleft()
        reachable[cur] = True
        for nxt in adj[cur]:
            if reachable[nxt] == False and c <= cost[nxt]:
                q.append((nxt, c+1))
    ans = 0
    for i in range(N):
        if reachable[i] and len(adj[i]) >= 2:
            ans = max(ans, cost[i])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,t,a=map(int,input().split())
t-=1
a-=1
g=[[] for _ in range(n)]
uv=[list(map(int,input().split())) for _ in range(n-1)]
for i in range(n-1):
    u,v=uv[i]
    u-=1
    v-=1
    g[u].append(v)
    g[v].append(u)


from collections import deque
q=deque()
q.append(t)
g1=[0]*n
while q:
    now=q.popleft()
    l=g[now]
    for k in l:
        if g1[k]:
            continue
        g1[k]=g1[now]+1
        for s in l:
            q.append(s)
g1[t]=0

q.append(a)
g2=[0]*n
while q:
    now=q.popleft()
    l=g[now]
    for k in l:
        if g2[k]:
            continue
        g2[k]=g2[now]+1
        for s in l:
            q.append(s)
g2[a]=0

x=0
for i in range(n):
    if g1[i]<g2[i]:
        x=max(x,i)
print(g2[x]-1)

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix 

N,u,v = (int(x) for x in input().split())
mat = [[0] * N for i in range(N)]

for i in range(N-1):
  a,b = (int(x) for x in input().split())
  mat[a-1][b-1] = 1
  mat[b-1][a-1] = 1
  
matrix = np.array(mat)
dist = shortest_path(matrix,directed=False,unweighted=True).tolist()
num = 0
while(1):
  if u == v:
    break
  dic = dict(enumerate(dist[v-1]))
  for key,value in sorted(dic.items(),key=lambda x:x[1],reverse=True):
    if mat[u-1][key] != 0:
      u = key+1
      break
    
  if u == v:
    break
  dic = dict(enumerate(dist[u-1]))
  for key,value in sorted(dic.items(),key=lambda x:x[1]):
    if mat[v-1][key] != 0:
      v = key+1
      num += 1
      break
  if u == v:
    break
  

print(num)

Submission status: Wrong Answer

Solution code:
n,u,v = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)
print(1)

Submission status: Wrong Answer

Solution code:
n,u,v = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)
print(0)

Submission status: Wrong Answer

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

from collections import deque
Q = deque()
Q.append([v-1,0])
visited=[-1]*n
visited[v-1]=0
while Q:
    now,cnt = Q.popleft()
    for nxt in link[now]:
        if visited[nxt]!=-1:
            continue
        visited[nxt]=cnt+1
        Q.append([nxt,cnt+1])
Q = deque()
Q.append([u-1,0])
v_taka=[-1]*n
v_taka[u-1]=0
while Q:
    now,cnt = Q.popleft()
    for nxt in link[now]:
        if v_taka[nxt]!=-1:
            continue
        if visited[nxt] <= cnt+1:
            continue
        v_taka[nxt]=cnt+1
        Q.append([nxt,cnt+1])

import numpy as np
ind = link[np.argsort(np.array(v_taka))[-1]]
print(visited[ind[0]])

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    sys.setrecursionlimit(100000000)

    n,u,v=map(int,input().split())
    u-=1
    v-=1
    tree=[[] for i in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        a-=1
        b-=1
        tree[a].append(b)
        tree[b].append(a)
    
    depth_u=[0]*n #uからの距離
    depth_v=[0]*n #vからの距離
    
    def dfs1(i,before=-1):
        for e in tree[i]:
            if e!=before:
                depth_u[e]=depth_u[i]+1
                dfs1(e,i)
    
    def dfs2(i,before=-1):
        for e in tree[i]:
            if e!=before:
                depth_v[e]=depth_v[i]+1
                dfs2(e,i)
    
    dfs1(u)
    dfs2(v)
    
    ans=0
    for i in range(n):
        if len(tree[i])==1:
            if depth_u[i]<depth_v[i]:
                ans=depth_v[i]-1
    print(ans)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from functools import lru_cache
    import sys
    input=sys.stdin.readline
    sys.setrecursionlimit(100000000)

    n,u,v=map(int,input().split())
    u-=1
    v-=1
    tree=[[] for i in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        a-=1
        b-=1
        tree[a].append(b)
        tree[b].append(a)
    
    depth=[0]*n
    depth[v]=0
    def dfs(i,before=-1):
        for e in tree[i]:
            if e!=before:
                depth[e]=depth[i]+1
                dfs(e,i)
    dfs(v)
    #print(depth)
    
    max_depth=[-1]*n
    max_depth[v]=0   
    @lru_cache(maxsize=None)
    def dfs2(i,before=-1):
        t=-1
        for e in tree[i]:
            if e!=before:
                t=max(t,dfs2(e,i))
        if t!=-1:
            max_depth[i]=t
            return max_depth[i]
        else:
            max_depth[i]=depth[i]
            return max_depth[i]
            
    dfs2(v)   
    #print(max_depth)
    
    lim=depth[u]
    i,key=u,u
    while i!=v:
        if 2*depth[i]<lim and max_depth[key]<max_depth[i]:
            key=i
            
        for e in tree[i]:
            if depth[e]<depth[i]:
                i=e
                break
                
    print(max_depth[key]-1) 
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from functools import lru_cache
    import sys
    input=sys.stdin.readline
    sys.setrecursionlimit(1000000)

    n,u,v=map(int,input().split())
    u-=1
    v-=1
    tree=[[] for i in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        a-=1
        b-=1
        tree[a].append(b)
        tree[b].append(a)
    
    depth=[0]*n
    depth[v]=0
    def dfs(i,before=-1):
        for e in tree[i]:
            if e!=before:
                depth[e]=depth[i]+1
                dfs(e,i)
    dfs(v)
    #print(depth)
    
    max_depth=[-1]*n
    max_depth[v]=0   
    @lru_cache(maxsize=None)
    def dfs2(i,before=-1):
        t=-1
        for e in tree[i]:
            if e!=before:
                t=max(t,dfs2(e,i))
        if t!=-1:
            max_depth[i]=t
            return max_depth[i]
        else:
            max_depth[i]=depth[i]
            return max_depth[i]
            
    dfs2(v)   
    #print(max_depth)
    
    lim=depth[u]
    i,key=u,u
    ans=0
    while i!=v:
        tmp=max_depth[i]+lim-2*depth[i]
        if 2*depth[i]<lim and ans<tmp:
            ans=tmp
            key=i
        for e in tree[i]:
            if depth[e]<depth[i]:
                i=e
                break
    if ans==0:
        print(depth[u]//2)
    else:
        print(max_depth[key]-1) 
if __name__=='__main__':
    main()