Problem:


Score : 600 points

Problem Statement

We have a tree with N vertices. The i-th edge connects Vertex A_i and B_i bidirectionally.

Takahashi is standing at Vertex u, and Aoki is standing at Vertex v.

Now, they will play a game of tag as follows:

1. If Takahashi and Aoki are standing at the same vertex, the game ends. Otherwise, Takahashi moves to a vertex of his choice that is adjacent to his current vertex.

2. If Takahashi and Aoki are standing at the same vertex, the game ends. Otherwise, Aoki moves to a vertex of his choice that is adjacent to his current vertex.

3. Go back to step 1.

Takahashi performs his moves so that the game ends as late as possible, while Aoki performs his moves so that the game ends as early as possible.

Find the number of moves Aoki will perform before the end of the game if both Takahashi and Aoki know each other's position and strategy.

It can be proved that the game is bound to end.

Constraints

2 \leq N \leq 10^5

1 \leq u,v \leq N

u \neq v

1 \leq A_i,B_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N u v
A_1 B_1
:
A_{N-1} B_{N-1}

Output

Print the number of moves Aoki will perform before the end of the game.

Sample Input 1

5 4 1
1 2
2 3
3 4
3 5

Sample Output 1

2

If both players play optimally, the game will progress as follows:

Takahashi moves to Vertex 3.

Aoki moves to Vertex 2.

Takahashi moves to Vertex 5.

Aoki moves to Vertex 3.

Takahashi moves to Vertex 3.

Here, Aoki performs two moves.

Note that, in each move, it is prohibited to stay at the current vertex.

Sample Input 2

5 4 5
1 2
1 3
1 4
1 5

Sample Output 2

1

Sample Input 3

2 1 2
1 2

Sample Output 3

0

Sample Input 4

9 6 1
1 2
2 3
3 4
4 5
5 6
4 7
7 8
8 9

Sample Output 4

5



Sample input:
5 4 1
1 2
2 3
3 4
3 5


Sample output:
2

Submission status: Wrong Answer

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

edges = [[] for _ in range(n)]

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

visit1 = [False]*n
visit2 = [False]*n

visit1[u-1] = True
visit2[v-1] = True

stack1 = [u-1]
stack2 = [v-1]

dis1 = [-1] * n
dis2 = [-1] * n
dis1[u-1] = 0
dis2[v-1] = 0

while stack1:
    for _ in range(len(stack1)):
        q1 = stack1.pop(-1)
        for i in edges[q1]:
            if not visit1[i] and not visit2[i]:
                visit1[i] = True
                dis1[i] = dis1[q1] + 1
                stack1.append(i)

    for _ in range(len(stack2)):
        q2 = stack2.pop(-1)
        for i in edges[q2]:
            if not visit2[i]:
                visit2[i] = True
                dis2[i] = dis2[q2] + 1
                stack2.append(i)

while stack2:
    q = stack2.pop(-1)
    for i in edges[q]:
        if not visit2[i]:
            visit2[i] = True
            dis2[i] = dis2[q] + 1
            stack2.append(i)

ans = 0
for i in range(n):
    if dis1[i] != -1:
        ans = max(ans, dis2[i])

print(ans-1)

Submission status: Wrong Answer

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

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

