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 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]:
                if w[c]+1>v[i]:
                    w[i]=-inf
                else:
                    w[i]=w[c]+1
                    if w[c]==v[c]:
                        ans=max(ans,w[c])
                    else:
                        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:
# -*- coding: utf-8 -*-

def solve():
    N, u, v = map(int, input().split())
    G = [[] for _ in range(N+1)]
    dv = [float('inf') for _ in range(N+1)]
    du = [float('inf') for _ in range(N+1)]
    d = [float('inf') for _ in range(N+1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        G[a].append(b)
        G[b].append(a)
    Q = [v]
    dv[v]=0
    while Q:
        n = Q.pop()
        for p in G[n]:
            if dv[p] == float('inf'):
                dv[p] = dv[n]+1
                Q.append(p)
    Q = [u]
    du[u]=0
    while Q:
        n = Q.pop()
        for p in G[n]:
            if du[p] == float('inf'):
                du[p] = du[n]+1
                Q.append(p)

    Q = [u]
    d[u]=0
    while Q:
        n = Q.pop()
        for p in G[n]:
            if d[p] == float('inf') and du[p] < dv[p]:
                d[p] = d[n]+1
                Q.append(p)
    D = min(a for a,b in zip(du,dv) if a==b)
    if D==float('inf'):
        D = 0
    d_max = max(a for a in d if a!=float('inf'))

    res = max(D, d_max)
    return str(res)

if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

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

import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

#n,w = map(int,input().split()) #n:頂点数　w:辺の数
edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(n-1):
    z=1
    x,y = map(int,input().split())
    x-=1;y-=1
    edge[x].append([z,y]) #有向辺
    edge[y].append([z,x]) #有向辺
A=dijkstra_heap(u)
B=dijkstra_heap(v)
l=[]
#print(A)
#print(B)
for i in range(n):
    l.append([A[i],B[i]])
l.sort()
l=l[::-1]
#print(l)
ans_1=float('inf')
ans_2=float('inf')
for i in range(n):
    if l[i][0]+1==l[i][1]:
        ans_1=l[i][0]
        break
for i in range(n):
        if l[i][0]==l[i][1]:
            ans_2=l[i][0]
print(min(ans_1,ans_2))

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([[u,[u]]])
x=[0]*n
x[u]=1
f=[]
while q:
    p=q.popleft()
    for i in g[p[0]]:
        if i==v:
            f=p[1]+[v]
            break
        if x[i]==0:
            x[i]=1
            q.append([i,p[1]+[i]])
    if len(f)>0:
        break
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
exit()
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
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)

def calcDist(cur, par, dst, lst):
    lst[cur] = dst
    for neighbour in graph[cur]:
        if neighbour == par: continue
        calcDist(neighbour, cur, dst + 1, lst)
        
uDist = [[] for i in range(N)]
vDist = [[] for i in range(N)]
calcDist(u, -1, 0, uDist)
calcDist(v, -1, 0, vDist)

best = 0
for node in range(N):
    if uDist[node] <= vDist[node]:
        if any(vDist[n] > vDist[node] for n in graph[node]) or (vDist[node]%2!=uDist[node]%2):
            best = max(best, uDist[node])
        else:
            best = max(best, uDist[node] - 1)
print(best)

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:
    i = que.popleft()
    if m<depth[i]:
        m = depth[i]
    for nv in G[i]:
        if depth[nv]<depth[i]:
            continue
        que.append(nv)
for i in range(d//2):
    now = par[now]
    que = deque([now])
    while que:
        p = que.popleft()
        if m<depth[i]:
            m = depth[i]
        for nv in G[p]:
            if depth[nv]<depth[p]:
                continue
            que.append(nv)
print(m-1)

Submission status: Wrong Answer

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

def hoge(start, geta, dist_dict):
    dist_dict[start] = geta
    for i, e in enumerate(g[start]):
      if e == 1 and dist_dict.get(i) == None:
        hoge(i, geta + 1, dist_dict)

    
u_dist = {}
hoge(u - 1, 0, u_dist)
v_dist = {}
hoge(v - 1, 0, v_dist)

print(max([v for k, v in u_dist.items() if v < v_dist[k]]) + (0 if v_dist[u - 1] % 2 else 1))

Submission status: Wrong Answer

Solution code:
2

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,x,y=map(int,input().split())
    x-=1; y-=1

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

    # x から y への path を作る(depthも)
    Q=[(x,-1)]
    prev=[None]*n
    prev[x]=-1
    depth=[None]*n
    depth[x]=0
    while(Q):
        v,p=Q.pop()
        for nv in E[v]:
            if(nv==p): continue
            prev[nv]=v
            depth[nv]=depth[v]+1
            Q.append((nv,v))

    z=y
    path=[]
    while(z!=-1):
        path.append(z)
        z=prev[z]

    # y からの depth
    Q=[(y,-1)]
    depth2=[None]*n
    depth2[y]=0
    while(Q):
        v,p=Q.pop()
        for nv in E[v]:
            if(nv==p): continue
            depth2[nv]=depth2[v]+1
            Q.append((nv,v))

    k=len(path)
    s,t=path[k//2-1],path[k//2]

    Q=[(x,-1)]
    depth3=[0]*n
    while(Q):
        v,p=Q.pop()
        for nv in E[v]:
            if(nv==p): continue
            if((v,nv)==(s,t) or (v,nv)==(t,s)): continue
            depth3[nv]=depth3[v]+1
            Q.append((nv,v))


    d1,l=max((depth3[v],v) for v in range(n))
    d2=depth2[l]
    # print(path)
    # print(d1,d2)
    ans=min(d1,d2)
    if((d1+d2)&1==0):
        ans-=1

    print(max(0,ans))
resolve()

Submission status: Wrong Answer

Solution code:
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def bitlist(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

#a = list(map(int, input().split()))

n,a,b = list(map(int, input().split()))
es = [[] for i in range(n+1)]

for i in range(n-1):
    p,q = list(map(int, input().split()))
    es[p].append(q)
    es[q].append(p)

dista = [9999999 for i in range(n+1)]
distb = [9999999 for i in range(n+1)]



dista[a]=0
distb[b]=0

queue = [[a,0]]
snum = 0
while(True):
    if(snum==len(queue)):
        break
    nowel = queue[snum]
    nowv = nowel[0]
    #print(nowv)
    nowdist = nowel[1]
    #print(nowdist)
    elist = es[nowv]
    for j in range(len(elist)):
        if(dista[elist[j]]>9999990):
            queue.append([elist[j],nowdist+1])
            dista[elist[j]] = nowdist+1
    snum+=1
#print(dista)


queue = [[b,0]]
snum = 0
while(True):
    if(snum==len(queue)):
        break
    nowel = queue[snum]
    nowv = nowel[0]
    #print(nowv)
    nowdist = nowel[1]
    #print(nowdist)
    elist = es[nowv]
    for j in range(len(elist)):
        if(distb[elist[j]]>9999990):
            queue.append([elist[j],nowdist+1])
            distb[elist[j]] = nowdist+1
    snum+=1
#print(distb)

acan = [0 for i in range(n+1)]

for ii in range(n):
    i = ii+1
    if(dista[i] < distb[i]):
        acan[i]=1

maxa = 0

for ii in range(n):
    i = ii+1
    if(maxa < dista[i] and acan[i]==1):
        maxa = dista[i]

print(maxa)

Submission status: Wrong Answer

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

class LCA:
    def __init__(self,v,Edges,root=0):
        self.v=v
        self.Edges=Edges
        self.maxLog=18
        self.Parent=[[-1]*v for _ in range(self.maxLog+1)]
        self.Depth=[0]*v
        self.__bfs(root)
        for i in range(self.maxLog):
            for j in range(v):
                if self.Parent[i][j]!=-1:
                    self.Parent[i+1][j]=self.Parent[i][self.Parent[i][j]]
    def __bfs(self,root):
        Visited=[False]*self.v
        Visited[root]=True
        q=deque([root])
        while q:
            fr=q.pop()
            for to in self.Edges[fr]:
                if Visited[to]:
                    continue
                self.Parent[0][to]=fr
                self.Depth[to]=self.Depth[fr]+1
                Visited[to]=True
                q.append(to)
    def lca(self,a,b):
        if self.Depth[a]>self.Depth[b]:
            a,b=b,a
        for i in range(self.maxLog):
            if (self.Depth[b]-self.Depth[a])&(1<<i):
                b=self.Parent[i][b]
        if a==b:
            return b
        for i in reversed(range(self.maxLog-1)):
            if self.Parent[i][a]!=self.Parent[i][b]:
                a=self.Parent[i][a]
                b=self.Parent[i][b]
        return self.Parent[0][a]
    def dist(self,a,b):
        lca=self.lca(a,b)
        return self.Depth[a]+self.Depth[b]-2*self.Depth[lca]

def main():
    n,u,v=map(int,input().split())
    u-=1; v-=1
    Edges=[[] for _ in range(n)]
    for _ in range(n-1):
        x,y=map(lambda i: int(i)-1,input().split())
        Edges[x].append(y)
        Edges[y].append(x)
    L=[]
    for i in range(n):
        if len(Edges[i])==1:
            L.append(i)
    lca=LCA(n,Edges)
    ans=lca.dist(u,v)//2
    for l in L:
        d_u=lca.dist(u,l)
        d_v=lca.dist(v,l)
        if d_u>=d_v:
            continue
        else:
            d=d_v-d_u
            cnt=max(0,d//2*2-1)
            ans=max(ans,d_u+cnt)
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
print("123".replace(input(),"").replace(input(),""))

Submission status: Wrong Answer

Solution code:
from collections import deque
N, U, V = map(int, input().split())
U -= 1
V -= 1
tree = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)


def get_rank(v):
    rank = [-1] * N
    next_v = deque([v])
    rank[v] = 0
    while next_v:
        node = next_v.popleft()
        r = rank[node]
        for i in tree[node]:
            if rank[i] != -1:
                continue
            rank[i] = r + 1
            next_v.append(i)
    return rank


# 答えはmax(rank)-1以下

takahashi = get_rank(U)
aoki = get_rank(V)
ans = 0
can_go = 0
for x, y in zip(takahashi, aoki):
    if x == 0:
        continue
    if x <= y:
        can_go = 1
        break

if can_go:
    ans = max(aoki) - 1
else:
    ans = 0
print(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, blocks = None):
    depth = [-1] * N

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

        if blocks is not None and d == blocks[p]:
            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)
    
    depth_A = dfs(N, L, v)
    depth_T = dfs(N, L, u, depth_A)

    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:
import sys
#input = sys.stdin.readline
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 = [v]
par = [-1]*N
depth = [-1]*N
depth[v] = 0
while que:
    i = que.pop()
    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 = [now]
while que:
    i = que.pop()
    m = max(m, depth[i])
    for nv in G[i]:
        if depth[nv]<depth[i]:
            continue
        que.append(nv)
for i in range(d//2):
    now = par[now]
    que = [now]
    for j in range(d):
        if not que:
            break
        p = que.pop()
        m = max(m, depth[p])
        for nv in G[p]:
            if depth[nv]<depth[p]:
                continue
            que.append(nv)
print(m-1)

Submission status: Wrong Answer

Solution code:
from collections import  deque
N,u,v=map(int,input().split())
u-=1
v-=1

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

q=deque([(v,0)])
T=[-1]*N
A=[-1]*N

while q:
    p,x=q.pop()
    A[p]=x
    for to in L[p]:
        if A[to]==-1:
            q.append((to,x+1))

q=deque([(u,0)])
while q:
    p,x=q.pop()
    T[p]=x
    for to in L[p]:
        if T[to]==-1 and A[to]>x+1:
            q.append((to,x+1))


Tcan=[i for i,x in enumerate(A) if x!=-1]
cnt,gi=max([(A[i], i) for i in Tcan]+[(0,0)])
if cnt==0:
    print(0)
    exit()
print(A[gi]-1)

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,tk,ao = MI()
    tk-=1
    ao-=1

    AB=LLIN_(N-1)
    edge = [[]for _ in range(N)]
    for a,b in AB:
        edge[a].append(b)
        edge[b].append(a)
    
    dist_from_tk = [-inf]*N
    dist_from_ao = [-inf]*N
    
    dist_from_ao[ao]=0
    q = deque([ao])
    while q:
        fr = q.popleft()
        for to in edge[fr]:
            if dist_from_ao[to]!=-inf:
                continue
            # print(fr,to,dist_from_ao)
            dist_from_ao[to]=dist_from_ao[fr]+1
            q.append(to)
    # print(dist_from_ao)

    dist_from_tk[tk]=0
    q = deque([tk])
    mid = -inf
    while q:
        fr = q.popleft()
        for to in edge[fr]:
            if dist_from_tk[to]!=-inf:
                continue
            if dist_from_ao[to]<=dist_from_tk[fr]+1:
                mid = fr
                continue
            # print(fr,to,dist_from_tk)
            dist_from_tk[to]=dist_from_tk[fr]+1
            q.append(to)
    # print("#########")
    # print(dist_from_ao)
    # print(dist_from_tk)
    # print(mid)


    dist_from_mid = [-inf]*N
    dist_from_mid[mid]=0
    q = deque([mid])
    while q:
        fr = q.popleft()
        for to in edge[fr]:
            if dist_from_mid[to]!=-inf:
                continue
            if dist_from_tk[to]==-inf:#到達不可
                continue
            # print(fr,to,dist_from_mid)
            dist_from_mid[to]=dist_from_mid[fr]+1
            q.append(to)
    # print(dist_from_mid)
    
    if dist_from_ao[tk]==1 and max(dist_from_tk)==0: ##自滅
        print(0)
    elif max(dist_from_tk)==0: ##動いたらすぐ死ぬ
        print(1)
    else:
        ans = dist_from_tk[mid]+max(dist_from_mid)
        print(ans)
    # print(dist_from_tk[mid]+max(dist_from_mid))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,u,v = (int(num) for num in input().split())
u -= 1
v -= 1
adj = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = (int(num)-1 for num in input().split())
    adj[a].append(b)
    adj[b].append(a)
    
visited = [0] * n
d = [-1] * n
q = []
q.append(u)
visited[u] = 1
d[u] = 0
while q != []:
    vt = q.pop(0)
    dt = d[vt]
    for vnext in adj[vt]:
        if visited[vnext] == 0:
            visited[vnext] = 1
            d[vnext] = dt + 1
            q.append(vnext)
            
visited = [0] * n
e = [-1] * n
q = []
q.append(v)
visited[v] = 1
e[v] = 0
while q != []:
    vt = q.pop(0)
    dt = e[vt]
    for vnext in adj[vt]:
        if visited[vnext] == 0:
            visited[vnext] = 1
            e[vnext] = dt + 1
            q.append(vnext)

ans = 0
for i in range(n):
    dd = d[i]
    de = e[i]
    yoyu = de - dd
    if yoyu > 0:
        ans = max(ans, dd + yoyu // 2)
print(ans)

Submission status: Wrong Answer

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

import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

#n,w = map(int,input().split()) #n:頂点数　w:辺の数
edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(n-1):
    z=1
    x,y = map(int,input().split())
    x-=1;y-=1
    edge[x].append([z,y]) #有向辺
    edge[y].append([z,x]) #有向辺
A=dijkstra_heap(u)
B=dijkstra_heap(v)
l=[]
#print(A)
#print(B)
for i in range(n):
    l.append([A[i],B[i]])
l.sort()
l=l[::-1]
for i in range(n):
    if l[i][0]+1==l[i][1]:
        print(l[i][0])
        break
else:
    print(1)

Submission status: Wrong Answer

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

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

depth = [-1] * N
stack = [(v-1, 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))

print(max(depth)-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
INF = 10**9

class RMQ:
    def __init__(self, a):
        self.n = len(a)
        self.size = 2**(self.n - 1).bit_length()
        self.data = [(INF, INF) for _ in range(2*self.size-1)]
        self.initialize(a)

    # Initialize data
    def initialize(self, a):
        for i in range(self.n):
            self.data[self.size + i - 1] = a[i][:]
        for i in range(self.size-2, -1, -1):
            self.data[i] = min(self.data[i*2 + 1], self.data[i*2 + 2])[:]

    # Update ak as x
    def update(self, k, x):
        k += self.size - 1
        self.data[k] = x
        while k > 0:
            k = (e - 1) // 2
            self.data[k] = min(self.data[2*k+1], self.data[2*k+2])[:]

    # Min value in [l, r)
    def query(self, l, r):
        L = l + self.size; R = r + self.size
        s = (INF, INF)
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])[:]
            if L & 1:
                s = min(s, self.data[L-1])[:]
                L += 1
            L >>= 1; R >>= 1
        return s

class LCA:
    def __init__(self, edge, root):
        self.edge = edge[:]
        self.path = []
        self.depth = []
        self.index = [0] * n
        self.euler_tour(-1, root, 0, 0)
        dat = list(zip(self.depth, self.path))
        self.rmq = RMQ(dat)

    # Lowest ancestor of u, v
    def get_lca(self, u, v):
        l, r = self.index[u], self.index[v]
        if l > r:
            l, r = r, l
        return self.rmq.query(l, r+1)[1]

    def get_depth(self, v):
        return self.depth[self.index[v]]

    def euler_tour(self, prev, v, d, k):
        self.index[v] = k
        self.path.append(v)
        self.depth.append(d)
        k += 1
        for item in self.edge[v]:
            if prev == item:
                continue
            k = self.euler_tour(v, item, d + 1, k)
            self.path.append(v)
            self.depth.append(d)
            k += 1
        return k

n, u, v = [int(item) for item in input().split()]
u -= 1; v -= 1
edge = [[] for _ in range(n)]

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

lca = LCA(edge, v)
frm = lca.get_depth(v)
too = lca.get_depth(u)
up = (too - frm - 1) // 2
max_depth = too 

def dfs(p, v, lim):
    global max_depth
    max_depth = max(max_depth, lca.get_depth(v))
    for nv in edge[v]:
        if nv == p:
            continue
        if lca.get_depth(v) < lim:
            continue
        dfs(v, nv, lim)
if too == 1 and max_depth == 1:
    print(0)
    exit()
if too == 2 and max_depth == 2:
    print(1)
    exit()

dfs(-1, u, too - up)
ans = 0
if (too - frm) % 2 == 1:
    ans = up + max_depth - (too - up)
else:
    ans = up + max_depth - (too - up) - 1
print(ans)

Submission status: Wrong Answer

Solution code:
n, u, v, *L = map(int, open(0).read().split())
dist_f_v = [-1] * n
con = [[] for _ in range(n)]
for s, t in zip(*[iter(L)] * 2):
	con[s - 1].append(t - 1)
	con[t - 1].append(s - 1)
dist_f_v[v - 1] = 0
q = [v - 1]
while q:
	cur = q.pop()
	for nxt in con[cur]:
		if dist_f_v[nxt] < 0:
			dist_f_v[nxt] = dist_f_v[cur] + 1
			q.append(nxt)
dist_f_u = [-1] * n
dist_f_u[u - 1] = 0
q = [u - 1]
m = 0
while q:
	cur = q.pop()
	m = max(m, dist_f_v[cur])
	for nxt in con[cur]:
		if dist_f_u[cur] + 1 < dist_f_v[nxt]:
			dist_f_u[nxt] = dist_f_u[cur] + 1
			q.append(nxt)
		elif dist_f_u[cur] + 1 == dist_f_v[nxt]:
			dist_f_u[nxt] = dist_f_u[cur] + 1
print(m-1)

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 and y[i]!=0:
    if abs(x[i]-y[i])%2==0:
      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
input=sys.stdin.readline
from collections import deque

class LCA:
    def __init__(self,v,Edges,root=0):
        self.v=v
        self.Edges=Edges
        self.maxLog=18
        self.Parent=[[-1]*v for _ in range(self.maxLog+1)]
        self.Depth=[0]*v
        self.__bfs(root)
        for i in range(self.maxLog):
            for j in range(v):
                if self.Parent[i][j]!=-1:
                    self.Parent[i+1][j]=self.Parent[i][self.Parent[i][j]]
    def __bfs(self,root):
        Visited=[False]*self.v
        Visited[root]=True
        q=deque([root])
        while q:
            fr=q.pop()
            for to in self.Edges[fr]:
                if Visited[to]:
                    continue
                self.Parent[0][to]=fr
                self.Depth[to]=self.Depth[fr]+1
                Visited[to]=True
                q.append(to)
    def lca(self,a,b):
        if self.Depth[a]>self.Depth[b]:
            a,b=b,a
        for i in range(self.maxLog):
            if (self.Depth[b]-self.Depth[a])&(1<<i):
                b=self.Parent[i][b]
        if a==b:
            return b
        for i in reversed(range(self.maxLog-1)):
            if self.Parent[i][a]!=self.Parent[i][b]:
                a=self.Parent[i][a]
                b=self.Parent[i][b]
        return self.Parent[0][a]
    def dist(self,a,b):
        lca=self.lca(a,b)
        return self.Depth[a]+self.Depth[b]-2*self.Depth[lca]

def main():
    n,u,v=map(int,input().split())
    u-=1; v-=1
    Edges=[[] for _ in range(n)]
    for _ in range(n-1):
        x,y=map(lambda i: int(i)-1,input().split())
        Edges[x].append(y)
        Edges[y].append(x)
    L=[]
    for i in range(n):
        if len(Edges[i])==1:
            L.append(i)
    lca=LCA(n,Edges)
    ans=0
    for l in L:
        d_u=lca.dist(u,l)
        d_l=lca.dist(v,l)
        if d_u>=d_l:
            continue
        d=d_l-d_u
        if d==1:
            cnt=0
        else:
            cnt=d//2*2-1
        ans=max(ans,d_u+cnt)
    print(ans)
    
if __name__=='__main__':
    main()