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
from collections import defaultdict, deque
from copy import deepcopy
import itertools
input = sys.stdin.readline
# 文字列の場合は普通のinput()を使うか下を使う
# input = sys.stdin.readline().rstrip()


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

# vを根にしたDFS
depth = [0] * N
leaf = []
parent = [None] * N
visited = [False] * N
q = deque([(v, 0)])
visited[v] = True
while q:
    w, h = q.popleft()
    is_leaf = True
    for s in repn[w]:
        if visited[s] == False:
            is_leaf = False
            visited[s] = True
            depth[s] = h + 1
            parent[s] = w
            q.append((s, h + 1))
    if is_leaf:
        leaf.append(w)
#print('depth={}'.format(depth))
#print('parent={}'.format(parent))
#print('leaf={}'.format(leaf))


# 各頂点から葉までの最長距離
height = [0] * N
q = deque(leaf)
while q:
    w = q.popleft()
    s = parent[w]
    if s != None:
        height[s] = max(height[w] + 1, height[s])
        q.append(s)
#print('height={}'.format(height))


# 逃走経路の最長の長さ
mid = (depth[u] + 2) // 2
t = (depth[u] + 1) // 2
descend = height[u]
up = 0
p = parent[u]
for h in range(1, t):
    if descend + h <= height[p]:
        descend = height[p]
        up = h
    p = parent[p]
length = descend + (depth[u] - up)
print(length - 1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
n,u,v=map(int,input().split())
visitedlist=[-1 for  i in range(n)]
kilist=[[] for i in range(n)]
anslist=[0 for i in range(n)]
searchedlist=[-1 for i in range(n)]
for i in range(n-1):
        a,b=map(int,input().split())
        kilist[a-1].append(b)
        kilist[b-1].append(a)
def search(P):
        searchedlist[P-1]=1
        visitedlist[P-1]=1
        flag=0
        for j in kilist[P-1]:
            if visitedlist[j-1]<0:
                visitedlist[j-1]=1
                flag+=1
                anslist[j-1]=anslist[P-1]+1
        else:
            pass

        if flag>0:    
            for k in kilist[P-1]:
                if searchedlist[k-1]==-1:
                    search(k)
search(v)
if v<u:
	print(anslist[u]-1)
else:
  if u>1:
  	print(v-u)
  else:
    print(v-2)

Submission status: Wrong Answer

Solution code:
N,u,v = map(int,input().split())
inf = 10**9
edge = [[] for j in range(N+1)]
G = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
    edge[a].append([1,b])
    edge[b].append([1,a])
import heapq
def dis(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (N+1)
    used = [True] * (N+1) #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
U = dis(u)
V = dis(v)
F = [v]
list = []
HA = []
while len(F) > 0:
    x = F.pop(0)
    list.append(x)
    h = []
    for j in G[x]:
        if j not in F:
            if j not in list:
                F.append(j)
                h.append(j)
    if len(h) == 0:
        HA.append(x)
m = -1
for i in HA:
    x = U[i]
    y = V[i]
    if y > x:
        if y > m:
            s = i
x = U[s]
y = V[s]
ans = x + (y-x)//2
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
import heapq
input = sys.stdin.readline
N, u, v = map(int, input().split())
e = dd(list)
for _ in range(N - 1):
  a, b = map(int, input().split())
  e[a].append((b, 1))
  e[b].append((a, 1))
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 6)
      v0 = v // (10 ** 6)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 6) + p[0])
    return d
d = dijkstra(N, e)
p = d.path(v, 0)
pp = d.path(u, 0)
#print(p)
#print(pp)
res = -1
ee = dd(list)
for k in e.keys():
  for x in e[k]:
    if p[x[0]] > pp[x[0]]:
      ee[k].append((x[0], 1))
dd = dijkstra(N, ee)
ppp = dd.path(u, 0)
#print(ppp)
t = 0
for i in range(1, N + 1):
  if ppp[i] != float("inf"):
    if ppp[i] > res:
      res = ppp[i]
      if ppp[i] + 1 < p[i]: res = p[i]
      t = i
for x in e[t]:
  if p[x[0]] == pp[x[0]]: 
    res = ppp[t]
    res += 1
    break
print(res)

Submission status: Wrong Answer

Solution code:
from collections import deque
from math import ceil

def read():
    N, u, v = list(map(int, input().strip().split()))
    G = [list() for i in range(N+1)]
    for i in range(N-1):
        a, b = list(map(int, input().strip().split()))
        G[a].append(b)
        G[b].append(a)
    return N, u, v, G

def bfs(G, N, start, INF):
    D = [INF for i in range(N+1)]
    D[start] = 0
    q = deque()
    q.appendleft(start)
    while(len(q) > 0):
        s = q.pop()
        for i in range(len(G[s])):
            t = G[s][i]
            if D[t] == INF:
                D[t] = D[s] + 1
                q.appendleft(t)
    return D


def argmax(x):
    imax = 0
    for i, e in enumerate(x):
        if x[imax] < e:
            imax = i
    return imax

def solve(N, u, v, G, INF=-1000000):
    du = bfs(G, N, u, INF)
    dv = bfs(G, N, v, INF)
    du_opt = [x for x in du]
    for i in range(N+1):
        if du[i] >= dv[i]:
            du_opt[i] = INF
    idx = argmax(du_opt)
    return (du[idx] + dv[idx]) // 2


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
import heapq
input = sys.stdin.readline
N, u, v = map(int, input().split())
e = dd(list)
for _ in range(N - 1):
  a, b = map(int, input().split())
  e[a].append((b, 1))
  e[b].append((a, 1))
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 6)
      v0 = v // (10 ** 6)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 6) + p[0])
    return d