def tami2(n, cnt):
  global ans
  choku_visited[n] = True
  if cnt < aoki[n]:
    #print("---")
    #print(n,cnt,aoki[n])
    choku[n] = cnt + (((aoki[n] - 1) - cnt) //2)*2
    for x in edge[n]:
      if choku_visited[x] == False:
        tami2(x, cnt+1)
  elif cnt == aoki[n]:
    choku[n] = cnt + ((aoki[n] - cnt) //2)*2

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

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

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

ans = 0
tami(v, 0)
tami2(u, 0)
#print(aoki)
#print(choku)

for a,b in zip(aoki,choku):
  if a > b:
    if (a - b)%2 == 0:
      ans = max(ans, b + 1)
    else:
      ans = max(ans, a - 1)

print(ans)

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 = BFS(v - 1, edges, N)
    if dist[u - 1] > max(dist) - dist[u - 1]:
        print(max(dist) - 1)
    else:
        print(dist[u - 1] - 1)


if __name__ == '__main__':
    p_f()

Submission status: Wrong Answer

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

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

A = [-1] * (N + 1)
T = [-1] * (N + 1)
Leaf = [0] * (N + 1)

for i in range(1, N+1):
  if len(graph[i]) == 1:
    Leaf[i] = 1
    

stack = [u]
T[u] = 0
while stack:
  s = stack.pop()
  for g in graph[s]:
    if T[g] == -1:
      T[g] = T[s] + 1
      stack.append(g)
#print("T:", T)

stack = [v]
A[v] = 0
while stack:
  s = stack.pop()
  for g in graph[s]:
    if A[g] == -1:
      A[g] = A[s] + 1
      stack.append(g)
#print("A:", A)

answer = []
for i in range(N+1):
  if Leaf[i] == 1 and A[i] > T[i]:
    answer.append(T[i] + (A[i] - T[i]) // 2)
print(max(answer))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

input = sys.stdin.readline
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)

memo = [[0, 0] for i in range(n)]

def dfs(cur, pre, p):
    stack = deque([[cur, pre]])
    while stack:
        cur, pre = stack.pop()
        if pre != -1:
            memo[cur][p] = memo[pre][p] + 1
        for e in E[cur]:
            if e != pre:
                stack.append([e, cur])

dfs(u - 1, - 1, 0)
dfs(v - 1, -1, 1)

# print(memo)
ans = 0
for a, b in memo:
    ans = max(ans, b - 1)
print(ans)

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

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)]
closed = (1 << taka)
max_dist = aoki_dist[taka]

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

    index += 1

print(max_dist - 1)

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

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)]
closed = (1 << taka)
max_dist = aoki_dist[taka]

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

    index += 1

print(max_dist - 1)

Submission status: Wrong Answer

Solution code:
from scipy.sparse import*
n,t,a,*x=map(int,open(0).read().split())
print(max(a-1for t,a in zip(*csgraph.dijkstra(csr_matrix(([1]*~-n,(x[::2],x[1::2])),[n+1]*2),0,[t,a]))if t<a))

Submission status: Wrong Answer

