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(lambda x: int(x)-1, input().split())
N += 1
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]
for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# bfs from v
dist_from_v = [-1]*N
dist_from_v[v] = 0
Q = [v]
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_v[next] == -1:
                dist_from_v[next] = dist_from_v[cur]+1
                tmp.append(next)
    Q = tmp

dst_u = -1
# bfs from u
dist_from_u = [-1]*N
dist_from_u[u] = 0
Q = [u]
cut = None
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_u[next] == -1:
                if dist_from_u[cur]+1 >= dist_from_v[next]:
                    assert cut == None
                    cut = (cur, next)
                else:
                    dist_from_u[next] = dist_from_u[cur]+1
                    tmp.append(next)
    Q = tmp


dst_u = dist_from_u.index(max(dist_from_u))
dist_u_dst = max(dist_from_u)
dist_v_dst = dist_from_v[dst_u]
# print(dist_from_v)
# print(dist_from_u)
# print(cut)
assert dist_u_dst < dist_v_dst

ans = dist_v_dst-1
print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil
N, u, v = map(lambda x: int(x)-1, input().split())
N += 1
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]
for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# bfs from v
dist_from_v = [-1]*N
dist_from_v[v] = 0
Q = [v]
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_v[next] == -1:
                dist_from_v[next] = dist_from_v[cur]+1
                tmp.append(next)
    Q = tmp

dst_u = -1
# bfs from u
dist_from_u = [-1]*N
dist_from_u[u] = 0
Q = [u]
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_u[next] == -1:
                if dist_from_u[cur]+1 >= dist_from_v[next]:
                    # print("update")
                    cut = (cur, next)
                else:
                    dist_from_u[next] = dist_from_u[cur]+1
                    tmp.append(next)
    Q = tmp


dst_u = dist_from_u.index(max(dist_from_u))
dist_u_dst = max(dist_from_u)
dist_v_dst = dist_from_v[dst_u]
# print(dist_from_v)
# print(dist_from_u)
# print(cut)
assert dist_u_dst < dist_v_dst

ans = dist_v_dst-1
print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil
N, u, v = map(lambda x: int(x)-1, input().split())
N += 1
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]
for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# bfs from v
dist_from_v = [-1]*N
dist_from_v[v] = 0
Q = [v]
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_v[next] == -1:
                dist_from_v[next] = dist_from_v[cur]+1
                tmp.append(next)
    Q = tmp

dst_u = -1
# bfs from u
dist_from_u = [-1]*N
dist_from_u[u] = 0
Q = [u]
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_u[next] == -1:
                if dist_from_u[cur]+1 >= dist_from_v[next]:
                    # print("update")
                    cut = (cur, next)
                else:
                    dist_from_u[next] = dist_from_u[cur]+1
                    tmp.append(next)
    Q = tmp


dst_u = dist_from_u.index(max(dist_from_u))
dist_u_dst = max(dist_from_u)
dist_v_dst = dist_from_v[dst_u]
# print(dist_from_v)
# print(dist_from_u)
# print(cut)
assert dist_u_dst < dist_v_dst

if (dist_v_dst-dist_u_dst) % 2 == 1:
    ans = dist_v_dst-2
else:
    ans = dist_v_dst-1
print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil
N, u, v = map(lambda x: int(x)-1, input().split())
N += 1
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]
for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# bfs from v
dist_from_v = [-1]*N
dist_from_v[v] = 0
Q = [v]
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_v[next] == -1:
                dist_from_v[next] = dist_from_v[cur]+1
                tmp.append(next)
    Q = tmp

dst_u = -1
# bfs from u
dist_from_u = [-1]*N
dist_from_u[u] = 0
Q = [u]
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_u[next] == -1:
                if dist_from_u[cur]+1 >= dist_from_v[next]:
                    # print("update")
                    cut = (cur, next)
                else:
                    dist_from_u[next] = dist_from_u[cur]+1
                    tmp.append(next)
    Q = tmp


dst_u = dist_from_u.index(max(dist_from_u))
dist_u_dst = max(dist_from_u)
dist_v_dst = dist_from_v[dst_u]
# print(dist_from_v)
# print(dist_from_u)
# print(cut)
assert dist_u_dst < dist_v_dst

if (dist_v_dst-dist_u_dst) % 2 == 0:
    ans = dist_v_dst-2
