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:
from collections import deque

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

du = [0] * N
pu = [-1] * N
q = [(u - 1, -1)]
while q :
  cur, pre = q.pop()
  for nex in vec[cur] :
    if nex != pre :
      du[nex] = du[cur] + 1
      pu[nex] = cur
      q.append((nex, cur))

dv = [0] * N
pv = [-1] * N
q = [(v - 1, -1)]
while q :
  cur, pre = q.pop()
  for nex in vec[cur] :
    if nex != pre :
      dv[nex] = dv[cur] + 1
      pv[nex] = cur
      q.append((nex, cur))

# du[u - 1] = 2
# dv[v - 1] = 2

ret = 0
for i, (u, v) in enumerate(zip(du, dv)) :
  if pu[i] == -1 or pv[i] == -1 :
    if u == 1 or v == 1 :
      ret = max(ret, 1)
    else :
      ret = max(ret, u - 1, v - 1)
  if u < v or (u == v and pu[i] != pv[i]) :
    if u == v :
      ret = max(ret, u)
    else :
      ret = max(ret, v - 1)
print(ret)

Submission status: Wrong Answer

Solution code:
N, U, V = map(int, input().split())
A = [[] for _ in range(N)]

import sys
sys.setrecursionlimit(10**8)
for _ in range(N - 1):
    a, b = map(int, input().split())

    A[a - 1].append(b - 1)
    A[b - 1].append(a - 1)

C = [0] * N

def DFS(x, pre, cnt):
    if C[x] < cnt:
        C[x] = cnt
    cnt += 1
    for a in A[x]:
        if a == pre:
            continue

        if a == (U - 1):
            cnt -= 1 
        
        DFS(a, x, cnt)


DFS(V - 1, -1, 0)
ans = max(C) - 1
if ans < 0:
    ans = 0
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
def main():

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

    if N == 2: return 0

    dist1 = [0 for _ in range(N)]
    cur = [v]
    visited = set()
    l = 0
    while cur:
        l += 1
        temp = []
        for a in cur:
            for b in graph[a]:
                if b not in visited:
                    temp.append(b)
                    visited.add(b)
                    dist1[b-1] = l
        cur = temp

    ans = -1
    dist2 = [0 for _ in range(N)]
    cur = [u]
    visited = set()
    l = 0
    while cur:
        l += 1
        temp = []
        for a in cur:
            for b in graph[a]:
                if b not in visited:
                    if l >= dist1[b-1]:
                        d = l + dist1[b-1]-1
                        if d % 2 == 0: d -= 1
                        ans = max(ans, d)
                    else:
                        if l % 2 == 0:
                            ans = max(ans, l-1)
                        else:
                            ans = max(ans, l)
                        temp.append(b)
                        visited.add(b)
                        dist2[b-1] = l
        cur = temp
        # if len(cur) > 0: ans = max(ans, l)

    return ans

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)
best = t
for v in range(n):
    if distT[v] <= distA[v] and distT[best] < distT[v]:
        best = v