d = dijkstra(N, e)
p = d.path(v, 0)
pp = d.path(u, 0)
#print(p)
#print(pp)
res = -1
ee = dd(list)
for k in e.keys():
  for x in e[k]:
    if p[x[0]] > pp[x[0]]:
      ee[k].append((x[0], 1))
dd = dijkstra(N, ee)
ppp = dd.path(u, 0)
#print(ppp)
t = 0
for i in range(1, N + 1):
  if ppp[i] != float("inf"):
    if ppp[i] > res:
      res = max(ppp[i], p[i])
      t = i
for x in e[t]:
  if p[x[0]] == pp[x[0]]: 
    res += 1
    break
print(res)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
import heapq
input = sys.stdin.readline
N, u, v = map(int, input().split())
e = dd(list)
for _ in range(N - 1):
  a, b = map(int, input().split())
  e[a].append((b, 1))
  e[b].append((a, 1))
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 6)
      v0 = v // (10 ** 6)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 6) + p[0])
    return d
d = dijkstra(N, e)
p = d.path(v, 0)
pp = d.path(u, 0)
#print(p)
#print(pp)
res = -1
ee = dd(list)
for k in e.keys():
  for x in e[k]:
    if p[x[0]] > pp[x[0]]:
      ee[k].append((x[0], 1))
dd = dijkstra(N, ee)
ppp = dd.path(u, 0)
#print(ppp)
t = 0
for i in range(1, N + 1):
  if ppp[i] != float("inf"):
    if ppp[i] > res:
      res = ppp[i]
      t = i
for x in e[t]:
  if p[x[0]] == pp[x[0]]: 
    res += 1
    break
print(res)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
import heapq
input = sys.stdin.readline
N, u, v = map(int, input().split())
e = dd(list)
for _ in range(N - 1):
  a, b = map(int, input().split())
  e[a].append((b, 1))
  e[b].append((a, 1))
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 6)
      v0 = v // (10 ** 6)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 6) + p[0])
    return d
d = dijkstra(N, e)
p = d.path(v, 0)
pp = d.path(u, 0)
#print(p)
#print(pp)
res = -1
ee = dd(list)
for k in e.keys():
  for x in e[k]:
    if p[x[0]] > pp[x[0]]:
      ee[k].append((x[0], 1))
dd = dijkstra(N, ee)
ppp = dd.path(u, 0)
#print(ppp)
t = 0
for i in range(1, N + 1):
  if ppp[i] != float("inf"):
    if ppp[i] > res:
      res = ppp[i]
      t = i
for x in e[t]:
  if p[x[0]] >= pp[x[0]]: 
    res += 1
    break
print(res)

Submission status: Wrong Answer

Solution code:
N,u,v = map(int,input().split())
inf = 10**9
edge = [[] for j in range(N+1)]
G = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
    edge[a].append([1,b])
    edge[b].append([1,a])
