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:
N, u, v = map(int, input().split())
L = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    L[a - 1].append(b - 1)
    L[b - 1].append(a - 1)

Leaf = []  # 葉かどうかを記録する
for i in range(N):
    c = 0
    for j in L[i]:
        c = c + 1
    if c == 1:
        Leaf.append(True)
    else:
        Leaf.append(False)

UD = [0 for i in range(N)]  # 各頂点のuからの距離
UD[u - 1] = -1  # 0でないなら訪問済みとする
M = L[u - 1]  # 次に訪れるノードのリスト
d = 1  # uからの距離
while True:
    new_M = []
    for i in M:
        if UD[i] == 0:  # 0 ならiに隣接するノードをnew_Mに追加
            UD[i] = d
            for j in L[i]:
                new_M.append(j)
        else:
            pass
    M = new_M
    if len(M) == 0:
        break
    d = d + 1
UD[u-1] = 0

VD = [0 for i in range(N)]
VD[v-1] = -1
M = L[v-1]
d = 1

while True:
    new_M = []
    for i in M:
        if VD[i] == 0:  # 0 ならiに隣接するノードをnew_Mに追加
            VD[i] = d
            for j in L[i]:
                new_M.append(j)
        else:
            pass
    M = new_M
    if len(M) == 0:
        break
    d = d + 1
VD[v-1] = 0




d = -1
index = u-1
# vよりもuの方が近く,最もuから離れている葉を見つける
for i in range(N):
    if Leaf[i]:
        if UD[i] < VD[i]:
            if UD[i] > d:
                d = UD[i]
                index = i