diff = distA[best] - distT[best]
if diff == 0:
    print(distT[best] // 2)
else:
    print(distT[best] + diff // 2)

Submission status: Wrong Answer

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


if (len(T[u])) == 1 and (T[u][0][0] == v):
    print(0)
    exit()


def dijkstra(graph, start, inf=float('inf')):
    import heapq
    n = len(graph)
    distances = [inf] * n
    distances[start] = 0
    visited = [False] * n

    # 距離・頂点
    hq = [(0, start)]
    while hq:
        dist, fr = heapq.heappop(hq)
        visited[fr] = True

        for to, cost in graph[fr]:
            new_dist = distances[fr] + cost
            if (visited[to]) or (distances[to] <= new_dist):
                continue

            distances[to] = new_dist
            heapq.heappush(hq, (new_dist, to))

    return distances


U_dist = dijkstra(T, u)
V_dist = dijkstra(T, v)

Good = set()
for i, ud, vd in zip(range(N), U_dist, V_dist):
    if ud < vd:
        Good.add(i)


T2 = [[] for i in range(N)]
for a, b, d in E:
    if (a in Good) and (b in Good):
        T2[a].append([b, 1])
        T2[b].append([a, 1])

longest = -1
tmp_max = 0
for n, d in enumerate(dijkstra(T2, u)):
    if d != float('inf'):
        if tmp_max < d:
            tmp_max = d
            longest = n

if longest == -1:
    print(1)
    exit()

reach = V_dist[longest]
if abs(tmp_max - reach) % 2 == 1:
    print(tmp_max)
else:
    print(tmp_max + 1)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True
#for i in range(n):

ans=0

n,t,a=LI_()
n+=1
g,c=GI(n,n-1)

#for i in range(1,30):


#vにはdepthをセット & -1 で未訪問フラグ

v=[-1]*(n)

def bfs(x):  # x スタート
    p=deque()
    p.append(x)
    v[x]=0
    while p:
        c=p.popleft()
        for i in g[c]:
            if v[i]==-1:
                p.append(i)
                v[i]=v[c]+1
    return

w=[-1]*(n)

def t_bfs(x):  # x スタート
    ans=0
    p=deque()
    p.append(x)
    w[x]=0
    while p:
        c=p.popleft()
        for i in g[c]:
            if w[i]==-1:
                p.append(i)
                #w[i]=w[c]+1
                if w[c]+1==v[i]:
                    ans=max(ans,v[i])
                if w[c]+1>=v[i]:
                #if w[c]+1>v[i]:
                    
                    w[i]=-inf
                else:
                    w[i]=w[c]+1
                    #ans=max(ans,v[i]-(1 if (v[i]-w[i])%2==0 else 0))
                if (w[c]+1-v[i])%2==0:
                        ans=max(ans,v[i])
                else:
                    ans=max(ans,v[i]-1)
                
    return ans


bfs(a)
ans=t_bfs(t)

#print(max(0,ans-1))
print(ans)

Submission status: Wrong Answer

Solution code:
class Tree:
  C, RL = {}, {}
  R, N, D, S, P = None, None, None, None, None
  def __init__(s, num):
    s.N = num
  def setC(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def makeRank(s, root):
    s.R = [0] * s.N
    s.R[root] = 1
    s.RL[1] = [root]
    s.S = {}
    s.P = {}
    F = [root]
    s.D = 2
    while F != []:
      Ft = []
      s.RL[s.D] = []
      for i in F:
        for j in s.C[i]:
          if s.R[j] == 0:
            s.R[j] = s.D
            Ft.append(j)
            s.RL[s.D].append(j)
            if i not in s.S:
              s.S[i] = [j]
            else:
              s.S[i].append(j)
            s.P[j] = i

      s.D += 1
      F = Ft
  def getDeep(s, x):
    ans = 0
    if x in s.S:
      for i in s.S[x]:
        ans = max(ans, s.getDeep(i))
      return ans + 1
    else:
      return 0
  def getParent(s, x, n):
    if n == 0:
      return x
    return s.getParent(s.P[x], n - 1)
    

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

T = Tree(N)
for a, b in AB:
  T.setC(a - 1, b - 1)

T.makeRank(v - 1)
t = (T.R[u - 1] // 2) - 1
f = T.R[u - 1] % 2
#k = T.getDeep(T.getParent(u - 1, t))
#print(t + k + f)

Submission status: Wrong Answer

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


from collections import deque, defaultdict
Tree = defaultdict(lambda: [])

# input data
N, u, v = read_ints()
for _ in range(N - 1):
    s, t = list(map(int, input().split()))
    w = 1
    Tree[s - 1].append((t - 1, w))
    Tree[t - 1].append((s - 1, w))


def bfs(Tree, n_V, s):
    '''
    指定した点sからの単一始点で各点までの距離を返す。
    n_Vは頂点の数
    Treeはdefault dictで、valueには(隣接ノード,そこまでのコスト)がリスト形式で格納されているとする。
    '''
    INF = 10**9
    Dists = [INF] * n_V  # 距離の初期化 #こいつを更新して返すことにする
    is_visited = [False] * n_V
    is_visited[s] = True
    que = deque([(s, 0)])  # (ノード番号,そこまでたどり着くためのコスト)
    while que:
        cur, cost = que.popleft()
        Dists[cur] = cost
        for nx_node, nx_cost in Tree[cur]:
            if is_visited[nx_node]:
                continue
            que.append((nx_node, nx_cost + cost))
            is_visited[nx_node] = True

    return Dists


# 任意の点から一番遠い点を求めて、そこからさらに一番遠い点がほしい
Dists = bfs(Tree, N, 0)
next_node = Dists.index(max(Dists))  # numpyでいうargmaxしてる
Dists = bfs(Tree, N, next_node)

print(max(Dists) - 1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from heapq import heapify, heappop, heappush
from collections import defaultdict, deque
import sys
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

class LCA:
    # ダブリングver
    def __init__(self, G):
        self.N = len(G)
        self.base = int.bit_length(self.N)
        self.depth = [-1]*self.N
        self.parents = [[-1]*self.base for _ in range(self.N)]
        self.parents[0][0] = 0
        Q = [0]
        self.depth[0] = 0

        while Q:
            p = Q.pop()
            for q in G[p]:
                if self.depth[q] != -1:
                    continue
                self.parents[q][0] = p
                self.depth[q] = self.depth[p] + 1
                Q.append(q)

        for i in range(1, self.base):
            for j in range(self.N):
                self.parents[j][i] = self.parents[self.parents[j][i-1]][i-1]


    def find_ancestor(self, a, b):
        if self.depth[a] > self.depth[b]:
            a, b = b, a
        d = self.depth[b] - self.depth[a]
        f = 2**(self.base-1)
        c = b*1
        while f:
            if d&f:
                c = self.parents[c][int.bit_length(f)-1]
            f //= 2
        if c == a:
            return c, 1
        f = 2**(self.base-1)
        while f:
            na = self.parents[a][int.bit_length(f)-1]
            nc = self.parents[c][int.bit_length(f)-1]
            if na != nc:
                a = na*1
                c = nc*1
            f //= 2
        return self.parents[a][0], 0

    def distance(self, a, b):
        c, _ = self.find_ancestor(a, b)
        return self.depth[a] + self.depth[b] - 2*self.depth[c]

N, u, v = inpl()
u -= 1
v -= 1
G = [[] for _ in range(N)]
for i in range(N-1):
    a, b = inpl()
    G[a-1].append(b-1)
    G[b-1].append(a-1)

lca = LCA(G)

isleaf = [1]*N

Q = deque()
Q.append(0)
searched = [0]*N
searched[0] = 1
while Q:
    p = Q.popleft()
    for q in G[p]:
        if searched[q]:
            continue
        isleaf[p] = 0
        searched[q] = 1
        Q.append(q)

ans = 0
for i in range(N):
    if len(G[i]) > 1:
        continue
    uc = lca.find_ancestor(u, i)[0]
    vc = lca.find_ancestor(v, i)[0]
    
    if lca.depth[uc] >= lca.depth[vc]:
        ans = max(ans, lca.depth[v] + lca.depth[i] - 2*lca.depth[vc] - 1)
    else:
        if lca.distance(u, vc) < abs(lca.depth[v] - lca.depth[vc]):
            ans = max(ans, lca.depth[v] + lca.depth[i] - 2*lca.depth[vc] - 1)
print(ans)

Submission status: Wrong Answer

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

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

u_que = [u]
v_que = [v]
long = 0
u_visit = []
u_visitset = [u]
v_visit = []
v_visitset = [v]

for i in range(n-1):
    u_visit.append(u_que)
    u_que_tmp = []
    for j in u_que:
        for k in hen[j-1]:
            u_que_tmp.append(k)
    set(u_que_tmp)
    list(u_que_tmp)
    tmp = []
    for j in u_que_tmp:
        if j not in u_visitset:
            tmp.append(j)
            u_visitset.append(j)           
    u_que = tmp

    v_visit.append(v_que)
    v_que_tmp = []
    for j in v_que:
        for k in hen[j-1]:
            v_que_tmp.append(k)
    set(v_que_tmp)
    list(v_que_tmp)
    tmp = []
    for j in v_que_tmp:
        if j not in v_visitset:
            tmp.append(j)
            v_visitset.append(j)
    v_que = tmp

#print(u_visit,v_visit)
#print(u_visitset,v_visitset)

flag = False
x = len(v_visit)
for i in range(1,len(v_visit)):
    if v_visit[-1*i] == []:
        x -= 1
    else:
        break

for i in range(1,n):
    ans = x - i
    if flag:
        break
    for j in v_visit[-1*i]:
        if flag:
            break
        for k in u_visit[:-1*i]:
            if j in k:
                check = k
                flag = True
                break
flag = False
odd = 0
for i in range(n-1):
    if flag:
        break
    for j in v_visit[i]:
        if u == j:
            if i % 2 == 0:
                odd = 1
                flag = True
                break
            else:
                odd = 0
                flag = True
                break
#print(x,odd,ans)
ans += odd
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,u,v=map(int,input().split())
edges=list(list(map(int,input().split())) for _ in range(n-1))

counts=list(0 for _ in range(n))
roots=list([] for _ in range(n))
dist_u=list(-1 for _ in range(n))
dist_v=list(-1 for _ in range(n))

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

for s,t in edges:
    counts[s-1]+=1
    counts[t-1]+=1
    roots[s-1].append(t)
    roots[t-1].append(s)

count=0
while count!=n:
    for node in range(1, n+1):
        if dist_u[node-1]==-1:
            dist_root=max(dist_u[r-1] for r in roots[node-1])
            if dist_root!=-1:
                dist_u[node-1]=dist_root+1
                if dist_v[node-1]!=-1:
                    count+=1
        if dist_v[node-1]==-1:
            dist_root=max(dist_v[r-1] for r in roots[node-1])
            if dist_root!=-1:
                dist_v[node-1]=dist_root+1
                if dist_u[node-1]!=-1:
                    count+=1

longest_path=max(dist_u[node]+dist_v[node] if dist_u[node]<=dist_v[node] else 0 for node in range(n))
print(longest_path//2)

Submission status: Wrong Answer

Solution code:
from queue import Queue

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

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

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

q = Queue()
db = [-1 for i in range(n)]
q.put(v - 1)
db[v - 1] = 0
while True:
  if q.empty():
    break
  else:
    p = q.get()
    for _e in e[p]:
      if db[_e] < 0:
        q.put(_e)
        db[_e] = db[p] + 1

print(max(db) - 1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
 
N, u, v = map(int, input().split())
 
u -= 1
v -= 1
 
graph = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
 
lst = []
def calcDist(cur, par, dst):
    global lst
    lst[cur] = dst
    for neighbour in graph[cur]:
        if neighbour == par: continue
        calcDist(neighbour, cur, dst + 1)
        
uDist = [None for i in range(N)]
vDist = [None for i in range(N)]
lst = uDist
calcDist(u, -1, 0)
lst = vDist
calcDist(v, -1, 0)
 
best = 0
# uDoes hiding, vdoes searching
for node in range(N):
    if uDist[node] < vDist[node]:
        if vDist[node]%2==uDist[node]%2:
            best = max(best, uDist[node])
        else:
            best = max(best, max(uDist[n] for n in graph[node]))
    if uDist[node] == vDist[node]:
        if any((vDist[n] == uDist[n] and vDist[n] < vDist[node]) for n in graph[node]): continue
        best = max(best, uDist[node])
print(best)

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 (d + ans)
else:
    print (d + ans - 1)

Submission status: Wrong Answer

Solution code:
import heapq
WHITE = 0
GRAY = 1
BLACK = 2
INFTY = 10**16
def dijkstra(s, VC):
    color = [WHITE for i in range(N)]
    d = [INFTY for i in range(N)]
    d[s] = 0
    pq = []
    heapq.heappush(pq, (0, s))

    while len(pq) != 0:
        u = heapq.heappop(pq)[1]
        color[u] = BLACK

        for v, c in VC[u]:
            if color[v] != BLACK:
                if d[u] + c < d[v]:
                    d[v] = d[u] + c
                    color[v] = GRAY
                    heapq.heappush(pq, (d[v], v))

    return d

N, T, A = map(int, input().split())
V = [[] for i in range(N)]
# VB = [[] for i in range(N)]
for i in range(N-1):
    u, v = list(map(int, input().split()))
    V[u-1].append([v-1, 1])
    V[v-1].append([u-1, 1])

dt = dijkstra(T-1, V)
da = dijkstra(A-1, V)
# tmp = 10**16
# base = 10 ** 15
# ans = [0 for i in range(N)]
max_a = -1
max_i = -1
for i, a in enumerate(da):
    if max_a < a:
        max_a = a
        max_i = i
    elif max_a == a and i == T-1:
        max_i = i
t = dt[max_i]
a = max_a - t
ans = a - int(t == 0)
print(ans)
# print(t, a)

Submission status: Wrong Answer

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

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

def dijkstra(s, d):
    d[s] = 0
    q = [s]

    while q:
        u = q.pop()
        du = d[u] + 1
        for v in e[u]:
            if du < d[v]:
                d[v] = du
                q.append(v)
du = [N+2] * N
dv = [N+2] * N
dijkstra(u-1, du)
dijkstra(v-1, dv)
#print("T", du)
#print("A", dv)

e = 0
for i in range(N):
    if du[i] <= dv[i]:
        e = max(e, du[i])
e0 = N+1
for i in range(N):
    if du[i] == dv[i]:
        e0 = min(e0, du[i])
e = min(e, e0)
#print("e=",e, "T-A=%d"%du[v-1])
print(e)

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([])
for w in leaf:
    q.append(w)
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:
# -*- 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))

for i in range(N):
    if memo[i] <= memo2[i]:
        memo2[i] = -1
mx = mx2 = -1
for u, val in enumerate(memo2):
    if val > mx:
        mx = val
        val2 = memo[u]
        if val2 > mx2:
            mx2 = val2
print(val2 - 1)

Submission status: Wrong Answer

Solution code:
N, u, v = map(int, input().split())
edge = [set() for i in range(N)]

u -= 1
v -= 1

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

def calcDepth(root):
  depth = [-1] * N
  stack = [(root, 0)]

  while stack:
    cur, curD = stack.pop()
    depth[cur] = curD
    for c in edge[cur]:
      if depth[c] != -1: continue
      stack.append((c, curD+1))
  
  return depth

Adepth = calcDepth(v)
Ddepth = calcDepth(u)
maxA = max(Adepth)
maxAI = Adepth.index(maxA)

print(max(maxA, Ddepth[maxAI]) - 1)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True
#for i in range(n):

ans=0

n,t,a=LI_()
n+=1
g,c=GI(n,n-1)

#for i in range(1,30):


#vにはdepthをセット & -1 で未訪問フラグ

v=[-1]*(n)

def bfs(x):  # x スタート
    p=deque()
    p.append(x)
    v[x]=0
    while p:
        c=p.popleft()
        for i in g[c]:
            if v[i]==-1:
                p.append(i)
                v[i]=v[c]+1
    return

w=[-1]*(n)

def t_bfs(x):  # x スタート
    ans=0
    p=deque()
    p.append(x)
    w[x]=0
    while p:
        c=p.popleft()
        for i in g[c]:
            if w[i]==-1:
                p.append(i)
                #w[i]=w[c]+1
                if w[c]+1==v[i]:
                    ans=max(ans,v[i])
                if w[c]+1>=v[i]:
                #if w[c]+1>v[i]:
                    if (w[c]+1-v[i])%2==0:
                        ans=max(ans,v[i])
                    else:
                        ans=max(ans,v[i]+1)
                
                    w[i]=-inf
                else:
                    w[i]=w[c]+1
                    #ans=max(ans,v[i]-(1 if (v[i]-w[i])%2==0 else 0))
                    
    return ans


bfs(a)
ans=t_bfs(t)

#print(max(0,ans-1))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

N , u,v = map(int,input().split())
u -= 1
v -= 1
lis = [[int(i)-1 for i in input().split()]for _ in range(N-1)]
adj = [[] for i in range(N)]
for (i,j) in lis:
    adj[i].append(j)
    adj[j].append(i)
l = [[v,0,False]]
q = deque(l)
b = [-1]*N
b[v] = 0
ans = 0
m = 0
for _ in range(N-1):
    i, n ,bl = q.popleft()
    for j in adj[i]:
        if j == u:
            ans = n+1
            bl = True
        if bl:
            m = n
        if b[j]==-1:
            q.append([j,n+1,bl])
            b[j] = n+1

i,n,bl = q.popleft()
l = [i]
mal = [-1]*(n+1)
mal[-1] = i
nn = n
for _ in range(nn):
    for j in adj[i]:
        if nn-1 == b[j]:
            i = j
            mal[nn-1] = j
            nn -= 1
            break

nu = ans
uu = u
bln = False
for _ in range(nu):
    for j in adj[uu]:
        if nu-1 == b[j]:
            uu = j
            nu -= 1
            if mal[nu] == uu:
                bln = True
                break
    if bln:
        break


if nu > ans - nu or bl:
    print(n-1)
else:
    print(m-1)