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: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heappop
from math import isinf


class Edge(object):

    def __init__(self, src, dst, cost):
        self.src = src
        self.dst = dst
        self.cost = cost


class Dijkstra(object):

    def __init__(self, v_len, edges, start, directed=False):
        """
        ダイクストラ法で最短経路を求める。

        :param v_len: グラフのノード数 通常は|V|、1-indexedなグラフなら |V| + 1
        :param edges: グラフの構造
        :param start: 始点 単一視点最短経路問題として解くので必要
        :param directed: 有向グラフの場合True 隣接行列を対称行列にするかが変わる
        """

        # 隣接行列 (adjacency matrix)
        # adj[i][j] でi番目の頂点からj番目の頂点へのコストを示す パスがなければINF
        self._adj = [[float('inf') for _ in range(v_len)] for _ in range(v_len)]
        for e in edges:
            self._adj[e.src][e.dst] = e.cost
            if not directed:
                self._adj[e.dst][e.src] = e.cost
        self._dist = [float('inf') for i in range(v_len)]  # 始点から各頂点までの最短距離
        self._prev = [float('inf') for i in range(v_len)]  # 最短経路における，その頂点の前の頂点のIDを格納する

        self._solve(start)

    def _solve(self, start):
        # 「最短距離が確定した頂点」に隣接する点からBFSするにあたり、それをどう探すかが問題になる
        # 安直に実装すればここで O(|V|) かかってしまうが、優先度キューを使えば O(log|V|) になる
        self._dist[start] = 0
        q = list()
        heappush(q, (0, start))  # キューの要素は (始点から頂点v_iへの仮の距離, v_iのID)

        while len(q) != 0:
            c, src = heappop(q)
            if self._dist[src] < c:
                continue

            # 隣接行列から隣接するノードを全て調べる = BFS
            for dst in range(len(self._adj)):
                cost = self._adj[src][dst]
                if isinf(cost):
                    continue
                if self._dist[src] + cost < self._dist[dst]:
                    self._dist[dst] = self._dist[src] + cost
                    heappush(q, (self._dist[dst], dst))
                    self._prev[dst] = src

    def distance(self, goal):
        return self._dist[goal]

    def path(self, goal):
        path = list()
        path.append(goal)
        cursor = goal

        while not isinf(self._prev[cursor]):
            path.append(self._prev[cursor])
            cursor = self._prev[cursor]

        return list(reversed(path))


def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7


N, u, v = MI()
edges = list()
for _ in range(N - 1):
    a, b = MI()
    edges.append(Edge(a - 1, b - 1, 1))

t = Dijkstra(N, edges, u - 1)
a = Dijkstra(N, edges, v - 1)
initial_dist = t.distance(v - 1)

ans = 0
for i in range(N):
    if a.distance(i) > t.distance(i):
        ans = max(ans, a.distance(i) - 1)
ans = max(ans, initial_dist - 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7

n,u,v=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n-1)]

dic=[[] for i in range(n+1)]
for i in range(n-1):
    a,b=ab[i]
    dic[a].append(b)
    dic[b].append(a)
itta=[0]*(n+1)
ta=deque([u])
ao=deque([v])
itta[v]=1
cnt=0
while 1:
    ittata=[0]*(n+1)
    for i in range(len(ta)):
        tmp=ta.popleft()
        if itta[tmp]==1:
            continue
        for i in dic[tmp]:
            if itta[i]==0 and ittata[i]==0:
                ittata[i]=1
                ta.append(i)
    if len(ta)==0:
        print(cnt)
        break
    cnt+=1
    for i in range(len(ao)):
        tmp=ao.popleft()
        for i in dic[tmp]:
            if itta[i]==0:
                itta[i]=1
                ao.append(i)
    # print(ta)
    # print(ao)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7

n,u,v=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n-1)]

dic=[[] for i in range(n+1)]
for i in range(n-1):
    a,b=ab[i]
    dic[a].append(b)
    dic[b].append(a)