else:
    ans = dist_v_dst-1
print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil
N, u, v = map(lambda x: int(x)-1, input().split())
N += 1
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]
for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# bfs from v
dist_from_v = [-1]*N
dist_from_v[v] = 0
Q = [v]
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_v[next] == -1:
                dist_from_v[next] = dist_from_v[cur]+1
                tmp.append(next)
    Q = tmp

dst_u = -1
# bfs from u
dist_from_u = [-1]*N
dist_from_u[u] = 0
Q = [u]
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_u[next] == -1:
                if dist_from_u[cur]+1 >= dist_from_v[next]:
                    # print("update")
                    cut = (cur, next)
                else:
                    dist_from_u[next] = dist_from_u[cur]+1
                    tmp.append(next)
    Q = tmp


dst_u = dist_from_u.index(max(dist_from_u))
dist_u_dst = max(dist_from_u)
dist_v_dst = dist_from_v[dst_u]
# print(dist_from_v)
# print(dist_from_u)
# print(cut)
assert dist_u_dst < dist_v_dst

if dist_v_dst % 2 == 0:
    ans = dist_v_dst-1
else:
    ans = dist_v_dst-2
print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil
N, u, v = map(lambda x: int(x)-1, input().split())
N += 1
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]
for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# bfs from v
dist_from_v = [-1]*N
dist_from_v[v] = 0
Q = [v]
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_v[next] == -1:
                dist_from_v[next] = dist_from_v[cur]+1
                tmp.append(next)
    Q = tmp

dst_u = -1
# bfs from u
dist_from_u = [-1]*N
dist_from_u[u] = 0
Q = [u]
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_u[next] == -1:
                if dist_from_u[cur]+1 >= dist_from_v[next]:
                    # print("update")
                    cut = (cur, next)
                else:
                    dist_from_u[next] = dist_from_u[cur]+1
                    tmp.append(next)
    Q = tmp


dst_u = dist_from_u.index(max(dist_from_u))
dist_u_dst = max(dist_from_u)
dist_v_dst = dist_from_v[dst_u]
# print(dist_from_v)
# print(dist_from_u)
# print(cut)
assert dist_u_dst < dist_v_dst

if dist_v_dst % 2 == 0:
    ans = dist_v_dst
else:
    ans = dist_v_dst
print(ans-1)

Submission status: Wrong Answer

Solution code:
from math import ceil
N, u, v = map(lambda x: int(x)-1, input().split())
N += 1
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]
for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# bfs from v
dist_from_v = [-1]*N
dist_from_v[v] = 0
Q = [v]
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_v[next] == -1:
                dist_from_v[next] = dist_from_v[cur]+1
                tmp.append(next)
    Q = tmp

dst_u = -1
# bfs from u
dist_from_u = [-1]*N
dist_from_u[u] = 0
Q = [u]
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_u[next] == -1:
                if dist_from_u[cur]+1 >= dist_from_v[next]:
                    # print("update")
                    cut = (cur, next)
                else:
                    dist_from_u[next] = dist_from_u[cur]+1
                    tmp.append(next)
    Q = tmp


dst_u = dist_from_u.index(max(dist_from_u))
dist_u_dst = max(dist_from_u)
dist_v_dst = dist_from_v[dst_u]
# print(dist_from_v)
# print(dist_from_u)
# print(cut)
assert dist_u_dst < dist_v_dst

if dist_v_dst % 2 == 0:
    ans = dist_v_dst
else:
    ans = dist_v_dst
print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil
N, u, v = map(lambda x: int(x)-1, input().split())
N += 1
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]
for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# bfs from v
dist_from_v = [-1]*N
dist_from_v[v] = 0
Q = [v]
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_v[next] == -1:
                dist_from_v[next] = dist_from_v[cur]+1
                tmp.append(next)
    Q = tmp

dst_u = -1
# bfs from u
dist_from_u = [-1]*N
dist_from_u[u] = 0
Q = [u]
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_u[next] == -1:
                if dist_from_u[cur]+1 >= dist_from_v[next]:
                    # print("update")
                    cut = (cur, next)
                else:
                    dist_from_u[next] = dist_from_u[cur]+1
                    tmp.append(next)
    Q = tmp


