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())
inf = 10 ** 6
u -= 1
v -= 1
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  peer[a].append(b)
  peer[b].append(a)
seen = [0 for _ in range(n)]
rank = [0 for _ in range(n)]
seen[v] = 1
now = [v]
pst = [[] for _ in range(n)]
pre = [inf for _ in range(n)]
while now:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if seen[y] == 0:
        seen[y] = 1
        rank[y] = rank[x] + 1
        pst[x].append(y)
        pre[y] = x
        now.append(y)
print(rank)
r = rank[u]
if r % 2 == 0:
  m = r//2 + 1
  M = u
  for _ in range(r-m):
    M = pre[M]
  now = [M]
  while now != []:
    last = now
    now = []
    for x in last:
      for y in pst[x]:
        now.append(y)
  ans = rank[last[0]] - m + r - m + 1
  #print(r,m,M,rank[last[0]],last[0])
  #print(0,ans)
else:
  m = r//2 + 1
  M = u
  for _ in range(r-m):
    M = pre[M]
  now = [M]
  while now != []:
    last = now
    now = []
    for x in last:
      for y in pst[x]:
        now.append(y)
  ans = rank[last[0]] - m + r - m
  #print(r,m,M,rank[last[0]],last[0])
  #print(1,ans)
print(ans)

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
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:
N, u, v = map(int, input().split())
u -= 1
v -= 1

e_list = [[] for _ in range(N)]

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

def calc_depth_table(v):
	queue = [[v, None, 0]]
	depth_table = [0] * N
	depth_table[v] = 0
	
	while queue:
		cur, pre, depth = queue.pop()
		depth += 1
		for n in e_list[cur]:
			if n != pre:
				queue.append([n, cur, depth])
				depth_table[n] = depth
	return depth_table

def calc_depth_table2(depth_from_v, u):
	queue = [[u, None, 0, depth_from_v[u], u]]
	depth_table = [0] * N
	depth_table[u] = [0, depth_from_v[u], u]
	
	while queue:
		cur, pre, depth, min_depth_from_v, min_depth_point = queue.pop()
		depth += 1
		for n in e_list[cur]:
			if n != pre:
				depth2 = depth_from_v[n]
				if min_depth_from_v > depth2:
					depth3 = depth2
					new_point = n
				else:
					depth3 = min_depth_from_v
					new_point = min_depth_point
				queue.append([n, cur, depth, depth3, min_depth_point])
				depth_table[n] = (depth, depth3, min_depth_point)
	return depth_table

depth_from_v = calc_depth_table(v)
depth_from_u = calc_depth_table2(depth_from_v, u)

#print(depth_from_v)
#print(depth_from_u)

max_count = 0
for i in range(N):
	a_dist = depth_from_v[i]
	t_dist, t_hit_dist, hit_pos = depth_from_u[i]
	a_hit_dist = depth_from_v[hit_pos]
	
	if t_hit_dist < a_hit_dist:
#		if (a_hit_dist - t_hit_dist) % 2 == 1:
		if max_count < a_dist - 1:
			max_count = a_dist - 1
#			else:
#				

print(max_count)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
import sys
input = sys.stdin.readline