itta=[0]*(n+1)
ta=deque([u])
ao=deque([v])
itta[v]=1
cnt=0
while 1:
    for i in range(len(ta)):
        tmp=ta.popleft()
        if itta[tmp]==1:
            continue
        for i in dic[tmp]:
            if itta[i]==0:
                ta.append(i)
    if len(ta)==0:
        print(cnt)
        break
    cnt+=1
    for i in range(len(ao)):
        tmp=ao.popleft()
        for i in dic[tmp]:
            if itta[i]==0:
                itta[i]=1
                ao.append(i)
    # print(ta)
    # print(ao)

Submission status: Time Limit Exceeded

Solution code:
N,u,v = map(int, input().split())
G=[[] for i in range(N)]
for i in range(N-1):
    s,t = map(int, input().split())
    G[s-1].append(t-1)
    G[t-1].append(s-1)

"""
for i in range(len(G[u])):
    k=G[u][i]
    D[k]=1
"""
def expro(u):
    D=[0]*N
    D[u]=0
    S=[]
    S.append(u)
    L=[]
    while(len(S)!=0):
        l=S[0]
        for i in range(len(G[l])):
            m=G[l][i]
            if(len(G[l])==1 and l!=u):
                L.append(l)
            if(D[m]==0 and m!=u):
                D[m]=D[l]+1
                S.append(m)
        S.remove(l)
    return L,D
L,D = expro(u-1)
M,E = expro(v-1)
k=0
ans=0
#print(G)
#print(D)
#print(L)
for i in M:
    if D[i]<E[i]:
        if k<E[i]:
            k=E[i]
            ans=E[i]-1
print(ans)

Submission status: Time Limit Exceeded

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

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

def dfs(v, dist, p=-1, d=0):
    dist[v] = d
    for nv in es[v]:
        if nv == p:
            continue
        dfs(nv, dist, v, d+1)

def calc_dist(x):
    dist = [-1] * n
    dfs(x, dist)
    return dist

dist_t = calc_dist(u)
dist_a = calc_dist(v)

mx = 0
for i in range(n):
    if dist_t[i] < dist_a[i]:
        mx = max(mx, dist_a[i])

ans = mx - 1
print(ans)

Submission status: Time Limit Exceeded

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


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

GRAPH = {i:[] for i in range(1, n + 1)}
for _ in range(n - 1):
    a, b = map(int, input().split())
    GRAPH[a].append(b)
    GRAPH[b].append(a)

def dfs(now, prev = 0):
    PARENT[now] = prev
    DEPTH[now] = DEPTH[prev] + 1
    if len(GRAPH[now]) == 1:
        LEAVES.append((DEPTH[now], now))
    
    for w in GRAPH[now]:
        if w == prev:
            continue
        next = w
        dfs(next, now)

PARENT = {}
DEPTH = {0:-1}
LEAVES = []
dfs(v)

PATH = []
now = u
while True:
    PATH.append(now)
    if now == v:
        break
    now = PARENT[now]

LEAVES.sort(reverse = True)
for leaf in LEAVES:
    now = leaf[1]
    while True:
        if now in PATH:
            break
        now = PARENT[now]
    lca = now
    
    du, dv = DEPTH[u] - DEPTH[lca], DEPTH[lca]
    if du < dv:
        print(leaf[0] - 1)
        exit()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,u,v=LI()

TR=[[] for i in range(N+1)]
for _ in range(N-1):
    i,j=LI()
    TR[i].append(j)
    TR[j].append(i)

DIST=[(-1,-1) for i in range(N+1)]
DIST[v] = (0, -1)
def dfs(root=v):
    maxdist = DIST[root][0]
    for vtx in TR[root]:
        if DIST[vtx][0] == -1:
            DIST[vtx] = (DIST[root][0] + 1, -1)
            maxdist = max(maxdist, dfs(vtx))
    DIST[root] = (DIST[root][0], maxdist)
    return maxdist

