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:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N,u,v = inputMap()
	g = Graph()

	for i in range(N-1):
		A,B = inputMap()
		g.add_edge(A, B, 1)
		g.add_edge(B, A, 1)

	d = Dijkstra(g, u)
	tmp = d.shortest_distance(v)

	print(tmp-1)


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

if __name__ == "__main__":
	main()

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,w[i])
                    
    return ans


bfs(a)
ans=t_bfs(t)

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

Submission status: Wrong Answer

Solution code:
n,u,v=map(int,input().split())
u-=1
v-=1
d=[[]for _ in range(n)]
inf=float('inf')
aoki=[inf]*n
for i in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  d[a].append(b)
  d[b].append(a)
Q=d[v]
aoki[v]=0
dis=1
visited={v}
while Q:
  P=[]
  for i in Q:
    visited.add(i)
    for j in d[i]:
      if j not in visited:P.append(j)
    aoki[i]=dis
  dis+=1
  Q=P
Q=d[u]
chokudai=[-1]*n
chokudai[u]=0
dis=1
visited={u}
point=-1
while Q:
  P=[]
  for i in Q:
    visited.add(i)
    for j in d[i]:
      if aoki[j]<=dis+1:
        if point<0:point=i
        continue
      if j not in visited:P.append(j)
    chokudai[i]=dis
  dis+=1
  Q=P
Q=d[point]
dis=chokudai[point]+1
visited={point}
while Q:
  P=[]
  for i in Q:
    visited.add(i)
    if chokudai[i]==-1:continue
    if dis<=aoki[i]:continue
    chokudai[i]=max(dis,chokudai[i])
    for j in d[i]:
      if j not in visited:P.append(j)
  dis+=1
  Q=P
ans=0
for i in range(n):
  if aoki[i]>=chokudai[i]:ans=max(ans,chokudai[i])
print(ans)
#print(aoki)
#print(chokudai)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N,u,v = inputMap()
	g = Graph()

	for i in range(N-1):
		A,B = inputMap()
		g.add_edge(A, B, 1)
		g.add_edge(B, A, 1)

	d = Dijkstra(g, u)
	tmp = d.shortest_distance(v)

	print(tmp)


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from collections import deque
n,u,v=map(int,input().split())
u-=1
v-=1
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
q=deque([[v,0,0]])
x=[0]*n
x[v]=1
ans=0
while q:
    p=q.popleft()
    for i in g[p[0]]:
        if x[i]==0:
            x[i]=1
            if i==u:
                q.append([i,p[1]+1,1])
                ans=max(ans,p[1]+1)
            else:
                q.append([i,p[1]+1,p[2]])
                if p[2]==1:
                    ans=max(ans,p[1]+1)
print(ans)
   
  
  