class LCA1():
    def __init__(self, l, start):
        self.n = len(l)
        self.dep=[0]*self.n
        self.par=[[-1]*self.n for i in range(18)]
        self.is_leaf = [0]*n

        def dfs(p,v,d):
            self.dep[v]=d
            self.par[0][v]=p
            f = True
            for w in l[v]:
                if w!=p:
                    dfs(v,w,d+1)
                    f = False
            if f:
                self.is_leaf[v] = 1
        dfs(-1,start,0)
        for i in range(17):
            for j in range(self.n):
                self.par[i+1][j]=self.par[i][self.par[i][j]]

    def lca(self,a,b):
        if self.dep[a]>self.dep[b]:
            a,b=b,a
        for i in range(18):
            if (self.dep[b]-self.dep[a]) & 1<<i:
                b=self.par[i][b]
        if a==b:
            return a
        for i in range(18)[::-1]:
            if self.par[i][a]!=self.par[i][b]:
                a=self.par[i][a]
                b=self.par[i][b]
        return self.par[0][a]

    def dist(self, a,b):
        return abs(self.dep[a]-self.dep[b])

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

    LCA = LCA1(G, v)
    ans = 0
    for i in range(n):
        if not LCA.is_leaf[i]:
            continue
        lca = LCA.lca(u, i)
        if lca == v:
            continue
        if LCA.dist(lca, u) >= LCA.dist(lca, v):
            continue
        turn = 0
        tmp = 0
        d = LCA.dist(u, lca) + LCA.dist(lca, i)
        if d != 0:
            tmp = 2*d
            aoki = d
        else:
            aoki = 0
        tak = LCA.dep[i]
        m = tak-aoki
        if m%2==1:
            tmp += 2*m -1
        else:
            tmp += 2*(m-1)
        ans = max(ans, tmp)
    print(ans//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]:
                    w[i]=inf
                else:
                    w[i]=w[c]+1
                    ans=max(ans,v[i])
    return ans


bfs(a)
ans=t_bfs(t)

print(max(0,ans-1))

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)]
data=[[] for i in range(n+1)]
for a,b in ab:
    data[a].append(b)
    data[b].append(a)
flag=[-1]*(n+1)
que=[u]
flag[u]=0
cnt=1
while que:
    h=[]
    for x in que:
        for y in data[x]:
            if flag[y]==-1:
                flag[y]=cnt
                h.append(y)
    cnt+=1
    que=h
flag_2=[-1]*(n+1)
que=[v]
flag_2[v]=0
cnt=1
start=0
ans=0
if flag[v]<=2:
    start=v
else:
    while que:
        h=[]
        for x in que:
            for y in data[x]:
                if flag_2[y]==-1:
                    flag_2[y]=cnt
                    h.append(y)
                    if flag[y]-flag_2[y]<=2:
                        ans=flag_2[y]
                        start=y
                        break
            else:
                continue
            break
        else:
            cnt+=1
            que=h
            continue
        break
que=[start]
while que:
    ans+=1
    h=[]
    for x in que:
        for y in data[x]:
            if flag_2[y]==-1:
                flag_2[y]=ans
                h.append(y)
    que=h
print(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,[]]])
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
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
from collections import defaultdict as dd
import heapq
input = sys.stdin.readline
N, u, v = map(int, input().split())
e = dd(list)
for _ in range(N - 1):
  a, b = map(int, input().split())
  e[a].append((b, 1))
  e[b].append((a, 1))
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 6)
      v0 = v // (10 ** 6)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 6) + p[0])
    return d
d = dijkstra(N, e)
p = d.path(v, 0)
pp = d.path(u, 0)
#print(p)
#print(pp)
res = 0
for i in range(1, N + 1):
  x = p[i] == pp[i]
  if p[i] >= pp[i]: res = max(pp[i] - x, res)
print(res)

Submission status: Wrong Answer

Solution code:

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())


N,T,A = inpl()
T -= 1
A -= 1
lines = defaultdict(set)
for _ in range(N-1):
    a,b = inpl()
    lines[a-1].add(b-1)
    lines[b-1].add(a-1)

def dfs(s,b,d):
    global depthes
    depthes[s] = d
    for t in lines[s]:
        if t !=b:
            dfs(t,s,d+1)
    return

depthes = [-1]*N
dfs(A,-1,0)

aoki_nodes = [set() for _ in range(N)]
for i,d in enumerate(depthes):
    aoki_nodes[d].add(i)