dst_u = dist_from_u.index(max(dist_from_u))
dist_u_dst = max(dist_from_u)
dist_v_dst = dist_from_v[dst_u]
# print(dist_from_v)
# print(dist_from_u)
# print(cut)
assert dist_u_dst < dist_v_dst

if dist_v_dst % 2 == 0:
    ans = dist_u_dst+(dist_v_dst-dist_u_dst)//2
else:
    ans = dist_u_dst+dist_v_dst-dist_u_dst
print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil
N, u, v = map(lambda x: int(x)-1, input().split())
N += 1
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]
for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# bfs from v
dist_from_v = [-1]*N
dist_from_v[v] = 0
Q = [v]
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_v[next] == -1:
                dist_from_v[next] = dist_from_v[cur]+1
                tmp.append(next)
    Q = tmp

dst_u = -1
# bfs from u
dist_from_u = [-1]*N
dist_from_u[u] = 0
Q = [u]
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_u[next] == -1:
                if dist_from_u[cur]+1 >= dist_from_v[next]:
                    # print("update")
                    cut = (cur, next)
                else:
                    dist_from_u[next] = dist_from_u[cur]+1
                    tmp.append(next)
    Q = tmp


dst_u = dist_from_u.index(max(dist_from_u))
dist_u_dst = max(dist_from_u)
dist_v_dst = dist_from_v[dst_u]
# print(dist_from_v)
# print(dist_from_u)
# print(cut)
assert dist_u_dst < dist_v_dst

ans = dist_u_dst+ceil((dist_v_dst-dist_u_dst)/2)
print(ans)

Submission status: Wrong Answer

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

# bfs from v
dist_from_v = [-1]*N
dist_from_v[v] = 0
Q = [v]
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_v[next] == -1:
                dist_from_v[next] = dist_from_v[cur]+1
                tmp.append(next)
    Q = tmp

dst_u = -1
# bfs from u
dist_from_u = [-1]*N
dist_from_u[u] = 0
Q = [u]
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_u[next] == -1:
                if dist_from_u[cur]+1 >= dist_from_v[next]:
                    # print("update")
                    cut = (cur, next)
                else:
                    dist_from_u[next] = dist_from_u[cur]+1
                    tmp.append(next)
    Q = tmp


dst_u = dist_from_u.index(max(dist_from_u))
dist_u_dst = max(dist_from_u)
dist_v_dst = dist_from_v[dst_u]
# print(dist_from_v)
# print(dist_from_u)
# print(cut)

if dist_from_v[u] % 2 == 0:
    ans = dist_u_dst+1
    # print("ans->", dist_u_dst+1)
else:
    ans = dist_u_dst
    # print("ans->", dist_u_dst)
print(ans)

Submission status: Wrong Answer

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

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

taka = [0] * N
aoki = [0] * N

def dfs(v, pre, cost, i):
    for e in edge[v]:
        if e == pre:
            continue
        cost = dfs(e, v, cost, i+1)
    cost[v] = i
    return cost

taka = dfs(u, -1, [0] * N, 0)
aoki = dfs(v, -1, [0] * N, 0)

m = 0
for i in range(N):
    if taka[i] < aoki[i]:
        m = max(m, aoki[i])

print(m)

Submission status: Wrong Answer

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

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

taka = [0] * N
aoki = [0] * N

def dfs(v, pre, cost, i):
    for e in edge[v]:
        if e == pre:
            continue
        cost = dfs(e, v, cost, i+1)
    cost[v] = i
    return cost

taka = dfs(u, -1, [0] * N, 0)
aoki = dfs(v, -1, [0] * N, 0)

m = 0
for i in range(N):
    if taka[i] < aoki[i]:
        m = max(m, taka[i])

print(m)

Submission status: Wrong Answer

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

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

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

# process
def getdis(idx, num, dis):
    dis[idx] = num
    for i in tree[idx] :
        if dis[i] < 0:
            dis = getdis(i, num+1, dis)
    return dis

dis_u = [-1]*n
dis_u = getdis(u-1, 0, dis_u)
dis_v = [-1]*n
dis_v = getdis(v-1, 0, dis_v)

ans = 0
for i in range(n):
    if dis_u[i] == dis_v[i] or dis_u[i]+1 == dis_v[i]:
        ans = max(ans, dis_v[i]-1)

# output
print(ans)

Submission status: Wrong Answer

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

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

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