DIST2=[(-1,-1) for i in range(N+1)]
LST = 0
def dfs2(root=u):
    global LST
    maxdist = DIST2[root][0]
    for vtx in TR[root]:
        if DIST2[vtx][0] == -1 and DIST2[root][0] + 1 < DIST[vtx][0]:
            LST = max(LST, DIST[vtx][0])
            DIST2[vtx] = (DIST2[root][0] + 1, -1)
            maxdist = max(maxdist, dfs2(vtx))
    DIST2[root] = (DIST2[root][0], maxdist)
    return maxdist

dfs()
dfs2()
# print(DIST)
# print(DIST2)

print(max(0, LST-1))

Submission status: Time Limit Exceeded

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

t, a = 0, 0
tpos, apos = {u:0}, {v:0}

amin = float("-inf")
while len(tpos) > 0:
    t_new = dict() # T moves                                                                                                                            
    for k, v in tpos.items():
        for dst in V[k]:
            t_new[dst] = max(t_new.get(dst, 0), v + 1)
            if dst in apos:
                amin = max(amin, apos[dst])
                del t_new[dst]

    a_new = dict() # A moves                                                                                                                            
    for k, v in apos.items():
        for dst in V[k]:
            a_new[dst] = max(a_new.get(dst, 0), v + 1)
            if dst in t_new:
                amin = max(amin, a_new[dst])
                del t_new[dst]

    tpos = t_new
    apos = a_new

print(amin)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

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

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

g=csr_matrix((w,(row,col)),shape=(n,n))

d_u=dijkstra(g,directed=False,indices=u-1)
d_v=dijkstra(g,directed=False,indices=v-1)

l=0
for t_u,t_v in zip(d_u,d_v):
 if t_u<t_v:
  l=max(l,t_v)
print(int(l)-1)

Submission status: Time Limit Exceeded