import heapq
def dis(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (N+1)
    used = [True] * (N+1) #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
U = dis(u)
V = dis(v)
F = [v]
list = []
HA = []
while len(F) > 0:
    x = F.pop(0)
    list.append(x)
    h = []
    for j in G[x]:
        if j not in F:
            if j not in list:
                F.append(j)
                h.append(j)
    if len(h) == 0:
        HA.append(x)
ans = 0
for i in HA:
    x = U[i]
    y = V[i]
    if y > x:
        a = x + (y-x)//2
        ans = max(a,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import copy
input = sys.stdin.readline
import numpy as np
N, U, V = [int(x) for x in input().split()]
n = N
G_1 = [[] for _ in range(N)]
G = G_1[0:]
for _ in range(N-1):
    A, B = [int(x) for x in input().split()]
    G[A-1].append(B-1)
    G[B-1].append(A-1)

from collections import deque
d = [-1] * n
color = ["WHITE"] * n
queue = []
queue = deque(queue)

def bfs(u):
    color[u-1] = "GRAY"
    d[u-1] = 0
    queue.append(u-1)
    while len(queue) > 0:
        u = queue.popleft()
        if len(G[u]) == 0:
            color[u] = "BLACK"
        else:
            for u_next in G[u]:
                if color[u_next] == "WHITE":
                    d[u_next] = d[u] + 1
                    color[u_next] = "GRAY"
                    queue.append(u_next)
                G[u] = 0
            color[u] == "BLACK"
bfs(U)
a = d[0:]
G = G_1[0:]
d = [-1] * n
color = ["WHITE"] * n
queue = []
queue = deque(queue)
bfs(V)
t = d[0:]
a = np.array(a)
t = np.array(t)
ans = a[a<t].max()
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
from math import ceil

def read():
    N, u, v = list(map(int, input().strip().split()))
    G = [list() for i in range(N+1)]
    for i in range(N-1):
        a, b = list(map(int, input().strip().split()))
        G[a].append(b)
        G[b].append(a)
    return N, u, v, G

def bfs(G, N, start, INF):
    D = [INF for i in range(N+1)]
    D[start] = 0
    q = deque()
    q.appendleft(start)
    while(len(q) > 0):
        s = q.pop()
        for i in range(len(G[s])):
            t = G[s][i]
            if D[t] == INF:
                D[t] = D[s] + 1
                q.appendleft(t)
    return D


def solve(N, u, v, G, INF=-1000000):
    du = bfs(G, N, u, INF)
    dv = bfs(G, N, v, INF)
    for i in range(N):
        if du[i] >= dv[i]:
            du[i] == INF
    return max(du)


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))

Submission status: Wrong Answer