Solution code:
from collections import deque
def main():
    N, u, v = [int(i) for i in input().split()]
    u -= 1
    v -= 1
    graph = [[] for _ in range(N)]
    for i in range(N-1):
        a,b = [int(i) for i in input().split()]
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)
    tree = [[] for _ in range(N)]
    parents = [-1] * N
    
    stack = deque([(v, -1)])
    while len(stack) > 0:
        current, parent = stack.pop()
        parents[current] = parent
        for n in graph[current]:
            if parent == n:
                continue
            stack.append((n, current))
            tree[current].append(n)
    
    current = u
    distance = 0
    while current != v:
        current = parents[current]
        distance += 1
    current = u
    cnt = 0
    res = 0
    # print(distance)
    from_n = -1
    while distance != 0:
        # print("checking %d" % current)
        stack = deque([(current, 0)])
        cnmax = 0
        # print(current)
        while len(stack) > 0:
            root, cn = stack.pop()
            cnmax = max(cn, cnmax)
            for c in tree[root]:
                if(c != from_n):
                    stack.append((c, cn+1))
            # print(cn)
        # print("---")
        res = max(res, cnmax + ((distance) // 2) + cnt)
        from_n = current
        current = parents[current]
        if current == -1:
            break
        distance -= 2
        cnt += 1
    print(res)
        
main()

Submission status: Wrong Answer

Solution code:
from collections import deque
N, u, v = map(int, input().split())
G = {k: [] for k in range(N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    # 無向グラフ
    G[a].append(b)
    G[b].append(a)

visited = [-1] * (N+1)

visited[v] = 0
route = []
que = deque([(v, 0)])

while que:
    ci, d = que.popleft()

    if ci == u:
        dist = d

    for ni in G[ci]:
        if visited[ni] == -1:
            visited[ni] = d+1
            que.append((ni, d+1))


que = deque([(u, 0)])
end = 0
ans = 0
while que:
    ci, p = que.popleft()

    end = 0
    que2 = deque([(ci, 0)])

    while que2:
        ci2, end_d = que2.popleft()
        end = max(end, end_d)
        for ni2 in G[ci2]:
            if visited[ni2] > visited[ci2]:
                que2.append((ni2, end_d+1))
    if ci != v:
        ans = max(ans, end+visited[ci]//2)
    # print(ci, end, visited[ci], ans)

    for ni in G[ci]:
        if visited[ni] < visited[ci]:
            que.append((ni, ci))
print(ans)

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]) - 1:
            ans = max(ans, lca.depth[v] + lca.depth[i] - 2*lca.depth[vc] - 1)
print(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 + 1) // 2)

Submission status: Wrong Answer

Solution code:
from sys import stdin
input=stdin.readline
n,u,v=map(int,input().split())
tree={}
for i in range(n-1):
    an,bn=map(int,input().split())
    #双方向に辺生成
    tree.setdefault(an,[]).append(bn)
    tree.setdefault(bn,[]).append(an)
    
def trelen(x,y):#tree内のx→yの最短距離
    dist=[-1]*(n+1)
    stack=[]
    stack.append(x)
    dist[x]=0
    while stack:
        label=stack.pop(-1)
        for i in tree[label]:
            if dist[i]==-1:
                dist[i]=dist[label]
                stack+=[i]
            if i==y:
                return dist[y]
    

count=0#vの移動回数
while(u!=v):
    umove=tree[u]
    vmove=tree[v]
    
    #uの行動
    if u==v:
        break
    
    if len(umove)==1:#辺が1つしかないときはそこを移動するしかない
        u=umove[0]
    else:
        dist=0
        move=umove[0]
        for i in range(len(umove)):
            d=trelen(v,umove[i])
            if dist<d:
                dist=d
                move=umove[i]
        u=move
                
        
    
    
    
    #vの行動
    if u==v:
        break
    
    if len(vmove)==1:#辺が1つしかないときはそこを移動するしかない
        v=vmove[0]
        count+=1
    else:
        dist=1000000
        move=vmove[0]
        for i in range(len(vmove)):
            d=trelen(v,vmove[i])
            if dist>d:
                dist=d
                move=vmove[i]
        v=move
        count+=1
        
    
    
print(count)

Submission status: Wrong Answer

Solution code:
n,v,u=map(int,input().split())
#行き先を格納
edge=[[] for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
#print(edge)

t=0
vpast = list([v])
upast = list([u])
while 1:
  vnow = [edge[vn-1] for vn in vpast]
  V=[]
  for es in vnow:
    for e in es:
      V.append(e)
  t+=1
  for v in V:
    if v in upast:
      print(t)
      break
  #print('v-now: ', V)
  unow = [edge[un-1] for un in upast]
  U=[]
  for es in unow:
    for e in es:
      U.append(e)
  if len(U)==1:
    if U[0] in V:
      print(t)
      break
  #print('u-now: ', U)
  vpast = V
  upast = U
  #break

Submission status: Wrong Answer

Solution code:
from collections import deque
def main():
    N, u, v = [int(i) for i in input().split()]
    u -= 1
    v -= 1
    graph = [[] for _ in range(N)]
    for i in range(N-1):
        a,b = [int(i) for i in input().split()]
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)
    tree = [[] for _ in range(N)]
    parents = [-1] * N
    
    stack = deque([(v, -1)])
    while len(stack) > 0:
        current, parent = stack.pop()
        parents[current] = parent
        for n in graph[current]:
            if parent == n:
                continue
            stack.append((n, current))
            tree[current].append(n)
    
    current = u
    distance = 0
    while current != v:
        current = parents[current]
        distance += 1
    current = u
    cnt = 0
    res = 0
    print(distance)
    from_n = -1
    while distance != 0:
        # print("checking %d" % current)
        stack = deque([(current, 0)])
        cnmax = 0
        # print(current)
        while len(stack) > 0:
            root, cn = stack.pop()
            cnmax = max(cn, cnmax)
            for c in tree[root]:
                if(c != from_n):
                    stack.append((c, cn+1))
            # print(cn)
        # print("---")
        res = max(res, cnmax + ((distance+1) // 2))
        from_n = current
        current = parents[current]
        if current == -1:
            break
        cnt += 1
        # res = max(res, cnmax + cnt)
        distance -= 2
    print(res)
        
main()

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

di_lst = []
N, U, V = map(int, input().split())
edges = {tuple(map(int, input().split())) for i in range(N - 1)}

stack = deque()


def BFS(X, edges, N):
    roots = [set() for _ in range(N + 1)]
    for a, b in edges:
        roots[a].add(b)
        roots[b].add(a)
    dist = {}
    stack = deque()
    stack.append(X)
    dist[X] = 0
    while stack:
        parent = stack.pop()
        for child in roots[parent]:
            if not child in dist:
                dist[child] = dist[parent] + 1
                stack.append(child)
    return dist


U_dist = BFS(U, edges, N)
V_dist = BFS(V, edges, N)

ans = 0
for i in range(1, N + 1):
    u, v = U_dist[i], V_dist[i]
    if u > v:
        ans = max(v - 1, ans)
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))

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

Submission status: Wrong Answer

Solution code:
#メモ，葉もしくはその一つ手前でぶつかるはず？
import heapq
class Dijkstra():
    """
    ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
    ・負のコストがない場合のみ
    ・計算量はO(E log|V|)　
    ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
    """
    
    #最短のpathをたす
    
    
    class Edge():
        #重み付き有向辺
        
        def __init__(self, _to, _cost):
            self.to =_to
            self.cost = _cost
    
    def __init__(self, V):
        #引数Vは頂点数
        self.G = [[] for _ in range(V)] #隣接リストG[u][i]が頂点uのi番目の辺
        self. _E = 0 #辺の数
        self._V = V #頂点数
    
    #proparty - 辺の数
    def E(self):
        return self._E
    
    #proparty - 頂点数
    def V(self):
        return self._V
    
    def add(self, _from, _to, _cost):
        #2頂点と辺のコストを追加
        self.G[_from].append(self.Edge(_to,_cost))
        self._E +=1
        
    def add2(self, _from, _to, _cost):
        #2頂点と辺のコスト（無向）を追加
        self.G[_from].append(self.Edge(_to, _cost))
        self.G[_to].append(self.Edge(_from, _cost))
        self._E +=1
        
    def shortest_path(self,s):
        #始点sから頂点iまでの最短経路長のリストを返す
        
        que = [] #priority queue
        d = [float("inf")] * self.V()
        prev = [None]*self.V() #prev[j]は，sからjへ最短経路で行くときのjの一つ前の場所
        d[s] = 0
        heapq.heappush(que,(0,s)) #始点の距離と頂点番号をヒープに追加
        
        while len(que)!=0:
            #キューに格納されてある中で一番コストが小さい頂点を取り出す
            cost,v = heapq.heappop(que)
            
            #キューに格納された最短経路長候補がdの距離よりも大きい場合に処理をスキップ
            if d[v] < cost:
                continue
                
            #頂点vに隣接する各頂点iに対して，vを経由した場合の距離を計算して，これがd[i]よりも小さい場合に更新
            for i in range(len(self.G[v])):
                e = self.G[v][i] #vのi個目の隣接辺
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost #更新
                    prev[e.to] = v
                    heapq.heappush(que,(d[e.to],e.to)) #queに新たな最短経路長候補を追加
                    
        return d

    

N, u, v = map(int, input().split())
list=[[] for _ in range(N)]
djk = Dijkstra(N)

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

root_num=0
for i in range(N):
    if len(list[i])>root_num:
        root_num=i

d=djk.shortest_path(u-1)
path_to_leaf=[]

for i in range(N):
    if len(list[i])==1:
        path_to_leaf.append(d[i])

ans = max(path_to_leaf)-1
print(ans)

Submission status: Wrong Answer

Solution code:
N,u,v = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N-1)]
    
x = [[] for _ in range(N)]
for ab in AB:
  a = ab[0]
  b = ab[1]
  x[a-1].append(b-1)
  x[b-1].append(a-1)
  
flag1 = [False]*N
flag2 = [False]*N
length1 = [0]*N
length2 = [0]*N
go = [v-1]
while go!=[]:
  a = go.pop()
  if flag1[a]:
    continue
  else:
    flag1[a]=True
    for i in x[a]:
      if flag1[i]:
        continue
      else:
        length1[i]=length1[a]+1
        go.append(i)

go = [u-1]
while go!=[]:
  a = go.pop()
  if flag2[a]:
    continue
  else:
    flag2[a]=True
    for i in x[a]:
      if flag2[i]:
        continue
      else:
        length2[i]=length2[a]+1
        go.append(i)
        
print(length1[v-1]-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heappop, heappush
from collections import defaultdict
N, u, v = list(map(int, input().split()))
u = u - 1
v = v - 1
T = defaultdict(list)

lenList = [-1] * N

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


q = deque()
q.append(u)

while q:
    i = q.popleft()
    for t in T[i]:
        if lenList[t] == -1:
            lenList[t] = lenList[i] + 1
            q.append(t)


shortest = lenList[v]


maxLen = 0
lenList2 = [-1] * N

for l in lenList:
    shortest2 = shortest // 2
    if shortest2 == l:
        q.append(l)
        lenList2[l] = 0

while q:
    i = q.popleft()
    for t in T[i]:
        if lenList2[t] == -1 and t != v:
            tmp = lenList2[i] + 1
            lenList2[t] = tmp
            if maxLen < tmp:
                maxLen = tmp
            q.append(t)


if shortest % 2 == 0:
    print(max(0, shortest//2 + maxLen-1))
else:
    print(shortest//2 + maxLen)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

N, u, v = map(int, input().split())
u -= 1
v -= 1
adj = defaultdict(list)
for i in range(N - 1):
    Ai, Bi = map(lambda x: int(x) - 1, input().split())
    adj[Ai].append(Bi)
    adj[Bi].append(Ai)

A = [0] * N
stack = deque()
stack.append(v)
while len(stack) > 0:
    e = stack.popleft()
    for a in adj[e]:
        if a == v or A[a] != 0:
            continue
        A[a] = A[e] + 1
        stack.append(a)

T = [0] * N
stack = deque()
stack.append(u)
while len(stack) > 0:
    e = stack.popleft()
    for a in adj[e]:
        if a == u or T[a] != 0 or A[a] < T[e] + 1:
            continue
        T[a] = T[e] + 1
        stack.append(a)
max_T = max(T)
max_i = [i for i, t in enumerate(T) if t == max_T]
ans = 0
for i in max_i:
    ans = max(ans, A[i] - 1)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N,u,v = II()
A,B = Line(N-1,2)

def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if directed==False:
            pt[t[i]-1].append(s[i]-1)
    return pt

def bfs(pt,v):
    n = len(pt)
    d = [-1]*n
    d[v] = 0
    q = [v]
    c = 1
    while q:
        q1 = []
        for i in q:
            for j in pt[i]:
                if d[j]==-1:
                    d[j] = c
                    q1.append(j)
        q = q1
        c += 1
    return d

pt = edges_to_pt(A,B,N)
du = bfs(pt,u-1)
dv = bfs(pt,v-1)

ans = -float('inf')
#print(du)
#print(dv)
for i in range(N):
    if du[i]>=dv[i]:
        continue
    if du[i]==0:
        temp = max(0,dv[i]-1)
    else:
        if (du[i]-dv[i])%2==0:
            temp = dv[i]
        else:
            temp = max(0,dv[i]-1)

    ans = max(ans,temp)

print(ans)

Submission status: Wrong Answer

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

n, u, v = map(int, input().split())
conn = {}
for _ in range(n-1):
    ai, bi = map(int, input().split())
    if conn.get(ai):
        conn.get(ai).add(bi)
    else:
        conn[ai] = {bi}
        
    if conn.get(bi):
        conn.get(bi).add(ai)
    else:
        conn[bi] = {ai}
    
def hoge(start, geta, dist_dict):
    dist_dict[start] = geta
    for i in conn[start]:
        if dist_dict.get(i) == None:
            hoge(i, geta + 1, dist_dict)

    
u_dist = {} # 子
hoge(u, 0, u_dist)
v_dist = {} # 鬼
hoge(v, 0, v_dist)

if (u_dist[1] - v_dist[1]) % 2: # 子の手番で捕まる
    print(max([val for k, val in u_dist.items() if val < v_dist[k]]))
else: # 鬼の手番で捕まる
    print(1 + max([val for k, val in u_dist.items() if val < v_dist[k]]))