Solution code:
import sys,heapq
input = sys.stdin.readline
def main():
    n,u,v = map(int,input().split())
    u,v = u-1,v-1

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

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

    #cost:vからの距離
    cost = [0]*n
    new = [v]
    c = 1
    while len(new):
        tank = []
        for e in new:
            for go in edge[e]:
                if go != v and cost[go] == 0:
                    cost[go] = c
                    tank.append(go)
        c += 1
        new = tank

    res = 1
    new = set([u])
    while len(new):
        tank = set()
        for e in new:
            for go in edge[e]:
                if cost[go] > res:
                    tank.add(go)
        res += 1
        new = tank
    
    if cost[u]% 2 == 1:
        print(res-2)
    else:
        print(res-1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys,heapq
input = sys.stdin.readline
def main():
    n,u,v = map(int,input().split())
    u,v = u-1,v-1

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

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

    #cost:vからの距離
    cost = [0]*n
    new = [v]
    c = 1
    while len(new):
        tank = []
        for e in new:
            for go in edge[e]:
                if go != v and cost[go] == 0:
                    cost[go] = c
                    tank.append(go)
        c += 1
        new = tank

    res = 1
    new = [u]
    while len(new):
        tank = []
        for e in new:
            for go in edge[e]:
                if cost[go] > res:
                    tank.append(go)
        res += 1
        new = tank
    
    if cost[u]% 2 == 1:
        print(res-2)
    else:
        print(res-1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

N,u,v = map(int,input().split())
u -= 1
v -= 1
E = [set() for _ in range(N)]
for _ in range(N-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  E[a].add(b)
  E[b].add(a)

DU = [-1 for _ in range(N)]  
DV = [-1 for _ in range(N)]
def dfs(p,c,D):
  D[p] = c
  for q in E[p]:
    if D[q] == -1:
      dfs(q,c+1,D)
dfs(u,0,DU)
dfs(v,0,DV)
#print(DU)
#print(DV)
mx = 0
for du,dv in zip(DU,DV):
  if du < dv:
    mx = max(dv,mx)
print(mx-1)

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
N, u, v = map(int, input().split())
u, v = u-1, v-1
AB = [list(map(int, input().split())) for a in range(N-1)]

G = [[] for a in range(N)]

for ab in AB:
  G[ab[0]-1].append(ab[1]-1)
  G[ab[1]-1].append(ab[0]-1)
#print(AB)
#print(G)

def bfs(current, goal):
#  print('bfs start')
#  print(current, goal)
  q = deque([current])
  costs = [0 for a in range(N)]
  done = [0 for a in range(N)]
  done[current] = 1
  while q:
    start = q.popleft()
#    print(start)
    if start == goal:
      return costs[goal]
    for i in G[start]:
      if done[i] == 0:
        q.append(i)
        costs[i] = costs[start] + 1
        done[i] = 1

distances = [0]
for i in range(N):
#  print(i)
  aoki = bfs(i, v)
  takahashi = bfs(i, u)
  if aoki > takahashi:
    distances.append(aoki)

print(max(distances)-1)

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
N, u, v = map(int, input().split())
u, v = u-1, v-1
AB = [list(map(int, input().split())) for a in range(N-1)]

G = [[0 for b in range(N)] for a in range(N)]
D = [[0 for b in range(N)] for a in range(N)]


for ab in AB:
  G[ab[0]-1][ab[1]-1] = 1
  G[ab[1]-1][ab[0]-1] = 1

def bfs(current, goal):
  if D[current][goal] > 0:
    return D[current][goal]
  q = deque([[current, 0]])
  memo = [0 for a in range(N)]
  while q:
    startcost = q.popleft()
    start = startcost[0]
    cost = startcost[1]
    if start == goal:
      D[current][goal] = cost
      D[goal][current] = cost
      return cost
    for i in range(N):
      if G[start][i] == 1 and memo[i] == 0:
        q.append([i, cost + 1])
        memo[i] = 1
  

distances = [0]
for i in range(N):
  aoki = bfs(i, v)
  takahashi = bfs(i, u)
  if aoki > takahashi:
    distances.append(aoki)

print(max(distances)-1)

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
N, u, v = map(int, input().split())
u, v = u-1, v-1
AB = [list(map(int, input().split())) for a in range(N-1)]

G = [[0 for b in range(N)] for a in range(N)]
D = [[0 for b in range(N)] for a in range(N)]


for ab in AB:
  G[ab[0]-1][ab[1]-1] = 1
  G[ab[1]-1][ab[0]-1] = 1

def bfs(current, goal):
  if D[current][goal] > 0:
    return D[current][goal]
  q = deque([[current, 0]])
  memo = [0 for a in range(N)]
  while q:
    startcost = q.popleft()
    start = startcost[0]
    cost = startcost[1]
    if start == goal:
      D[current][goal] = cost
      D[goal][current] = cost
      return cost
    for i in range(N):
      if G[start][i] == 1 and memo[i] == 0:
        q.append([i, cost + 1])
        memo[i] = 1
  

distances = [0]
for i in range(N):
  count = 0
  for j in range(N):
    if G[i][j] == 1:
      count += 1
  if count == 1:
    aoki = bfs(i, v)
    takahashi = bfs(i, u)
    if aoki > takahashi:
      distances.append(aoki)

print(max(distances)-1)

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
N, u, v = map(int, input().split())
u, v = u-1, v-1
AB = [list(map(int, input().split())) for a in range(N-1)]

G = [[0 for b in range(N)] for a in range(N)]
#D = [[0 for b in range(N)] for a in range(N)]


for ab in AB:
  G[ab[0]-1][ab[1]-1] = 1
  G[ab[1]-1][ab[0]-1] = 1

def bfs(current, goal):
  q = deque([[current, 0]])
  memo = [0 for a in range(N)]
  while q:
    startcost = q.popleft()
    start = startcost[0]
    cost = startcost[1]
    if start == goal:
      return cost
    for i in range(N):
      if G[start][i] == 1 and memo[i] == 0:
        q.append([i, cost + 1])
        memo[i] = 1
  

distances = [0]
for i in range(N):
  count = 0
  for j in range(N):
    if G[i][j] == 1:
      count += 1
  if count == 1:
    aoki = bfs(i, v)
    takahashi = bfs(i, u)
    if aoki > takahashi:
      distances.append(aoki)

print(max(distances)-1)

Submission status: Time Limit Exceeded

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

G = [[0 for b in range(N)] for a in range(N)]
D = [[0 for b in range(N)] for a in range(N)]

for ab in AB:
  G[ab[0]-1][ab[1]-1] = 1
  G[ab[1]-1][ab[0]-1] = 1

def dfs(current, goal, distance, prev):
  if current == goal:
    return distance
  if 0 < D[current][goal] :
    return D[current][goal]
  if 0 < D[goal][current] :
    return D[goal][current]
  dists = [0]
  for i in range(N):
    if G[current][i] == 1 and i != prev and i != current:
      dists.append(dfs(i, goal, distance + 1, current))
  D[goal][current] = max(dists)
  D[current][goal] = D[goal][current]
  return D[current][goal]

distances = [0]
for i in range(N):
  count = 0
  for j in range(N):
    if G[i][j] == 1:
      count += 1
  if count == 1:
    aoki = dfs(i, v, 0, -1)
    takahashi = dfs(i, u, 0, -1)
    if aoki > takahashi:
      distances.append(aoki)

print(max(distances)-1)

Submission status: Time Limit Exceeded

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

def bfs(node):
	sta = [node]
	dis = [-1] * (N + 1)
	dis[node] = 0
	while sta:
		no = sta.pop(0)
		tempD = dis[no] + 1
		for tempN in tree[no]:
			if dis[tempN] < 0:
				dis[tempN] = tempD
				sta.append(tempN)
	else:
		return dis

disU = bfs(u)
disV = bfs(v)
ans = 0

for u_, v_ in zip(disU[1:], disV[1:]):
	if u_ < v_:
			ans = max(ans, v_)
else:
	print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra


def calc(d):
    if d == 1 or d == 0:
        return 0
    else:
        return int(d - 1)


delta = []
n, u, v = map(int, input().split())
G = [[float("inf")] * n for i in range(n)]
Gn = np.array(G)
for i in range(n - 1):
    a, b = map(int, input().split())
    a = a - 1
    b = b - 1
    Gn[a][b] = 1
    Gn[b][a] = 1
    Gn[i][i] = 0
minimum_u = dijkstra(Gn, indices=u - 1)
minimum_v = dijkstra(Gn, indices=v - 1)
for i in range(n):
    if minimum_v[i] - minimum_u[i] > 0 and i != u - 1 and i != v - 1:
        delta.append([i, minimum_v[i]])
if delta != []:
    delta_sorted = sorted(delta, key=lambda x: x[1])
    p = delta_sorted[-1][0]
    d = int(minimum_v[p])
    print(calc(d))
else:
    print(calc(minimum_u[v - 1]))

Submission status: Time Limit Exceeded

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

from collections import deque
infinity=10**6
#uを中心とする深さ優先探索(の改良版)
def bfs(u,d):
    Q=deque([u])
    d[u]=0

    while(Q):
        x = Q.pop()
        for y in G[x]:
            if d[y] == infinity:
                d[y] = d[x]+1
                Q.appendleft(y)
    dlist=[set() for i in range(N)]
    #dlist=[set()]*(N-1)
    for i in range(N):
        dlist[d[i]].add(i) 

    return dlist


N,u,v = map(int,input().split())
u -= 1
v -= 1
#グラフの作成
G=[[] for i in range(N)]
# G=[[]]*N この初期化方法でappendすると全リストに要素が追加されてしまう　
# print(id(G[0]) == id(G[1]))がTrueになってしまうことからもわかる(同じオブジェクトを指してしまっている)
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

du=[infinity]*N 
dv=[infinity]*N
 
dlist_u = bfs(u,du) #逃げる側
dlist_v = bfs(v,dv) #鬼側

set_u_odd=set()
set_u_even={u} #set_uは常にi+1番目を更新したいため
set_v_odd=set()
set_v_even=set()


for i in range(N-1):
    if i%2==0:
        set_u_odd |= set(dlist_u[i+1])
        set_v_even |= set(dlist_v[i])
         
        if len(set_u_even-set_v_even)==0 or len(set_u_odd-set_v_even)==0: #前者は鬼が動いて確保, 後者は逃げる側が自爆
            print(i)
            break
    else:
        set_u_even |= set(dlist_u[i+1])
        set_v_odd |= set(dlist_v[i])
        if len(set_u_odd-set_v_odd)==0 or len(set_u_even-set_v_odd)==0:
            print(i)
            break

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
infinity=10**6
#uを中心とする深さ優先探索(の改良版)
def bfs(u,d):
    Q=deque([u])
    d[u]=0

    while(Q):
        x = Q.pop()
        for y in G[x]:
            if d[y] == infinity:
                d[y] = d[x]+1
                Q.appendleft(y)
    dlist=[set() for i in range(N)]
    #dlist=[set()]*(N-1)
    for i in range(N):
        dlist[d[i]].add(i) 

    return dlist


N,u,v = map(int,input().split())
u -= 1
v -= 1
#グラフの作成
G=[[] for i in range(N)]
# G=[[]]*N この初期化方法でappendすると全リストに要素が追加されてしまう　
# print(id(G[0]) == id(G[1]))がTrueになってしまうことからもわかる(同じオブジェクトを指してしまっている)
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

du=[infinity]*N 
dv=[infinity]*N
 
dlist_u = bfs(u,du) #逃げる側
dlist_v = bfs(v,dv) #鬼側

set_u_odd=set()
set_u_even={u} #set_uは常にi+1番目を更新したいため
set_v_odd=set()
set_v_even=set()


for i in range(N-1):
    if i%2==0:
        set_u_odd |= set(dlist_u[i+1])
        set_v_even |= set(dlist_v[i])
         
        if len(set_u_even-set_v_even)==0 or len(set_u_odd-set_v_even)==0: #前者は鬼が動いて確保, 後者は逃げる側が自爆
            print(i)
            break
    else:
        set_u_even |= set(dlist_u[i+1])
        set_v_odd |= set(dlist_v[i])
        if len(set_u_odd-set_v_odd)==0 or len(set_u_even-set_v_odd)==0:
            print(i)
            break

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

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

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

g=csr_matrix((w,(ro,co)),shape=(n,n))
d_u=dijkstra(g,directed=False,indices=u-1)
d_v=dijkstra(g,directed=False,indices=v-1)

l=0
for t_u,t_v in zip(d_u,d_v):
 if t_u<t_v:
  l=max(l,t_v)
print(int(l)-1)

Submission status: Time Limit Exceeded

Solution code:
import sys, numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson  
from collections import defaultdict
from itertools import product, permutations, combinations

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

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

    adjm = [[float('inf')] * N for _ in range(N)]
    for ab in AB:
        a, b = ab[0]-1, ab[1]-1
        adjm[a][b] = 1
        adjm[b][a] = 1
        
    adjm = csr_matrix(adjm)
    dv = dijkstra(adjm, indices=v-1)
    du = dijkstra(adjm, indices=u-1)
    dOK = [i for i, j in zip(dv, du) if i>j]

    print(int(max(dOK)-1))

solve()

Submission status: Time Limit Exceeded

Solution code:
import sys, numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson  
from collections import defaultdict
from itertools import product, permutations, combinations

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

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

    adjm = [[float('inf')] * N for _ in range(N)]
    for ab in AB:
        a, b = ab[0]-1, ab[1]-1
        adjm[a][b] = 1
        adjm[b][a] = 1
        
    dv = dijkstra(adjm, indices=v-1)
    du = dijkstra(adjm, indices=u-1)
    dOK = [i for i, j in zip(dv, du) if i>j]

    print(int(max(dOK)-1))

solve()

Submission status: Time Limit Exceeded

Solution code:
import sys, numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson  
from collections import defaultdict
from itertools import product, permutations, combinations

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

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

adjm = [[float('inf')] * N for _ in range(N)]
for ab in AB:
    a, b = ab[0]-1, ab[1]-1
    adjm[a][b] = 1
    adjm[b][a] = 1
    
dv = dijkstra(adjm, indices=v-1)
du = dijkstra(adjm, indices=u-1)
dOK = [i for i, j in zip(dv, du) if i>j]

print(int(max(dOK)-1))

Submission status: Time Limit Exceeded

Solution code:
import sys, numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson  
from collections import defaultdict
from itertools import product, permutations, combinations

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

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

adjm = [[float('inf')] * N for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    adjm[a][b] = 1
    adjm[b][a] = 1
    
dv = dijkstra(adjm, indices=v-1)
du = dijkstra(adjm, indices=u-1)
dOK = [(i>j)*i for i, j in zip(dv, du)]

print(int(max(dOK)-1))

Submission status: Time Limit Exceeded

Solution code:
import sys, numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson  
from collections import defaultdict
from itertools import product, permutations, combinations

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

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

adjm = [[float('inf')] * N for _ in range(N)]
for ab in AB:
    a, b = ab[0]-1, ab[1]-1
    adjm[a][b] = 1
    adjm[b][a] = 1
    
dv = dijkstra(adjm, indices=v-1)
du = dijkstra(adjm, indices=u-1)
dOK = [(i>j)*i for i, j in zip(dv, du)]

print(int(max(dOK)-1))

Submission status: Time Limit Exceeded

Solution code:
def dfs(v, dist, d = 0, p = -1):
#     print(v, d)
    dist[v] = d
    for u in to[v]:
        if u == p:
            continue
        dfs(u, dist, d + 1, v)
def calcDist(s, dist):
    dfs(s, dist)        
n, u, v = map(int, input().split())
u -= 1
v -= 1
to = [[] for _ in range(10000005)]
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
distS = [0] * n
distT = [0] * n
calcDist(u, distS)
calcDist(v, distT)
mx = 0
for i in range(n):
    if distS[i] < distT[i]:
        mx = max(mx, distT[i])
ans = mx - 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:

# グラフ問題での分析が全然できなかった（初体験）
# 次回は頑張って解く！

N, u, v = map(int, input().split())
edges = [[] for i in range(N+1)]

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

def dfs(u):
  colors = ["white"] * (N+1)
  d = [None] * (N + 1)
  d[u] = 0
  stack = [u]

  while stack:
    u = stack.pop()
    colors[u] = "black"

    for e in edges[u]:
      if colors[e] != "black":
        d[e] = d[u] + 1
        stack.append(e)

  return d

u_dist = dfs(u)
v_dist = dfs(v)

ans = 0
for uu in u_dist:
  if uu == None: continue
  for vv in v_dist:
    if vv == None: continue
    if uu < vv:
      ans = max(ans, vv - 1)

print(ans)

Submission status: Time Limit Exceeded

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

def dijkstra(s,n,w,cost):
    d=[float("inf")]*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 j in range(n):
               d[j]=min(d[j],d[v]+cost[v][j])
    return d

n=N
w=N-1
cost = [[float("inf") for i in range(n)] for i in range(n)] 
for i in range(w):
    x,y = map(int,input().split())
    x-=1
    y-=1
    cost[x][y] = 1
    cost[y][x] = 1

ni=dijkstra(u-1,n,w,cost)
ou=dijkstra(v-1,n,w,cost)

c=0
d=ni[v-1]
for i in range(N):
    if ni[i]<ou[i]:
        c=max(c,ni[i])

if c==0:
    if d%2==0:
        c=1
else:
    if d%2==0:
        c-=1
print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,u,v = map(int,input().split())
edge = [[] for _ in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
q = deque()
step = [0 for _ in range(n+1)]
q.appendleft([v,0])
visied = set()
visied.add(v)
while len(q)>0:
    a,v = q.pop()
    for node in edge[a]:
        if node not in visied:
            step[node] = v+1
            q.appendleft([node,v+1])
            visied.add(node)
q = deque()
q.appendleft((u,0))
mx= 0
queue = set()
queue.add((u,0))
while len(q)>0:
    a, v = q.pop()
    p=0
    value =0
    for node in edge[a]:
        cur = v+1
        if cur<step[node]:
            add = (node,cur)
            if add not in queue:
                q.appendleft(add)
                queue.add(add)
                p=1
        else:
            value = max(value,step[node])
    if p ==0:
        mx = max(mx,value)
# print(step)
print(mx)