print(d + (VD[index] - UD[index])//2)

Submission status: Wrong Answer

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

# 再帰上限を引き上げる
sys.setrecursionlimit(10**6)

# G:graph, cr:current node, seen:is seen?, dist:out;each distance
def dfs_u(G,cr,seen,dist):
	seen[cr] = 1
	for i in G[cr]: #G[cr]から行ける各頂点へ
		if seen[i] == 0: #まだ通っていなかったら
			dist[i] = dist[cr]+1
			dfs_u(G,i,seen,dist)
def dfs_v(G,cr,seen,dist):
	seen[cr] = 1
	for i in G[cr]: #G[cr]から行ける各頂点へ
		if seen[i] == 0: #まだ通っていなかったら
			dist[i] = dist[cr]+1
			dfs_v(G,i,seen,dist)

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

u,v = u-1,v-1

a = [[] for i in range(n)]

for i in range(n-1):
	# 配列indexは0開始だからinputは-1
	l,m = (int(x)-1 for x in input().split())
	a[l].append(m)
	a[m].append(l)

# v視点のdistを調べる
dist_u = [0]*n
dfs_u(a,u,[0]*n,dist_u)
# u視点のdistを調べる
dist_v = [0]*n
dfs_v(a,v,[0]*n,dist_v)

for i in range(n):
	if dist_u[i] >= dist_v[i]: # vが追いつける距離なら
		dist_u[i] = -1

print(dist_v[dist_u.index(max(dist_u))] - 1)

Submission status: Wrong Answer

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

Leaf = []  # 葉かどうかを記録する
for i in range(N):
    c = 0
    for j in L[i]:
        c = c + 1
    if c == 1:
        Leaf.append(True)
    else:
        Leaf.append(False)

UD = [0 for i in range(N)]  # 各頂点のuからの距離
UD[u - 1] = -1  # 0でないなら訪問済みとする
M = L[u - 1]  # 次に訪れるノードのリスト
d = 1  # uからの距離
while True:
    new_M = []
    for i in M:
        if UD[i] == 0:  # 0 ならiに隣接するノードをnew_Mに追加
            UD[i] = d
            for j in L[i]:
                new_M.append(j)
        else:
            pass
    M = new_M
    if len(M) == 0:
        break
    d = d + 1
UD[u-1] = 0

VD = [0 for i in range(N)]
VD[v-1] = -1
M = L[v-1]
d = 1

while True:
    new_M = []
    for i in M:
        if VD[i] == 0:  # 0 ならiに隣接するノードをnew_Mに追加
            VD[i] = d
            for j in L[i]:
                new_M.append(j)
        else:
            pass
    M = new_M
    if len(M) == 0:
        break
    d = d + 1
VD[v-1] = 0

dis_u_v = UD[v-1]//2


d = -1
index = u-1
# vよりもuの方が近く,最もuから離れている葉を見つける
for i in range(N):
    if Leaf[i]:
        if UD[i] <= VD[i]:
            if UD[i] > d:
                d = UD[i]
                index = i

print(d + (VD[index] - UD[index])//2)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
# 再帰上限を引き上げる
sys.setrecursionlimit(10**6)
# G:graph, cr:current node, seen:is seen?, dist:out;each distance
def dfs(G,cr,seen,dist):
	seen[cr] = 1
	for i in G[cr]: #G[cr]から行ける各頂点へ
		if seen[i] == 0: #まだ通っていなかったら
			dist[i] = dist[cr]+1
			dfs(G,i,seen,dist)


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

u,v = u-1,v-1

a = [[] for i in range(n)]

for i in range(n-1):
	# 配列indexは0開始だからinputは-1
	l,m = ( int(x)-1 for x in input().split() )
	a[l].append(m)
	a[m].append(l)

# v視点のdistを調べる
dist_u = [0]*n
dfs(a,u,[0]*n,dist_u)
# u視点のdistを調べる
dist_v = [0]*n
dfs(a,v,[0]*n,dist_v)

for i in range(n):
	if dist_u[i] >= dist_v[i]: # vが追いつける距離なら
		dist_u[i] = -1

print(dist_v[dist_u.index(max(dist_u))] - 1)

Submission status: Wrong Answer

Solution code:
import heapq
import numpy as np
N,u,v = map(int,input().split())
u -= 1
v -= 1

q = []
d = np.full([N], np.inf)
d[v] = 0
G = [0]*N
for i in range(N-1):
    e1,e2 = map(int, input().split())
    e1 -= 1
    e2 -= 1
    if G[e1] == 0:
        G[e1] = [e2]
    else:
        G[e1].append(e2)
    if G[e2] == 0:
        G[e2] = [e1]
    else:
        G[e2].append(e1)

if G[u]==[v]:
    ans = 0
else:    
    
    heapq.heappush(q,[0, v])
    d[v] = 0
    
    while q!=[]:
        p = heapq.heappop(q)
        pv = p[1]
        if d[pv] < p[0] :
            continue
        for i in range(len(G[pv])):
            eto = G[pv][i]
            if d[eto] > d[pv] + 1:
                 d[eto] = d[pv] + 1
                 heapq.heappush(q, [d[eto], eto])
    ans = int(np.amax(d)-1)
    
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
import numpy as np
N,u,v = map(int,input().split())
u -= 1
v -= 1

q = []
d = np.full([N], np.inf)
d[v] = 0
G = [0]*N
for i in range(N-1):
    e1,e2 = map(int, input().split())
    e1 -= 1
    e2 -= 1
    if G[e1] == 0:
        G[e1] = [e2]
    else:
        G[e1].append(e2)
    if G[e2] == 0:
        G[e2] = [e1]
    else:
        G[e2].append(e1)
    
    
heapq.heappush(q,[0, v])
d[v] = 0

while q!=[]:
    p = heapq.heappop(q)
    pv = p[1]
    if d[pv] < p[0] :
        continue
    for i in range(len(G[pv])):
        eto = G[pv][i]
        if d[eto] > d[pv] + 1:
             d[eto] = d[pv] + 1
             heapq.heappush(q, [d[eto], eto])

print(int(np.amax(d)-1))

Submission status: Wrong Answer

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

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d=[float("inf")]*n
    used=[False]*n
    d[s]=0
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v==-1):
               v=i
            elif (not used[i]) and d[i]<d[v]:
                v=i
        if v==-1:
               break
        used[v]=True
               
        for j in range(n):
               d[j]=min(d[j],d[v]+cost[v][j])
    return d

n=N
w=N-1
cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(w):
    x,y = map(int,input().split())
    x-=1
    y-=1
    cost[x][y] = 1
    cost[y][x] = 1

ni=dijkstra(u-1,n,w,cost)
ou=dijkstra(v-1,n,w,cost)
#print(ni)
#print(ou)

c=0
d=ni[v-1]
for i in range(N):
    if ni[i]<ou[i]:
        c=max(c,ni[i])
#print(d,c)
if c==0:
    if d%2==0:
        c=1
else:
    if d%2==0:
        c-=1
print(c)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

neighbors = [[i] for i in range(N + 1)]

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


def BFS(neighbors, v):
    q = deque([v])
    cost = {v: 0}
    count = 0
    visited = set([v])
    while q:
        t = q.popleft()
        visited.add(t)
        count += 1
        nodes = neighbors[t][1:]
        for n in nodes:
            if n not in visited:
                cost[n] = count
                q.append(n)

    return cost

u_cost = BFS(neighbors, u)
v_cost = BFS(neighbors, v)

ans = 0
for i in range(1, N):
    if u_cost[i] <= v_cost[i]:
        ans = max(ans, v_cost[i])

print(ans - 1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

neighbors = [[i] for i in range(N + 1)]

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


def BFS(neighbors, v):
    q = deque([v])
    cost = {v: 0}
    count = 0
    visited = set([v])
    while q:
        t = q.popleft()
        visited.add(t)
        count += 1
        nodes = neighbors[t][1:]
        for n in nodes:
            if n not in visited:
                cost[n] = count
                q.append(n)

    return cost

u_cost = BFS(neighbors, u)
v_cost = BFS(neighbors, v)

ans = 0
for i in range(1, N):
    if u_cost[i] < v_cost[i]:
        ans = max(ans, v_cost[i])

print(ans - 1)

Submission status: Wrong Answer

Solution code:
from collections import deque, Counter

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

neighbors = [[i] for i in range(N + 1)]

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


def BFS(neighbors, v):
    q = deque([v])
    cost = Counter({v: 0})
    count = 0
    visited = set([v])
    while q:
        t = q.popleft()
        visited.add(t)
        count += 1
        nodes = neighbors[t][1:]
        for n in nodes:
            if n not in visited:
                cost[n] = count
                q.append(n)

    return cost

u_cost = BFS(neighbors, u)
v_cost = BFS(neighbors, v)

ans = 0
for i in range(N):
    if u_cost[i] < v_cost[i]:
        ans = max(ans, v_cost[i])

print(ans - 1)

Submission status: Wrong Answer

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

from collections import deque

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

queT = deque()
queA = deque()

checkT = [-1] * (N + 1)
checkA = [-1] * (N + 1)

checkT[u] = 0
checkA[v] = 0

queT.append(u)
queA.append(v)
flag = True
while queT or queA: #どちらかが生きているとき
    tmp_lst = []
    while queT:
        tmp = queT.popleft()
        d = checkT[tmp]
        for next_ in G[tmp]:
            if checkT[next_] == -1:
                if checkA[next_] != -1:
                    flag = False
                    turn = True #高橋くんが動くとぶつかる
                    break
                checkT[next_] = d + 1
                tmp_lst.append(next_)
        if not flag:
            break
    if not flag:
        break
    for i in tmp_lst:
        queT.append(i)
    
    tmp_lst = []
    while queA:
        tmp = queA.popleft()
        d = checkA[tmp]
        for next_ in G[tmp]:
            if checkA[next_] == -1:
                if checkT[next_] != -1:
                    flag = False
                    turn = False #青木くんが動くとぶつかる
                    break
                checkA[next_] = d + 1
                tmp_lst.append(next_)
        if not flag:
            break
    if not flag:
        break
    for i in tmp_lst:
        queA.append(i)

# print (checkT)
# print (checkA)
# print (d)
# print (turn)
# print (tmp) #現在の場所
#ここまでで二人がギリギリまで近づく位置と、どちらが動いたらぶつかるかが分かる

ans = 0
check = [-1] * (N + 1)
check[tmp] = 0
stack = [tmp]
while stack:
    tmp1 = stack.pop()
    tmp_d = check[tmp1]
    # flag = True
    for next_ in G[tmp1]:
        if check[next_] == -1 and checkA[next_] == -1:
            check[next_] = tmp_d + 1
            stack.append(next_)
            # flag = False
    # if flag:
    ans = max(ans, tmp_d)

# print (check)
if turn:
    print (max(d + ans, 0))
else:
    print (max(d + ans - 1, 0))

Submission status: Wrong Answer

Solution code:
#1-index
import sys
input = sys.stdin.readline

from collections import deque

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

queT = deque()
queA = deque()

checkT = [-1] * (N + 1)
checkA = [-1] * (N + 1)

checkT[u] = 0
checkA[v] = 0

queT.append(u)
queA.append(v)
flag = True
while queT or queA: #どちらかが生きているとき
    tmp_lst = []
    while queT:
        tmp = queT.popleft()
        d = checkT[tmp]
        for next_ in G[tmp]:
            if checkT[next_] == -1:
                if checkA[next_] != -1:
                    flag = False
                    turn = True #高橋くんが動くとぶつかる
                    break
                checkT[next_] = d + 1
                tmp_lst.append(next_)
        if not flag:
            break
    if not flag:
        break
    for i in tmp_lst:
        queT.append(i)
    
    tmp_lst = []
    while queA:
        tmp = queA.popleft()
        d = checkA[tmp]
        for next_ in G[tmp]:
            if checkA[next_] == -1:
                if checkT[next_] != -1:
                    flag = False
                    turn = False #青木くんが動くとぶつかる
                    break
                checkA[next_] = d + 1
                tmp_lst.append(next_)
        if not flag:
            break
    if not flag:
        break
    for i in tmp_lst:
        queA.append(i)

# print (checkT)
# print (checkA)
# print (d)
# print (turn)
# print (tmp) #現在の場所
#ここまでで二人がギリギリまで近づく位置と、どちらが動いたらぶつかるかが分かる

ans = 0
check = [-1] * (N + 1)
check[tmp] = 0
stack = [tmp]
while stack:
    tmp1 = stack.pop()
    tmp_d = check[tmp1]
    # flag = True
    for next_ in G[tmp1]:
        if check[next_] == -1 and checkA[next_] == -1:
            check[next_] = tmp_d + 1
            stack.append(next_)
            # flag = False
    # if flag:
    ans = max(ans, tmp_d)

# print (check)
print (d + ans - 2)
exit()
if turn:
    print (max(d + ans, 0))
else:
    print (max(d + ans - 1, 0))

Submission status: Wrong Answer

Solution code:
#1-index
import sys
input = sys.stdin.readline

from collections import deque

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

queT = deque()
queA = deque()

checkT = [-1] * (N + 1)
checkA = [-1] * (N + 1)

checkT[u] = 0
checkA[v] = 0

queT.append(u)
queA.append(v)
flag = True
while queT or queA: #どちらかが生きているとき
    tmp_lst = []
    while queT:
        tmp = queT.popleft()
        d = checkT[tmp]
        for next_ in G[tmp]:
            if checkT[next_] == -1:
                if checkA[next_] != -1:
                    flag = False
                    turn = True #高橋くんが動くとぶつかる
                    break
                checkT[next_] = d + 1
                tmp_lst.append(next_)
        if not flag:
            break
    if not flag:
        break
    for i in tmp_lst:
        queT.append(i)
    
    tmp_lst = []
    while queA:
        tmp = queA.popleft()
        d = checkA[tmp]
        for next_ in G[tmp]:
            if checkA[next_] == -1:
                if checkT[next_] != -1:
                    flag = False
                    turn = False #青木くんが動くとぶつかる
                    break
                checkA[next_] = d + 1
                tmp_lst.append(next_)
        if not flag:
            break
    if not flag:
        break
    for i in tmp_lst:
        queA.append(i)

# print (checkT)
# print (checkA)
# print (d)
# print (turn)
# print (tmp) #現在の場所
#ここまでで二人がギリギリまで近づく位置と、どちらが動いたらぶつかるかが分かる

ans = 0
check = [-1] * (N + 1)
check[tmp] = 0
stack = [tmp]
while stack:
    tmp1 = stack.pop()
    tmp_d = check[tmp1]
    # flag = True
    for next_ in G[tmp1]:
        if check[next_] == -1 and checkA[next_] == -1:
            check[next_] = tmp_d + 1
            stack.append(next_)
            # flag = False
    # if flag:
    ans = max(ans, tmp_d)

# print (check)
print (d + ans)
exit()
if turn:
    print (max(d + ans, 0))
else:
    print (max(d + ans - 1, 0))

Submission status: Wrong Answer

Solution code:
#1-index
import sys
input = sys.stdin.readline

from collections import deque

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

queT = deque()
queA = deque()

checkT = [-1] * (N + 1)
checkA = [-1] * (N + 1)

checkT[u] = 0
checkA[v] = 0

queT.append(u)
queA.append(v)
flag = True
while queT or queA: #どちらかが生きているとき
    tmp_lst = []
    while queT:
        tmp = queT.popleft()
        d = checkT[tmp]
        for next_ in G[tmp]:
            if checkT[next_] == -1:
                if checkA[next_] != -1:
                    flag = False
                    turn = True #高橋くんが動くとぶつかる
                    break
                checkT[next_] = d + 1
                tmp_lst.append(next_)
        if not flag:
            break
    if not flag:
        break
    for i in tmp_lst:
        queT.append(i)
    
    tmp_lst = []
    while queA:
        tmp = queA.popleft()
        d = checkA[tmp]
        for next_ in G[tmp]:
            if checkA[next_] == -1:
                if checkT[next_] != -1:
                    flag = False
                    turn = False #青木くんが動くとぶつかる
                    break
                checkA[next_] = d + 1
                tmp_lst.append(next_)
        if not flag:
            break
    if not flag:
        break
    for i in tmp_lst:
        queA.append(i)

# print (checkT)
# print (checkA)
# print (d)
# print (turn)
# print (tmp) #現在の場所
#ここまでで二人がギリギリまで近づく位置と、どちらが動いたらぶつかるかが分かる

ans = 0
check = [-1] * (N + 1)
check[tmp] = 0
stack = [tmp]
while stack:
    tmp1 = stack.pop()
    tmp_d = check[tmp1]
    # flag = True
    for next_ in G[tmp1]:
        if check[next_] == -1 and checkA[next_] == -1:
            check[next_] = tmp_d + 1
            stack.append(next_)
            # flag = False
    # if flag:
    ans = max(ans, tmp_d)

# print (check)

if turn:
    print (max(d + ans, 0))
else:
    print (max(d + ans - 1, 0))

Submission status: Wrong Answer

Solution code:
from collections import deque, Counter

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

neighbors = [[i] for i in range(N + 1)]

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


def BFS(neighbors, v):
    q = deque([v])
    cost = Counter({v: 0})
    count = 0
    visited = set([v])
    while q:
        t = q.popleft()
        visited.add(t)
        count += 1
        nodes = neighbors[t][1:]
        for n in nodes:
            if n not in visited:
                cost[n] = count
                q.append(n)

    return cost

u_cost = BFS(neighbors, u)
v_cost = BFS(neighbors, v)

ans = 0
for i in range(N):
    if u_cost[i] <= v_cost[i]:
        ans = max(ans, v_cost[i])

print(ans - 1)

Submission status: Wrong Answer

Solution code:
from collections import deque

INF = -1

n, t, a = map(int, input().split())
t -= 1
a -= 1
g = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v = map(lambda x: int(x) - 1, input().split())
    g[u].append(v)
    g[v].append(u)

def bfs(start):
    dist = [INF] * n
    dist[start] = 0
    q = deque([start])
    while q:
        cur = q.pop()
        for to in g[cur]:
            if dist[to] == INF:
                dist[to] = 1 + dist[cur]
                q.appendleft(to)
    return dist

distT = bfs(t)
distA = bfs(a)
ret = 0
for v in range(n):
    if distT[v] < distA[v]:
        diff = distA[v] - distT[v]
        ret = max(ret, distT[v] + diff // 2)
print(ret)

Submission status: Wrong Answer

Solution code:
from collections import deque

N,u,v=map(int,input().split()) # u,vから1を引く必要がある
a=[[] for _ in range(N)] # 0-initial
for _ in range(N-1):
    Ai,Bi=map(int,input().split())
    a[Ai-1].append(Bi-1)
    a[Bi-1].append(Ai-1)
T=u-1;A=v-1

# 方針
# Tは，Tからの距離dTがAからの距離dA以下であるような点のうち，最もdAが大きい点を目指す。
dT=[-1]*N
q=deque()
q.append(T);dT[T]=0
while q:
    u=q.popleft()
    for v in a[u]:
        if dT[v]==-1:
            dT[v]=dT[u]+1
            q.append(v)

dA=[-1]*N
q=deque()
q.append(A);dA[A]=0
while q:
    u=q.popleft()
    for v in a[u]:
        if dA[v]==-1:
            dA[v]=dA[u]+1
            q.append(v)   


print(a)
print(dT)
print(dA)

ans=0
if a[T]!=[A] and T!=A:
    for i in range(N):
        if dT[i]<dA[i] and ans<dA[i]-1:
            ans=dA[i]-1

print(ans)

Submission status: Wrong Answer

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

def tami(n, cnt):
  aoki_visited[n] = True
  aoki[n] = cnt
  for x in edge[n]:
    if aoki_visited[x] == False:
      tami(x, cnt+1)

def tami2(n, cnt):
  choku_visited[n] = True
  if cnt <= aoki[n]:
    choku[n] = cnt
    for x in edge[n]:
      if choku_visited[x] == False:
        tami2(x, cnt+1)

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

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

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

ans = 0

Submission status: Wrong Answer

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

def tami(n, cnt):
  aoki_visited[n] = True
  aoki[n] = cnt
  for x in edge[n]:
    if aoki_visited[x] == False:
      tami(x, cnt+1)

def tami2(n, cnt):
  choku_visited[n] = True
  if cnt <= aoki[n]:
    choku[n] = cnt
    for x in edge[n]:
      if choku_visited[x] == False:
        tami2(x, cnt+1)

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

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

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

ans = 0
tami(v, 0)

Submission status: Wrong Answer

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

dist_u = [-1]*N
dist_v = [-1]*N
dist_u[u] = 0
dist_v[v] = 0

from collections import deque

H = deque()
H.append(u)
while H:
    x = H.popleft()
    for nx in table[x]:
        if dist_u[nx] == -1:
            H.append(nx)
            dist_u[nx] = dist_u[x]+1

H = deque()
H.append(v)
while H:
    x = H.popleft()
    for nx in table[x]:
        if dist_v[nx] == -1:
            H.append(nx)
            dist_v[nx] = dist_v[x]+1

tmp = 0
for i in range(N):
    if dist_u[i] <= dist_v[i] and dist_u[i] > tmp:
        tmp = dist_u[i]
        memo = i
print(tmp)

Submission status: Wrong Answer

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

u_dist = [n] * n
u_dist[u] = 0
stack = [u]
while stack:
  vertex = stack.pop()
  for nxt in adj[vertex]:
    if u_dist[nxt] == n:
      u_dist[nxt] = u_dist[vertex] + 1
      stack.append(nxt)

v_dist = [n] * n
v_dist[v] = 0
stack = [v]
leaves = []
while stack:
  vertex = stack.pop()
  isleaf = True
  for nxt in adj[vertex]:
    if u_dist[nxt] == n:
      u_dist[nxt] = u_dist[vertex] + 1
      stack.append(nxt)
      isleaf = False
  if isleaf:
    leaves.append(vertex)

max_depth = 0
for leaf in leaves:
  depth = v_dist[leaf]
  if u_dist[leaf] < depth and max_depth < depth:
    max_depth = depth
    
print(max_depth - 1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
N, u, v = map(int, input().split())
u -= 1
v -= 1

G = [[] for _ in range(N)]
elens = [0] * N

for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
    elens[a] += 1
    elens[b] += 1
depths = [0] * N
dists = [0] * N


TAKAHASHI = [0] * N
AOKI = [0] * N

def dfs_aoki(cur: int, past: int, d: int):
    AOKI[cur] = d

    for nx in G[cur]:
        if nx == past:
            continue
        dfs_aoki(nx, cur, d + 1)

def dfs_takahashi(cur: int, past: int, d: int):
    TAKAHASHI[cur] = d

    for nx in G[cur]:
        if nx == past:
            continue
        dfs_aoki(nx, cur, d + 1)

dfs_takahashi(u, -1, 0)
dfs_aoki(v, -1, 0)

ans = 0

for i in range(N):
    if TAKAHASHI[i] < AOKI[i]:
        ans = max(ans, AOKI[i] - 1)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(200000)

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

# nodeの値を-1しておく
u = u-1
v = v-1

# Making Adjacency list
Adj_dict = {}
for i in range(n):
    new = {i: []}
    Adj_dict.update(new)

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

def tree_distance(Adj_dict, start, Visited, distance, Dist_list):
    
    # 現在いる位置を Visited = True に変更する
    Visited[start] = True

    # 該当するnodeの距離を記録して、distanceを1加算する
    Dist_list[start] = distance
    distance += 1

    # 訪れていないnodeに対して、dfs
    for node in Adj_dict[start]:
        if Visited[node] == False:
            tree_distance(Adj_dict, node, Visited, distance, Dist_list)
    
    return


Dist_list = [0 for _ in range(n)]
Visited = [False for _ in range(n)]
distance = 0
tree_distance(Adj_dict, u, Visited, distance, Dist_list)
Taka = Dist_list

Dist_list = [0 for _ in range(n)]
Visited = [False for _ in range(n)]
distance = 0
tree_distance(Adj_dict, v, Visited, distance, Dist_list)
Aoki = Dist_list

Taka_num = 0
node = 0
for i in range(n):
    if Aoki[i] >= Taka[i]:
        if Taka[i] >= Taka_num:
            Taka_num = Taka[i]
            node = i

# TakahashiはTaka_numのnodeへ逃げる
ans = Aoki[node] -1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

def bfs(v):
    dist = [None] * N
    
    q = [(v, 0)]
    
    while q:
        v, c = q.pop(0)
        dist[v] = c
        
        for u in G[v]:
            if not dist[u] is None: continue
            q.append((u, c+1))
    return dist

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

G = [[] for i in range(N)]

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

n = 0
m = float('inf')

for v, u in zip(v_dist, u_dist):
    if v == u: m = min(m, v)
    elif v > u: n = max(n, u)
        
if m == float('inf'): print(n)
else: print(max(n, m))

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     

def deepest_path(G, v, par = -1):
    children = G[v]
    if len(children) == 0:
        return 0
    max_path = -1
    for next_v in children:
        if next_v == par:
            continue
        max_path = max(deepest_path(G, next_v, v), max_path)
    return 1 + max_path

def main():
    N, u, v = LI()
    u -= 1
    v -= 1
    G = [[] for __ in range(N)]
    for _ in range(N-1):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)
    cnt = deepest_path(G, v) - 1
    print(cnt)

main()

Submission status: Wrong Answer

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

children = [[] for i in range(N + 1)]

for i in range(N - 1):
        children[AB[i][0]].append(AB[i][1])
        children[AB[i][1]].append(AB[i][0])

def aoki(u, v):
        atot = [[-1, 0] for i in range(N + 1)]
        atot[v][0] = 0
        q = queue.Queue()
        for i in children[v]:
                q.put([i, v])
        while not q.empty():
                nt = q.get()
                if nt[0] == u:
                        atot[nt[0]] = [atot[nt[1]][0] + 1, nt[1]]
                        break
                else:
                        for i in children[nt[0]]:
                                if atot[i][0] == -1:
                                        q.put([i, nt[0]])
                        atot[nt[0]] = [atot[nt[1]][0] + 1, nt[1]]
        bk = u
        rout = [bk]
        while atot[bk][0] > 0:
                rout.append(atot[bk][1])
                bk = atot[bk][1]

        return rout

def takahashi(u, v):
        froma = [[-1, 0] for i in range(N + 1)]
        froma[u][0] = 0
        q = queue.Queue()
        for i in children[u]:
                q.put([i, u])
        mx = -1
        while not q.empty():
                nt = q.get()
                for i in children[nt[0]]:
                        if froma[i][0] == -1 and nt[0] != v:
                                q.put([i, nt[0]])
                froma[nt[0]] = [froma[nt[1]][0] + 1, nt[1]]
                if froma[nt[0]][0] > mx:
                        g = nt[0]
                        mx = froma[nt[0]][0]
        rout = aoki(g, u)
        if rout[-2] == v:
                aw = v
                for i in children[u]:
                        if i != v:
                                aw = i
                                return aw
                if aw == v:
                        return v
        else:
                return rout[-2]

cnt = 0
while True:
        u = takahashi(u, v)
        if u == v:
                break
        r = aoki(u, v)
        if len(r) == 1:
                v = r[0]
        else:
                v = r[-2]
        if u == v:
                cnt += 1
                break
        cnt += 1
print(cnt)