turn = 0
nexts = set([T])
while True:
    takahashi = nexts.copy()
    nexts = set()
    for s in takahashi:
        for t in lines[s]:
            if t not in aoki_nodes[turn]:
                nexts.add(t)

    if len(nexts) == 0:
        print(turn)
        break
    elif len(aoki_nodes[turn+1] - nexts) == 0:
        print(turn+1)
        break

    turn += 1

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): #root: 根, v: 頂点数, Edges: 隣接行列
        self.v=v
        self.Edges=Edges
        #self.maxLog=int(((-log2(V))//1)*(-1))
        self.maxLog=18
        self.Parent=[[-1]*v for _ in range(self.maxLog+1)] #各頂点の親 parent[i][j]: jの2**i個上の親
        self.Depth=[0]*v #各頂点の深さ
        self.__bfs(root) #parent[0]とdepthを構成
        for i in range(self.maxLog): #parent[1:]の初期化
            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): #a,bのlcaを求める
        if self.Depth[a]>self.Depth[b]: #深い方をbとする
            a,b=b,a
        for i in range(self.maxLog): #a,bを同じ深さまで持ってくる
            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
        ans=max(ans,d_u+(d_l-d_u)//2)
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,U,V = map(int,input().split())
U,V = U-1, V-1

adj = [list() for _ in range(N)]

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



dist_u = [None]*N
dist_u[U] = 0
stack = [U]

while stack:
    x = stack.pop()
    d = dist_u[x]+1
    for y in adj[x]:
        if dist_u[y] is None:
            dist_u[y] = d
            stack.append(y)


dist_v = [None]*N
dist_v[V] = 0
stack = [V]

while stack:
    x = stack.pop()
    d = dist_v[x]+1
    for y in adj[x]:
        if dist_v[y] is None:
            dist_v[y] = d
            stack.append(y)

m,n = max((a,b) for a,b in zip(dist_u, dist_v) if a < b)
print(n-(m-n)%2)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]

def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a=inp()
        a-=1
        g[i].append(a)
        g[a].append(i)
    return n,g


def dijkstra_back(s,t,n,w,cost):
    #sからtへの最短経路の経路復元
    prev = [s] * n #最短経路の直前の頂点
    d = [10**6] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
        
        for i in range(n):
            if d[i] > d[v] + cost[v][i]: 
                d[i] = d[v] + cost[v][i]
                prev[i] = v
        
    path = [t]
    while prev[t] != s:
        path.append(prev[t])
        prev[t] = prev[prev[t]]
    path.append(s)
    path = path[::-1]
    return path