exit()
uv=f
if len(uv)%2==0:
    nu=uv[len(uv)//2-1]
    ans=len(uv)//2-1
else:
    nu=uv[len(uv)//2-1]
    ans=len(uv)//2-1
y=[0]*n
y[len(uv)//2]=1
y[nu]=1
q=deque([[nu,0]])
z=0
while q:
    p=q.popleft()
    for i in g[p[0]]:
        if y[i]==0:
            y[i]=1
            q.append([i,p[1]+1])
            z=max(z,p[1]+1)
print(ans+z)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, u, v, AB):
    ans = 0
    g = defaultdict(set)
    for a, b in AB:
        g[a].add(b)
        g[b].add(a)


    def f(start):
        s = [(start, 0)]
        d = {}
        d[start] = 0
        while s:
            c, l = s.pop()
            for n in g[c]:
                if n not in d:
                    s.append((n, l+1))
                    d[n] = l+1
        return d

    vd = f(v)
    t = u
    a = v
    s = [(t, 0)]
    d = defaultdict(lambda : 0)
    d[t] = 0
    while s:
        u, l = s.pop()
        for v in g[u]:
            if v not in d and l + 1 < vd[v]:
                s.append((v, l+1))
                tmp = vd[v] - (l+1)
                tmp = (tmp//2) * 2
                d[v] = tmp + (l+1)
    dest = (0, -1)
    for k, v in d.items():
        dest = max(dest, (v, k))

    ans = dest[0]
    # error_print(dest)
    # error_print(d)
    # error_print(vd)
    if vd[dest[1]] - dest[0] > 1:
        ans += 1
    return ans


def main():
    N, u, v = read_int_n()
    AB = [read_int_n() for _ in range(N-1)]
    print(slv(N, u, v, AB))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

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

if u == v:
    print(0)
    exit()

memov = [-1] * n
q = deque()
memov[v] = 0
q.append((v, 0))

while q:
    v_, d = q.popleft()
    for nv in g[v_]:
        if memov[nv] != -1:
            continue
        memov[nv] = d + 1
        q.append((nv, d+1))

memou = [-1] * n
q = deque()
memou[u] = 0
q.append((u, 0))

while q:
    v_, d = q.popleft()
    for nv in g[v_]:
        if memou[nv] != -1:
            continue
        if d + 1 >= memov[nv]:
            memou[nv] = 0
            continue
        memou[nv] = d + 1
        q.append((nv, d+1))



ans = 0
max_v = -1
for i in range(n):
    if memou[i] > ans:
        ans = memou[i]
        max_v = i
diff = memov[max_v] - memou[max_v]
if diff == 0:
    print(ans)
    exit()

if diff > 2:
    ans += (diff - 2)
    diff = 1 if diff % 2 == 1 else 2
if diff == 1:
    print(ans)
    exit()
if diff == 2:
    print(ans + 1)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,u,v=map(int,input().split())
u-=1
v-=1
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
q=deque([[v,0,0]])
x=[0]*n
x[v]=1
ans=0
while q:
    p=q.popleft()
    for i in g[p[0]]:
        if x[i]==0:
            x[i]=1
            if i==u:
                q.append([i,p[1]+1,1])
                ans=max(ans,p[1]+1)
            else:
                q.append([i,p[1]+1,p[2]])
                if p[2]==1:
                    ans=max(ans,p[1]+1)
    print(ans)
   
  
  
exit()
uv=f
if len(uv)%2==0:
    nu=uv[len(uv)//2-1]
    ans=len(uv)//2-1
else:
    nu=uv[len(uv)//2-1]
    ans=len(uv)//2-1
y=[0]*n
y[len(uv)//2]=1
y[nu]=1
q=deque([[nu,0]])
z=0
while q:
    p=q.popleft()
    for i in g[p[0]]:
        if y[i]==0:
            y[i]=1
            q.append([i,p[1]+1])
            z=max(z,p[1]+1)
print(ans+z)

Submission status: Wrong Answer

Solution code:
import sys
#input = sys.stdin.readline
from collections import deque
N, u, v = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
v-=1
u-=1
que = deque([v])
par = [-1]*N
depth = [-1]*N
depth[v] = 0
while que:
    i = que.popleft()
    d = depth[i]
    for nv in G[i]:
        if depth[nv]>=0:
            continue
        depth[nv] = d+1
        par[nv] = i
        que.append(nv)
d = depth[u]
now = u
m = 0
que = deque([now])
while que:
    p = que.popleft()
    if m<depth[p]:
        m = depth[p]
    for nv in G[p]:
        if depth[nv]<depth[p]:
            continue
        que.append(nv)
for i in range(d//2):
    pp = par[now]
    que = deque([p])
    while que:
        p = que.popleft()
        if m<depth[p]:
            m = depth[p]
        for nv in G[p]:
            if depth[nv]<depth[p] or nv == now:
                continue
            que.append(nv)
    now = pp
print(m-1)

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
    elif len(pt[i])>=2:
        continue
    elif du[i]==0:
        if dv[i]==1:
            ans = 0
    else:
        if (du[i]-dv[i])%2==0:
            temp = dv[i]
        else:
            temp = max(0,dv[i]-1)
        #print(i,temp)
        ans = min(ans,temp)
if ans==float('inf'):
    ans = 1
print(ans)

Submission status: Wrong Answer

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

u -= 1
v -= 1
G = [set() for _ in range(N)]
for a, b in AB:
    G[a - 1].add(b - 1)
    G[b - 1].add(a - 1)


du = [-1] * N
du[u] = 0
q = set([u])
while q:
    i = q.pop()
    for j in G[i]:
        if du[j] == -1:
            du[j] = du[i] + 1
            q.add(j)

dv = [-1] * N
dv[v] = 0
q = set([v])
while q:
    i = q.pop()
    for j in G[i]:
        if dv[j] == -1:
            dv[j] = dv[i] + 1
            q.add(j)

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

if du[v] % 2 == 0:
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n,u,v=map(int,input().split())
u-=1
v-=1
d=[[]for _ in range(n)]
inf=float('inf')
aoki=[inf]*n
for i in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  d[a].append(b)
  d[b].append(a)
Q=d[v]
aoki[v]=0
dis=1
visited={v}
while Q:
  P=[]
  for i in Q:
    visited.add(i)
    for j in d[i]:
      if j not in visited:P.append(j)
    aoki[i]=dis
  dis+=1
  Q=P
Q=d[u]
chokudai=[-1]*n
chokudai[u]=0
dis=1
visited={u}
point=-1
while Q:
  P=[]
  for i in Q:
    visited.add(i)
    for j in d[i]:
      if aoki[j]<=dis+1:
        if point<0:point=i
        continue
      if j not in visited:P.append(j)
    chokudai[i]=dis
  dis+=1
  Q=P
Q=d[point]
dis=chokudai[point]+1
visited={point}
while Q:
  P=[]
  for i in Q:
    visited.add(i)
    if chokudai[i]==-1:continue
    chokudai[i]=max(dis,chokudai[i])
    for j in d[i]:
      if j not in visited:P.append(j)
  dis+=1
  Q=P
ans=0
anss=-1
for i in range(n):
  if aoki[i]>chokudai[i]:ans=max(ans,chokudai[i])
  if aoki[i]==chokudai[i]:
    if anss<0:anss=chokudai[i]
    else:anss=min(anss,chokudai[i])
print(max(ans,anss))

Submission status: Wrong Answer

Solution code:
import sys
n,u,v=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n-1)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)

def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

x=bfs(u-1)
y=bfs(v-1)
ans=[]
e=[]
for i in range(n):
  if x[i]<y[i] and x[i]!=0:
    if abs(x[i]-y[i])%2==0:
      if x[i]%2==1:
        ans.append(y[i]-1)
      else:
        ans.append(y[i])
    else:
      ans.append(y[i]-1)
if len(ans)==0:
  if x[v-1]==1:
    print(0)
  else:
    print(1)
  sys.exit()
print(max(ans))

Submission status: Wrong Answer

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


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def dfs(N, L, s, node = None, blocks = None):
    depth = [-1] * N

    stack = [(0, s)]
    while stack:
        d, p = stack.pop()
        depth[p] = d

        if blocks is not None:
            if d == 0:
                depth[p] = -1
            else:
                if d == blocks[p]:
                    continue

                if node is not None and p in node:
                    depth[p] =  d + 2 * ((blocks[p] - d) // 2)
                    continue

        for q in L[p]:
            if blocks is not None:
                if blocks[q] < d + 1:
                    continue

            if depth[q] != -1:
                continue
            stack.append((d + 1, q))
    return depth

    
def main():
    N, u, v = read_values()
    u -= 1
    v -= 1
    L = [set() for _ in range(N)]
    for _ in range(N - 1):
        A, B = read_values()
        A -= 1
        B -= 1
        L[A].add(B)
        L[B].add(A)

    node = {i for i in range(N) if len(L[i]) == 1} 
    depth_A = dfs(N, L, v)
    depth_T = dfs(N, L, u, node, depth_A)

    # print(depth_A)
    # print(depth_T)
    res = 0
    for i in range(N):
        a = depth_A[i]
        t = depth_T[i]
        if t <= 0: 
            continue
        res = max(res, t + 2 * ((a - t) // 2))

    print(res)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np

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

vds = [-1]*n

qp = deque([])

qp.append(v-1)

vds[v-1] = 0

while qp:
    now = qp.pop()
    for nxt in neighbors[now]:
        if vds[nxt] == -1:
            qp.appendleft(nxt)
            vds[nxt] = vds[now] + 1

print(max(vds)-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

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

dis=dA[T]
'''
print(a)
print(dT)
print(dA)
'''
l=[i for i in range(N) if dT[i]<=dA[i]]
MdA=max([dA[i] for i in range(N) if i in l])
g=dA.index(MdA) # Tが目指すべきゴール

kT=dT[g] # Tが到達に要する手数
kA=dA[g] # Aが到達に要する手数
# print(g)
# print(kT,kA)
# print(dis)
if kT==kA and dis<=kT:
    ans=dis//2
else:
    ans=kT+max(kA-kT-1,0)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n,u,v=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n-1)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)

def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

x=bfs(u-1)
y=bfs(v-1)
ans=[]
e=[]
for i in range(n):
  if x[i]<y[i] and x[i]!=0:
    if abs(x[i]-y[i])%2==0:
      if x[i]==1:
        ans.append(y[i]-1)
      else:
        ans.append(y[i])
    else:
      ans.append(y[i]-1)
if len(ans)==0:
  if x[v-1]==1:
    print(0)
  else:
    print(1)
  sys.exit()
print(max(ans))

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)

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):
  if (A[i] - T[i]) % 2 == 0:
    if T[i] < A[i]:
      answer.append(T[i] + (A[i] - T[i]) // 2)
  else:
    if T[i] < A[i]:
      if T[i] == 0 and len(graph[u]) == 1 and A[i] - T[i] == 1:
        answer.append(0)
      else:
        answer.append(T[i] + (A[i] - T[i]) // 2 + 1)
print(max(answer))

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np

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

vds = [-1]*n

qp = deque([])

qp.append(v-1)

vds[v-1] = 0

while qp:
    now = qp.pop()
    for nxt in neighbors[now]:
        if vds[nxt] == -1:
            qp.appendleft(nxt)
            vds[nxt] = vds[now] + 1

uds = [-1]*n

qp.append(u-1)

uds[u-1] = 0

while qp:
    now = qp.pop()
    for nxt in neighbors[now]:
        if uds[nxt] == -1 and nxt != v-1:
            qp.appendleft(nxt)
            uds[nxt] = uds[now] + 1
    
vds = np.array(vds)
uds = np.array(uds)
anls = vds + uds
ans = np.amax(anls)
for i in range(n):
    if anls[i] == ans:
        print(vds[i]-1)
        break

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]
    
N, u, v = map(int, input().split())
g = Graph()
for i in range(N-1):
    a, b = map(int, input().split())
    g.add_edge(a, b, 1)
    g.add_edge(b, a, 1)
d1 = Dijkstra(g, u)
d2 = Dijkstra(g, v)

max_dist = 0
same_dist = 0
for i in range(1,N+1):
    s1 = d1.shortest_distance(i)
    s2 = d2.shortest_distance(i)
    if s1 < s2:
        if s1 > max_dist:
            max_dist = s1
    elif s1 == s2:
        if s1 < same_dist or same_dist==0:
            same_dist = s1

print(max(max_dist,same_dist))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
minans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**7)

n,u,v=map(int,input().split())
u-=1;v-=1
G=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    G[a].append(b)
    G[b].append(a)
D=[-1]*n
maxD=[-1]*n

def make_tree_dfs(n,d):
    D[n]=d
    tmp=0
    f=True
    for gi in G[n]:
        if D[gi]==-1:
            f=False
            tmp=max(tmp,make_tree_dfs(gi,d+1))
    if f: tmp=d
    maxD[n]=tmp
    return tmp

make_tree_dfs(v,0)
sdis=D[u]

def good_dfs(v,d,sdis):
    f=True
    for gi in G[v]:
        if D[gi]==d-1 and d-1>sdis-(d-1):
            return good_dfs(D[gi],d-1,sdis)
    return (maxD[v],d)

gd,orid=good_dfs(u,D[u],sdis)
k=orid-(sdis-orid)
print(gd-orid+(sdis-orid)+k-1)
# print(D)
# print(maxD)
# print(sdis,orid,gd,k)