# process
def getdis(idx, num, dis):
    dis[idx] = num
    for i in tree[idx] :
        if dis[i] < 0:
            dis = getdis(i, num+1, dis)
    return dis

dis_u = [-1]*n
dis_u = getdis(u-1, 0, dis_u)
dis_v = [-1]*n
dis_v = getdis(v-1, 0, dis_v)

print(dis_u)
print(dis_v)

ans = 0
for i in range(n):
    if dis_u[i] == dis_v[i] or dis_u[i]+1 == dis_v[i]:
        ans = max(ans, dis_v[i]-1)

# output
print(ans)

Submission status: Wrong Answer

Solution code:
n,u,v = map(int,input().split())
u,v = u-1,v-1
link = [[] for i in range(n)]
for i in range(n-1):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  link[a].append(b)
  link[b].append(a)
tree = [[] for i in range(n)]
for i in [u,v]:
  stack = [i]
  vi = [0] * n
  tree[i].append(0)
  vi[i] = 1
  while stack:
    cur = stack.pop()
    for j in link[cur]:
      if vi[j] == 0:
        stack.append(j)
        vi[j] = 1
        tree[j].append(tree[cur][-1]+1)
m = 0
c = 0
for i,j in tree:
  print(i,j)
  if i < j:
    if m < j:
      m = j
      #c = (j-i) % 2
print(m-1)

Submission status: Wrong Answer

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

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

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

print(tree)

# process
def f(line, maxlen):
    print(line)
    edges = tree[line[-1]]
    if len(line) == 1 or len(edges) > 1:
        for e in edges :
            if len(line) ==1 or not e == line[-2]:
                l = line[:]
                l.append(e)
                maxlen = f(l, maxlen)
        return maxlen

    else:
        if len(line) > maxlen: maxlen = len(line)
        return maxlen

# output
print(f([v-1], 0)-2)

Submission status: Wrong Answer

Solution code:
from collections import deque 
import sys
input = sys.stdin.readline  #文字列入力では注意！

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

def bfs(start):
    q = deque()
    q.append([start,0])
    visited = set()
    lis = [0]*N
    while q:
        now,dis = q.popleft()
        if now in visited:
            continue
        lis[now] = dis
        visited.add(now)
        for node in tree[now]:
            q.append([node,dis+1])    
    return lis
ut = bfs(u)
vt = bfs(v)

q = deque()
q.append(0)
visited = set()
ans = 0
while q:
    now = q.popleft()
    if now in visited:
        continue
    elif ut[now] == vt[now]:
        ans = max(ans,vt[now])
        continue
    visited.add(now)
    if len(tree[now]) == 1:
        matsu = now
        kaisu = vt[matsu]-1
        ans = max(ans,kaisu)
    for child in tree[now]:
        q.append(child)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque 
import sys
input = sys.stdin.readline  #文字列入力では注意！

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

def bfs(start):
    q = deque()
    q.append([start,0])
    visited = set()
    lis = [0]*N
    while q:
        now,dis = q.popleft()
        if now in visited:
            continue
        lis[now] = dis
        visited.add(now)
        for node in tree[now]:
            q.append([node,dis+1])    
    return lis
ut = bfs(u)
vt = bfs(v)

q = deque()
q.append(0)
visited = set()
ans = 0
print(ut)
print(vt)
while q:
    now = q.popleft()
    if now in visited:
        continue
    elif ut[now] == vt[now]:
        ans = max(ans,vt[now])
        continue
    visited.add(now)
    if len(tree[now]) == 1:
        matsu = now
        kaisu = vt[matsu]-1
        ans = max(ans,kaisu)
    for child in tree[now]:
        q.append(child)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque 
import sys
input = sys.stdin.readline  #文字列入力では注意！

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

def bfs(start):
    q = deque()
    q.append([start,0])
    visited = set()
    lis = [0]*N
    while q:
        now,dis = q.popleft()
        if now in visited:
            continue
        lis[now] = dis
        visited.add(now)
        for node in tree[now]:
            q.append([node,dis+1])    
    return lis
ut = bfs(u)
vt = bfs(v)