def dijkstra(s,n,g): # 単一始点最短路問題　sからの最短距離 頂点数n
    s -= 1
    que = []
    d = [10**10 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while len(que)>0:
        p =  heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d

def main():
    n,u,v = inpm()
    g = [[] for _ in range(n)]
    cost = [[10**10 for i in range(n)] for i in range(n)] 
    ab = []
    for _ in range(n-1):
        a,b = inpm()
        a -= 1
        b -= 1
        ab.append((a,b))
        g[b].append((a,1))
        g[a].append((b,1))
        cost[a][b]=1
        cost[b][a]=1
    path = dijkstra_back(u-1,v-1,n,n-1,cost)
    dis = len(path)
    ans = int(dis//2)-1
    g = [[] for _ in range(n)]
    for i in range(n-1):
        if ab[i] == (path[ans],path[ans+1]) or ab[i] == (path[ans+1],path[ans]):
            continue
        g[ab[i][0]].append((ab[i][1],1))
        g[ab[i][1]].append((ab[i][0],1))
    d = dijkstra(path[ans]+1,n,g)
    maxd = 0
    for i in range(n):
        if d[i]==10**10:
            continue
        else:
            if maxd<d[i]:
                maxd=d[i]
    x = ans+maxd
    if x==0 and dis==3:
        x+=1
    print(x)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n, u, v, *L = map(int, open(0).read().split())

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


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()
	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
		m = max(m, dist_f_v[cur])
print(m-1)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,u,v=map(int,input().split())
Edge=[[] for i 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)


from collections import deque

def BFS(s):
  dist=[-1]*n
  que=deque([s-1])
  dist[s-1]=0
  while que:
    v=que.popleft()
    d=dist[v]
    for w in Edge[v]:
      if dist[w]>-1:
        continue
      dist[w]=d+1
      que.append(w)
  return dist

U_d,V_d=BFS(u),BFS(v)
ans=0
for i in range(n):
  if U_d[i]<V_d[i]:
    ans=max(ans,U_d[i])
print(ans)

Submission status: Wrong Answer

Solution code:
N,U,V = map(int,input().split())
U,V = U-1, V-1

adj = [list() for _ in range(N)]

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



dist_u = [None]*N
dist_u[U] = 0
stack = [U]

while stack:
    x = stack.pop()
    d = dist_u[x]+1
    for y in adj[x]:
        if dist_u[y] is None:
            dist_u[y] = d
            stack.append(y)


dist_v = [None]*N
dist_v[V] = 0
stack = [V]

while stack:
    x = stack.pop()
    d = dist_v[x]+1
    for y in adj[x]:
        if dist_v[y] is None:
            dist_v[y] = d
            stack.append(y)

m,n = max((a,b) for a,b in zip(dist_u, dist_v) if a < b)
print(n-1)

Submission status: Wrong Answer

Solution code:
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=[]
for i in range(n):
  if x[i]<y[i]:
    if abs(x[i]-y[i])%2==0:
      ans.append((x[i]+y[i]+1)//2)
    else:
      ans.append((x[i]+y[i])//2)
print(max(ans))

Submission status: Wrong Answer

Solution code:
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=[]
for i in range(n):
  if x[i]<y[i]:
    ans.append((x[i]+y[i])//2)
print(max(ans))

Submission status: Wrong Answer

Solution code:
n,u,v,*L=map(int,open(0).read().split())
vis=[-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)
vis[v-1]=0

def f(s):
	q=[s]
	vis[s]=1
	f=0
	while q:
		cur=q.pop(0)
		if cur==u-1:
			f=1
		for nxt in con[cur]:
			if vis[nxt]<0:
				vis[nxt]=vis[cur]+1
				q.append(nxt)
	if f:
		return vis[cur]
	else:
		return False

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

for s in con[v-1]:
	r=f(s)
	if r:
		print(r-1)
		exit()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,u,v=map(int,input().split())
grid=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    grid[a].append(b)
    grid[b].append(a)
d=deque()
d.append(u-1)
dist_u=[-1 for _ in range(n)]
dist_u[u-1]=0
while d:
    s=d.popleft()
    for i in grid[s]:
        if dist_u[i]!=-1:
            continue
        dist_u[i]=dist_u[s]+1
        d.append(i)

d.append(v-1)
dist_v=[-1 for _ in range(n)]
dist_v[v-1]=0
while d:
    s=d.popleft()
    for i in grid[s]:
        if dist_v[i]!=-1:
            continue
        dist_v[i]=dist_v[s]+1
        d.append(i)
        

while True:
    if dist_u[dist_v.index(max(dist_v))]<dist_v[dist_v.index(max(dist_v))]:
        print(max(dist_v)-1)
        break
    else:
        dist_u.pop(dist_v.index(max(dist_v)))
        dist_v.pop(dist_v.index(max(dist_v)))

Submission status: Time Limit Exceeded

Solution code:
from collections import*
n,u,v=map(int,input().split())
e=[[]for _ in range(n+1)]
INF=10**18
d=[INF]*(n+1)
for _ in range(n-1):
  a,b=map(int,input().split())
  e[a]+=[b]
  e[b]+=[a]
q=deque([(v,0)])
while q:
  now,c=q.popleft()
  d[now]=c
  for to in e[now]:
    if d[to]!=INF:continue
    q.append((to,c+1))
q=[(u,0)]
ans=0
vis=[1]*(n+1)
while q:
  now,c=q.pop()
  vis[now]=1
  f=1
  for to in e[now]:
    if vis[to]:
      f=0
      if d[to]>c+1:q+=[(to,c+1)]
      if d[to]==c+1:ans=max(c+1,ans)
      else:ans=max(c,ans)
  if f:ans=max(d[to],ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import*
n,u,v=map(int,input().split())
e=[[]for _ in range(n+1)]
INF=10**18
d=[INF]*(n+1)
for _ in range(n-1):
  a,b=map(int,input().split())
  e[a]+=[b]
  e[b]+=[a]
q=deque([v])
d[v]=0
while q:
  now=q.popleft()
  for to in e[now]:
    if d[to]!=INF:continue
    d[to]=d[now]+1
    q.append(to)
q=[(u,0)]
ans=0
vis=[1]*(n+1)
while q:
  now,c=q.pop()
  vis[now]=1
  f=1
  for to in e[now]:
    if vis[to]:
      f=0
      if d[to]>c+1:q+=[(to,c+1)]
      if d[to]==c+1:ans=max(c+1,ans)
      else:ans=max(c,ans)
  if f:ans=max(d[to],ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import*
n,u,v=map(int,input().split())
e=[[]for _ in range(n+1)]
INF=10**18
d=[INF]*(n+1)
for _ in range(n-1):
  a,b=map(int,input().split())
  e[a]+=[b]
  e[b]+=[a]
q=deque([v])
d[v]=0
while q:
  now=q.popleft()
  for to in e[now]:
    if d[to]!=INF:continue
    d[to]=d[now]+1
    q.append(to)
q=[(u,0)]
ans=0
while q:
  now,c=q.pop()
  for to in e[now]:
    if d[to]>c+1:q+=[(to,c+1)]
    elif d[to]==c+1:ans=max(c+1,ans)
    else:ans=max(c,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1<<30)
def dfs(x,dis):
    for y in Tree[x]:
        if parent[x] != y:
            parent[y] = x
            dis[y] = dis[x]+1
            dfs(y,dis)

N,u,v = map(int,input().split())
Tree = [[] for _ in range(N+1)]
for i in range(N-1):
    A,B = map(int,input().split())
    Tree[A].append(B)
    Tree[B].append(A)
disT = [-1]*(N+1)
disA = [-1]*(N+1)
disT[u] = 0
disA[v] = 0
parent = [-1]*(N+1)
dfs(u,disT)
parent = [-1]*(N+1)
dfs(v,disA)
ans = 0
for i in range(1,N+1):
    if disT[i] <= disA[i]:
        ans = max(ans,disA[i]-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

input = sys.stdin.readline

N, u, v = map(int, input().split())
u -= 1
v -= 1
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)

u_dist = [-1 for _ in range(N)]
v_dist = [-1 for _ in range(N)]

u_q = set([u])
v_q = set([v])

ans = -1
count = 0
visited = set()
while u_q and v_q:
    u_next = set()
    v_next = set()
    # print("count", count)
    for u_p in u_q:
        if u_p in u_next:
            continue
        for np in edges[u_p]:
            if np in v_q:
                # print("touched!")
                ans = count
            else:
                u_next.add(np)
    if not u_next:
        break
    count += 1
    for v_p in v_q:
        if v_p in visited:
            continue
        visited.add(v_p)
        for np in edges[v_p]:
            v_next.add(np)
            if np in u_next:
                # print("touched!!!")
                ans = count
                u_next.remove(np)

            
    u_q = u_next
    v_q = v_next
    # print(u_q)
    # print(v_q)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

input = sys.stdin.readline

N, u, v = map(int, input().split())
u -= 1
v -= 1
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)

u_dist = [-1 for _ in range(N)]
v_dist = [-1 for _ in range(N)]

u_q = set([u])
v_q = set([v])

ans = -1
count = 0
visited = set()
while u_q and v_q:
    u_next = set()
    v_next = set()
    # print("count", count)
    for u_p in u_q:
        for np in edges[u_p]:
            if np in v_q:
                # print("touched!")
                ans = count
            else:
                u_next.add(np)
    if not u_next:
        break
    count += 1
    for v_p in v_q:
        if v_p in visited:
            continue
        visited.add(v_p)
        for np in edges[v_p]:
            v_next.add(np)
            if np in u_next:
                # print("touched!!!")
                ans = count
                u_next.remove(np)

            
    u_q = u_next
    v_q = v_next
    # print(u_q)
    # print(v_q)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

input = sys.stdin.readline

N, u, v = map(int, input().split())
u -= 1
v -= 1
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)

u_dist = [-1 for _ in range(N)]
v_dist = [-1 for _ in range(N)]

u_q = set([u])
v_q = set([v])

ans = -1
count = 0
visited = set()
while u_q and v_q:
    u_next = set()
    v_next = set()
    # print("count", count)
    for u_p in u_q:
        for np in edges[u_p]:
            if np in v_q:
                # print("touched!")
                ans = count
            else:
                u_next.add(np)
    if not u_next:
        break
    count += 1
    for v_p in v_q:
        for np in edges[v_p]:
            if np in visited:
                continue
            v_next.add(np)
            visited.add(np)
            if np in u_next:
                # print("touched!!!")
                ans = count
                u_next.remove(np)

            
    u_q = u_next
    v_q = v_next
    # print(u_q)
    # print(v_q)

print(ans)