Solution code:
import sys
n, tak, aok = map(int, input().split())
sys.setrecursionlimit(100000)
tak = tak - 1
aok = aok - 1
neighbors = [set() for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a = a - 1
    b = b - 1
    neighbors[a].add(b)
    neighbors[b].add(a)
rurality = [n] * n
def paint(rurality, here, num, output=None):
    if rurality[here] >= num:
        rurality[here] = num
        if output is not None:
            output.add(num)
        for nei in neighbors[here]:
            paint(rurality, nei, num + 1)
paint(rurality, aok, 0)
takback = tak
for _ in range((rurality[tak] - 1) // 2):
    for nei in neighbors[takback]:
        if rurality[nei] < rurality[takback]:
            takback = nei
            break
output = set()
paint(rurality, takback, rurality[takback], output)
print(max(output))

Submission status: Wrong Answer

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

Dep_u = [-1] *n 
Dep_v = [-1] *n

Dep_u[u] = 0
Dep_v[v] = 0

from collections import deque
##bfs2回が簡明
def bfs(L,x):
    Q = deque()
    Q.append(x)
    while Q:
        y = Q.popleft()
        for z in Tr[y]:
            if L[z] == -1:
                L[z] = L[y] + 1
                Q.append(z)
                
bfs(Dep_u,u)
bfs(Dep_v,v)

ans = 1

for i in range(n):
    if Dep_v[i]>Dep_u[i]:
        ans = max(ans,Dep_v[i]-1)###v
print(ans)

Submission status: Wrong Answer

Solution code:
import queue

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

path = [0]*n

ab = [[ ] for i 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

print(ab)

q = queue.Queue()

q.put(u)

while not q.empty():
    tmp = q.get()
    for i in range(len(ab[tmp])):
        if path[ab[tmp][i]] == 0:
            path[ab[tmp][i]] = path[tmp] + 1
            q.put(ab[tmp][i])

path2 = [0]*n

max_path = 0
pos = 0

for i in range(n):
    if max_path < path[i]:
        max_path = path[i]
        pos = i

q = queue.Queue()

q.put(v)
    
while not q.empty():
    tmp = q.get()
    for i in range(len(ab[tmp])):
        if path2[ab[tmp][i]] == 0:
            path2[ab[tmp][i]] = path2[tmp] + 1
            q.put(ab[tmp][i])


print(max_path-path2[pos])

Submission status: Wrong Answer

Solution code:
import heapq;

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

vert = []

for i in range(n):
    vert.append([])

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

taka = u-1
aoki = v-1

if taka == aoki:
    print(0)
    exit()

q = [(0, aoki)]
aoki_dist = [-1] * n
aoki_dist[aoki] = 0

index = 0
while index < len(q):
    c0, i = q[index]
    c = c0 + 1
    for l in vert[i]:
        if aoki_dist[l] >= 0:
            continue
        aoki_dist[i] = c
        q.append((c, l))
    index += 1

q = [(0, taka)]
max_dist = aoki_dist[taka]
aoki_dist[taka] = -1

index = 0
while index < len(q):
    c0, i = q[index]
    c = c0 + 1
    for l in vert[i]:
        if aoki_dist[l] < 0:
            continue
        if c >= aoki_dist[l]:
            continue
        if max_dist < aoki_dist[l]:
            max_dist = aoki_dist[l]
        aoki_dist[l] = -1
        q.append((c, l))
    index += 1

print(max_dist - 1)

Submission status: Wrong Answer

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

Dep_u = [-1] *n 
Dep_v = [-1] *n

Dep_u[u] = 0
Dep_v[v] = 0

from collections import deque
##bfs2回が簡明
def bfs(L,x):
    Q = deque()
    Q.append(x)
    while Q:
        y = Q.popleft()
        for z in Tr[y]:
            if L[z] == -1:
                L[z] = L[y] + 1
                Q.append(z)
                
bfs(Dep_u,u)
bfs(Dep_v,v)

ans = 1

for i in range(n):
    if Dep_v[i]>Dep_u[i]:
        ans = max(ans,Dep_u[i])
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, x, y = MAP()
x -= 1; y -= 1
nodes = [[] for i in range(N)]
for i in range(N-1):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    nodes[b].append(a)

memo  = [-1] * N
stack = [(y, 0, -1)]
while stack:
    u, cost, prev = stack.pop()
    if memo[u] != -1:
        continue
    memo[u] = cost
    for v in nodes[u]:
        if v == prev:
            continue
        stack.append((v, cost+1, u))
memo2  = [-1] * N
stack = [(x, 0, -1)]
while stack:
    u, cost, prev = stack.pop()
    if memo2[u] != -1:
        continue
    memo2[u] = cost
    if u == y:
        continue
    for v in nodes[u]:
        if v == prev:
            continue
        stack.append((v, cost+1, u))

mx = -INF
for i in range(N):
    if memo[i] >= memo2[i]:
        mx = max(mx, memo[i])
print(mx - 1)

Submission status: Wrong Answer

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, V, U = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]

V -= 1
U -= 1
graph = [[] for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

# 深い方に逃げるべき
# 子どものうち一番深い場所の深さ
children_depths = [-1] * N
parents = [None] * N


def dfs(v, parent):
    for u in graph[v]:
        if u == parent:
            continue
        dfs(u, v)
    parents[v] = parent


dfs(U, None)
print(parents)

Submission status: Wrong Answer

Solution code:
import heapq;

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

vert = []

for i in range(n):
    vert.append([])

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

taka = u-1
aoki = v-1

if taka == aoki:
    print(0)
    exit()

q = [(0, aoki)]
aoki_dist = [-1] * n
aoki_dist[aoki] = 0

index = 0
while index < len(q):
    c0, i = q[index]
    c = c0 + 1
    for l in vert[i]:
        if aoki_dist[l] >= 0:
            continue
        aoki_dist[i] = c
        q.append((c, l))
    index += 1

q = [(0, taka)]
max_dist = aoki_dist[taka]
aoki_dist[taka] = -1

index = 0
while index < len(q):
    c0, i = q[index]
    c = c0 + 1
    for l in vert[i]:
        if aoki_dist[l] < 0:
            continue
        if c >= aoki_dist[l]:
            aoki_dist[l] = -1
            continue
        if max_dist < aoki_dist[l]:
            max_dist = aoki_dist[l]
        aoki_dist[l] = -1
        q.append((c, l))
    index += 1

print(max_dist - 1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, x, y = MAP()
x -= 1; y -= 1
nodes = [[] for i in range(N)]
for i in range(N-1):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    nodes[b].append(a)

memo  = [-1] * N
stack = [(y, 0, -1)]
while stack:
    u, cost, prev = stack.pop()
    if memo[u] != -1:
        continue
    memo[u] = cost
    for v in nodes[u]:
        if v == prev:
            continue
        stack.append((v, cost+1, u))
memo2  = [-1] * N
stack = [(x, 0, -1)]
while stack:
    u, cost, prev = stack.pop()
    if memo2[u] != -1:
        continue
    memo2[u] = cost
    if u == y:
        continue
    for v in nodes[u]:
        if v == prev:
            continue
        stack.append((v, cost+1, u))

mx = -INF
for i in range(N):
    if memo[i] > memo2[i]:
        mx = max(mx, memo[i])
print(mx - 1)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 5)


def dfs(v, parent, depth):
    parents[v] = parent
    self_depths[v] = depth
    sd = 0
    for u in links[v]:
        if u == parent:
            continue
        res = dfs(u, v, depth + 1)
        sd = max(sd, res + 1)

    subtree_depths[v] = sd
    return sd


def solve(u):
    catch = self_depths[u] // 2
    while self_depths[u] > catch:
        u = parents[u]
    return self_depths[u] + subtree_depths[u] - 1


n, u, v = map(int, input().split())
u -= 1
v -= 1
links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)

parents = [-1] * n
self_depths = [0] * n
subtree_depths = [0] * n
dfs(v, -1, 0)
print(solve(u))

Submission status: Wrong Answer

Solution code:
import heapq;

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

vert = []

for i in range(n):
    vert.append([])

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

taka = u-1
aoki = v-1

if taka == aoki:
    print(0)
    exit()

q = [(0, aoki)]
aoki_dist = [-1] * n
aoki_dist[aoki] = 0

index = 0
while index < len(q):
    c0, i = q[index]
    c = c0 + 1
    for l in vert[i]:
        if aoki_dist[l] >= 0:
            continue
        aoki_dist[i] = c
        q.append((c, l))
    index += 1

q = [(0, taka)]
max_dist = aoki_dist[taka]
aoki_dist[taka] = -1

index = 0
while index < len(q):
    c0, i = q[index]
    c = c0 + 1
    for l in vert[i]:
        if aoki_dist[l] < 0:
            continue
        if c > aoki_dist[l]:
            aoki_dist[l] = -1
            continue
        if max_dist < aoki_dist[l]:
            max_dist = aoki_dist[l]
        aoki_dist[l] = -1
        if c == aoki_dist[l]:
            continue
        q.append((c, l))
    index += 1

print(max_dist - 1)

Submission status: Wrong Answer

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, V, U = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]

V -= 1
U -= 1
graph = [[] for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

# 深い方に逃げるべき
# 子どものうち一番深い場所の深さ
children_depths = [-1 for _ in range(N)]
parents = [None for _ in range(N)]

Submission status: Wrong Answer

Solution code:
import sys


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

Submission status: Wrong Answer

Solution code:
def p_f():
    from sys import stdin
    input = stdin.readline
    N, u, v = map(int, input().split())
    edges = [list(map(int, input().split())) for i in range(N - 1)]
    if u == v:
        print(0)
        exit()

    def BFS(K, edges, N):
        roots = [[] for i in range(N)]
        for a, b in edges:
            roots[a - 1] += [(b - 1, 1)]
            roots[b - 1] += [(a - 1, 1)]
        dist = [-1] * N
        stack = []
        stack.append(K)
        dist[K] = 0
        while stack:
            label = stack.pop(-1)
            for i, c in roots[label]:
                if dist[i] == -1:
                    dist[i] = dist[label] + c
                    stack += [i]
        return dist

    dist_v = BFS(v - 1, edges, N)
    dist_u = BFS(u - 1, edges, N)
    # print(dist_v)
    # print(dist_u)
    max_dist = max(dist_v)
    maxIndex = [i for i, x in enumerate(dist_v) if x == max_dist]
    for i in maxIndex:
        if max_dist > dist_u[i]:
            print(max(dist_v) - 1)
            exit()
    if dist_v[u - 1] > max_dist - dist_v[u - 1]:
        print(max_dist - 1)
    else:
        print(dist_v[u - 1] - 1)


if __name__ == '__main__':
    p_f()

Submission status: Wrong Answer

Solution code:
import sys
import collections


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

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

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


if __name__ == '__main__':
    solve()