q = deque()
q.append(0)
visited = set()
ans = 0
while q:
    now = q.popleft()
    if now in visited:
        continue
    elif ut[now] == vt[now]:
        ans = max(ans,vt[now])
    visited.add(now)
    if len(tree[now]) == 1:
        matsu = now
        kaisu = vt[matsu]-1
        ans = max(ans,kaisu)
    for child in tree[now]:
        q.append(child)
print(ans)

Submission status: Wrong Answer

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

import queue

dist_t = [0] * n
dist_a = [0] * n

elb_t = [0] * n
elb_a = [0] * n

ab = [[] for j in range(n)]

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

u -= 1
v -= 1

q = queue.Queue()

q.put(u)
elb_t[u] = 1
dist_t[u] = 0

while not q.empty():
    tmp = q.get()
    for i in range(len(ab[tmp])):
        idx = ab[tmp][i]
        if elb_t[idx] != 1:
            dist_t[idx] = dist_t[tmp] + 1
            elb_t[idx] = 1
            q.put(idx)

q = queue.Queue()

q.put(v)
elb_a[v] = 1
dist_a[v] = 0

while not q.empty():
    tmp = q.get()
    for i in range(len(ab[tmp])):
        idx = ab[tmp][i]
        if elb_a[idx] != 1:
            dist_a[idx] = dist_a[tmp] + 1
            elb_a[idx] = 1
            q.put(idx)

ans = 0

for i in range(n):
    if dist_t[i] > dist_a[i]:
        ans = max(ans,dist_t[i]-1)

print(ans)

Submission status: Wrong Answer

Solution code:
n = input()    
m = n.split()
p = [int(i) for i in m]
from collections import deque
list = []
for i in range(p[0]-1): #因数注意！
    n = input()    
    m = n.split()
    q = [int(i) for i in m] #1列の数列をリスト化
    list.append(q)
l = [[] for i in range(p[0]+1)]
for pi in list:  #0-originedに注意
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])
sousa = deque([[p[2],0,0]]) #[捜査対象ノード,親ノード,そのノードの距離]
node = [[] for i in range(p[0])] #n番目のリストにn+1について[親ノード,rootからの距離,子ノード]
while len(sousa) != 0:
    a = sousa.popleft()
    b = l[a[0]]
    if a[1]!=0:
        b.remove(a[1])
    if len(b) == 0:
        pass
    else:
        for i in b:
            sousa.append([i,a[0],a[2]+1])
    node[a[0]-1] = [a[1]] + [a[2]] + b
dis = node[p[1]-1][1]
takahashi = p[1]
max = 0
hate = 0
for i in range((dis+1)//2):
    tansaku = deque([[takahashi,0]])
    if i >= 1:
        kitatoko = takahashi
        takahashi = node[takahashi-1][0]
        a = tansaku.popleft()
        b = node[takahashi-1][2:]
        b.remove(kitatoko)
        if len(b) == 0:
            continue
        else:
            for j in b:
                tansaku.append([j,1])

    while len(tansaku) != 0:
        a = tansaku.popleft()
        b = node[a[0]-1][2:]
        if len(b) == 0:
            pass
        else:
            for j in b:
                tansaku.append([j,a[1]+1])

    if max < a[1]:
        max = a[1]
        hate = a[0]
if dis == 2 and max == 0:
    print("1")
else:
    print(node[a[0]-1][1]-1)

Submission status: Wrong Answer

Solution code:
N,U,V=map(int,input().split())
if U==V:
    print(0)
    exit()

G=[[]*N 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)


from collections import deque
que=deque()
que.append([V-1,0])
#print(que)
visited=[0]*(N+1)
visited[V-1]=1
fin=[]
while que:
    vcnt=que.pop()
    #print(vcnt)
    v=vcnt[0]
    cnt=vcnt[1]
    if v==U:
        cnt_U=cnt
    #print(v,cnt)
    flg=True
    for u in G[v]:
        if visited[u]==0:
            que.appendleft([u,cnt+1])
            visited[u]=1
            flg=False

    if flg:
        fin.append([v,cnt])
fin.sort(key=lambda x:x[1])

print(fin[-1][1]-1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

# def find_distances(edge_dict, node, distances):
#     for end in edge_dict[node]:
#         if distances[end] < 0:
#             distances[end] = distances[node] + 1
#             distances = find_distances(edge_dict, end, distances)

#     return distances


def find_distances(edge_dict, node, V):
    distances = [-1] * V
    stack = [(0, node)]

    while stack:
        dist, node = stack.pop()
        if distances[node] > 0:
            continue

        distances[node] = dist
        for end in edge_dict[node]:
            stack.append((dist + 1, end))

    return distances

if __name__ == "__main__":
    V, T, A = map(int, input().split())
    T -= 1
    A -= 1
    edge_dict = defaultdict(list)

    for _ in range(V - 1):
        start, end = map(int, input().split())
        edge_dict[start - 1].append(end - 1)
        edge_dict[end - 1].append(start - 1)
    
    dist_T = [-1] * V
    dist_T[T] = 0
    dist_T = find_distances(edge_dict, T, V)

    dist_A = [-1] * V
    dist_A[A] = 0
    dist_A = find_distances(edge_dict, A, V)

    max_dist = 0
    for i in range(V):
        if dist_T[i] <= dist_A[i]:
            max_dist = max(max_dist, dist_A[i])
    
    print(max_dist - 1)

Submission status: Wrong Answer

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

def bfs(node):
	sta = [node]
	dis = [-1] * (N + 1)
	dis[node] = 0
	while sta:
		no = sta.pop(0)
		tempD = dis[no] + 1
		for tempN in tree[no]:
			if dis[tempN] < 0:
				dis[tempN] = tempD
				sta.append(tempN)
	else:
		return dis

disU = bfs(u)
disV = bfs(v)
ans = 0

for u_, v_ in zip(disU[1:], disV[1:]):
	if u_ < v_:
			ans = max(u_, v_) - 1
else:
	print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**6)

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

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

for i in range(N-1):
    a,b = list(map(int, input().split()))
    g[a-1].append(b-1)
    g[b-1].append(a-1)
    
seen_u = [0] * N
seen_v = [0] * N
dict_u = [0] * N
dict_v = [0] * N

seen_u[u-1] = 1
seen_v[v-1] = 1

def dfs(G, cr, seen, dct):
    for i in G[cr]:
        if seen[i] == 0:
            seen[i] = 1
            dct[i] = dct[cr] + 1
            dfs(G, i, seen, dct)

dfs(g, u-1, seen_u, dict_u)
dfs(g, v-1, seen_v, dict_v)


print(max([uv-vv for uv,vv in zip(dict_u, dict_v)])-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
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)
if len(G[u])==1 and G[u][0]==v:
    print(0)
    exit()
q=deque([])
q.append(u)
dist=[-1 for i in range(N)]
parents=[-1 for i in range(N)]
dist[u]=0
while(len(q)>0):
    r=q.popleft()
    for p in G[r]:
        if dist[p]!=-1:
            continue
        dist[p]=dist[r]+1
        parents[p]=r
        q.append(p)
L=[v]
x=v
while(1):
    if x==u:
        break
    L.append(parents[x])
    x=parents[x]
#print(parents)
#print(L)
M=len(L)
x=L[M//2-1]
X=M//2-1
dist2=[-1 for i in range(N)]
dist2[x]=0
q=deque([])
q.append(x)
while(len(q)>0):
    r=q.popleft()
    for p in G[r]:
        if dist2[p]!=-1:
            continue
        dist2[p]=dist2[r]+1
        q.append(p)
Y=max(dist2)-1
print(X+Y)

Submission status: Wrong Answer

Solution code:
from collections import deque
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)
q=deque([])
q.append(u)
dist=[-1 for i in range(N)]
parents=[-1 for i in range(N)]
dist[u]=0
while(len(q)>0):
    r=q.popleft()
    for p in G[r]:
        if dist[p]!=-1:
            continue
        dist[p]=dist[r]+1
        parents[p]=r
        q.append(p)
L=[v]
x=v
while(1):
    if x==u:
        break
    L.append(parents[x])
    x=parents[x]
#print(parents)
#print(L)
M=len(L)
x=L[M//2-1]
X=M//2-1
dist2=[-1 for i in range(N)]
dist2[x]=0
q=deque([])
q.append(x)
while(len(q)>0):
    r=q.popleft()
    for p in G[r]:
        if dist2[p]!=-1:
            continue
        dist2[p]=dist2[r]+1
        q.append(p)
Y=max(dist2)-1
print(X+Y)

Submission status: Wrong Answer

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

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




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
dist_v = [0]*n

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

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

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




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

print(d)