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 heapq;

n, u, v = [int(v) for v in input().split()]

vert = []

for i in range(n):
    vert.append([])

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

taka = u-1
aoki = v-1

q = []
heapq.heappush(q, (0, aoki))
aoki_dist = [-1] * n
closed = 0

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

heapq.heappush(q, (0, taka))
closed = (1 << taka)
max_dist = aoki_dist[taka]

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

print(max_dist - 1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    import sys

    input = sys.stdin.readline

    sys.setrecursionlimit(10 ** 7)

    def dfs(v, dist):
        for u in g[v]:
            if dist[u] == -1:
                dist[u] = dist[v] + 1
                dfs(u, dist)

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

    g = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        g[a].add(b)
        g[b].add(a)

    dist_from_a = [-1] * N
    dist_from_a[v] = 0
    dfs(v, dist_from_a)

    q = deque()
    q.append((u, -1, 0))

    while q:
        t, p, cost = q.popleft()
        for next_t in g[t]:
            if next_t == p:
                continue
            if dist_from_a[next_t] > cost + 1:
                q.append((next_t, t, cost + 1))
            elif dist_from_a[next_t] == cost:
                # 奇数距離で会う
                # cost+1//2とtとnext_tの間の辺を削除したグラフでtから最も遠い点までの距離の和
                x = t
                g[t].remove(next_t)
                g[next_t].remove(t)
                d_to_x = cost
                q = []
                break
            elif dist_from_a[next_t] == cost + 1:
                # 偶数距離で会う
                # cost+1//2とtとnext_tの間の辺を削除したグラフでtから最も遠い点までの距離の和
                x = t
                g[t].remove(next_t)
                g[next_t].remove(t)
                d_to_x = cost + 1
                q = []
                break

    dist_from_x = [-1] * N
    dist_from_x[x] = 0

    dfs(x, dist_from_x)
    d = max(dist_from_x)
    print(d + d_to_x)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,u,v = map(int,input().split())
l = [[] for _ in range(n+1)]
x = [0 for _ in range(n+1)]
y = [0 for _ in range(n+1)]
for i in range(n-1):
  ai,bi = map(int,input().split())
  l[ai].append(bi)
  l[bi].append(ai)
def t(p,a,m):
  global y
  for li in l[a]:
    if li != p:
      y[li] = m+1
      t(a,li,m+1)
  return
t(-1,v,0) 
def s(p,a,m):
  global x
  global mx
  ya = y[a]
  if ya <= m:
    return 
  if ya > m:
    if ya -1 > mx:
      mx = ya-1
  for li in l[a]:
    if li != p:
      x[li] = m+1
      s(a,li,m+1)
  return
mx = 0
s(-1,u,0)
print(mx)

Submission status: Time Limit Exceeded

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


def dfs4t(a, par):
    for child in edge[a]:
        if child == par:
            continue
        else:
            cost4t[child] = cost4t[a] + 1
            dfs4t(child, a)
    return

def dfs4a(a, par):
    for child in edge[a]:
        if child == par:
            continue
        else:
            cost4a[child] = cost4a[a] + 1
            dfs4a(child, a)
    return


N, u, v = map(int, input().split())
edge = [[] for _ in range(N)]
cost4t = [10**5 for i in range(N)]
cost4a = [10**5 for i in range(N)]

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

u -= 1
v -= 1
cost4t[u] = 0
cost4a[v] = 0
dfs4t(u, 10**5)
dfs4a(v, 10**5)

ans = 0
for t, a, in zip(cost4t, cost4a):
    if a  >= t:
        ans = max(ans, t + a - (t + 1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq;

n, u, v = [int(v) for v in input().split()]

vert = []

for i in range(n):
    vert.append([])

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

taka = u-1
aoki = v-1

q = []
heapq.heappush(q, (0, aoki))
aoki_dist = [-1] * n
closed = 0

while len(q) > 0:
    c0, i = heapq.heappop(q)
    aoki_dist[i] = c0
    closed |= (1 << i)

    c = c0 + 1
    for l in vert[i]:
        if closed & (1 << l) != 0:
            continue
        heapq.heappush(q, (c, l))

closed = 0
heapq.heappush(q, (0, taka))
max_dist = aoki_dist[taka] - 1

while len(q) > 0:
    c0, i = heapq.heappop(q)
    closed |= (1 << i)

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

print(max_dist)

Submission status: Time Limit Exceeded

Solution code:
import sys

def jisin(gen,mae,huka):
    hukasa[gen]=huka
    for c in tens[gen]:
        if(c!=mae):
            jisin(c,gen,huka+1)
    return

def kyokudai(gen,mae):
    dai=0
    if(len(tens[gen])==1 and mae!=-1):
        dai=hukasa[gen]
        #print(dai)
    else:
        for c in tens[gen]:
            if(c!=mae):
                dai=max(dai,kyokudai(c,gen))
    saisin[gen]=dai
    #print(gen,dai)
    return dai

def oikake(gen):
    miti.append(gen)
    if(hukasa[gen]==0):
        return
    for c in tens[gen]:
        if(hukasa[c]==hukasa[gen]-1):
            oikake(c)

sys.setrecursionlimit(10**6)
n,u,v=map(int,input().split())
u-=1
v-=1
tens=[[]for i in range(n)]
hukasa=[0]*n
saisin=[0]*n

for i in range(n-1):
    s,t=map(int,input().split())
    tens[s-1].append(t-1)
    tens[t-1].append(s-1)

#print(tens)

jisin(v,-1,0)
#print(hukasa)
kyokudai(v,-1)
#print(saisin)

miti=[]
oikake(u)
l=len(miti)-1
#print(miti)
#print(l)

ans=saisin[miti[l//2]]
print(ans-1)

Submission status: Time Limit Exceeded

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 = [set() for _ in range(N)]
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 aoki_nodes
    aoki_nodes[d].add(s)
    for t in lines[s]:
        if t !=b:
            dfs(t,s,d+1)
    return

stack = [(A,-1,0)]
aoki_nodes = [set() for _ in range(N)]

while len(stack)>0:
    s,b,d = stack.pop()
    aoki_nodes[d].add(s)
    for t in lines[s]:
        if t != b and d < N:
            stack.append((t,s,d+1))

turn = 0
takahashi = [set() for _ in range(N)]
takahashi[0].add(T)
while True:
    taka = takahashi[turn] - aoki_nodes[turn]
    next = set()
    for s in taka:
        takahashi[turn+1] |= lines[s]
    takahashi[turn+1] -= aoki_nodes[turn]

    if len(takahashi[turn+1]) == 0:
        print(turn)
        break
    turn += 1
    assert turn<N+5, "error"

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit

setrecursionlimit(1000000)

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

node = [[] for _ in range(N)]
for _ in range(N - 1):
  A, B = [int(s) - 1 for s in input().split()]
  node[A].append(B)
  node[B].append(A)

def tak(node, u, v, p):
  #print('tak %d %d %d' % (u, v, p))
  if p > N:
    return float('inf')
  if u == v:
    return p
  return max(aok(node, n, v, p) for n in node[u])

def aok(node, u, v, p):
  #print('aok %d %d %d' % (u, v, p))
  if u == v:
    return p
  return min(tak(node, u, n, p + 1) for n in node[v])

print(tak(node, u - 1, v - 1, 0))

Submission status: Time Limit Exceeded

Solution code:
N,u,v = list(map(int,input().split()))
A = [[float("inf") for i in range(N)] for i in range(N)]
for i in range(N-1):
    x,y = map(int,input().split())
    A[x-1][y-1] = 1
    A[y-1][x-1] = 1
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

Ta = dijkstra(u-1,N,N-1,A)
Ao = dijkstra(v-1,N,N-1,A)
output = 0
for i in range(N):
    if Ta[i]<Ao[i]:
        if Ao[i]-1>output:
            output = Ao[i]-1
print(output)

Submission status: Time Limit Exceeded

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):
    depth = [-1] * N

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

        for q in L[p]:
            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)

    res = 0
    stack = [(0, u)]
    while stack:
        d, p = stack.pop()
        if d == depth_A[p]:
            res = max(res, d)
            continue

        for q in L[p]:
            if depth_A[q] == d:
                res = max(res, d)
                continue
            
            stack.append((d + 1, q))
    
    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,u,v = list(map(int,input().split()))
A = [[float("inf") for i in range(N)] for i in range(N)]
for i in range(N-1):
    x,y = map(int,input().split())
    A[x-1][y-1] = 1
    A[y-1][x-1] = 1
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    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

Ta = dijkstra(u-1,N,N-1,A)
Ao = dijkstra(v-1,N,N-1,A)
firstD = Ta[v-1]

X = np.array((Ta,Ao))
Xsort = X[:, np.argsort(X[1])[::-1]]

for i in range(N):
    if Xsort[1,i]>Xsort[0,i]:
        print(Xsort[1,i]-1)
        break

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
sys.setrecursionlimit(100000)

N,U,V = map(int, input().split())
d = [set() for _ in range(N+1)]
dps = [0 for _ in range(N+1)]
dpss = [0 for _ in range(N+1)]
vs = set()
r = {}

def it(v, p, depth, ps):
    for u in d[v]:
        if u == p:
            continue
        dps[u] = depth
        if u == V:
            r["p"] = copy.deepcopy(ps)
            continue
        ps.add(u)
        it(u, v, depth+1,ps)
        ps.remove(u)
        vs.add(u)

def it2(v, p, depth):
    for u in d[v]:
        if u == p:
            continue
        if u not in vs:
            continue
        if dps[v] >= depth-1 and u not in r["p"]:
            continue
        dpss[u] = depth
        it2(u, v, depth+1)



for _ in range(N-1):
    a, b = [int(x) for x in input().split()]
    d[a].add(b)
    d[b].add(a)

vs.add(U)
it(U, -1, 1, set([U]))
it2(V, -1, 1)
print(max(dpss)-1)

Submission status: Time Limit Exceeded

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

n, u, v = [int(i) for i in sys.stdin.readline().split()]
u -= 1
v -= 1
graph = {i : [] for i in range(n)}
for i in range(n-1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

distance = 0
stack = [(u, 0)]
already = set()
parent = [i for i in range(n)]
while len(stack) > 0:
    cur, dis = stack.pop(-1)
    already.add(cur)
    for _next in graph[cur]:
        if _next in already:
            continue
        parent[_next] = cur
        if _next == v:
            distance = dis + 1
            break
        stack.append((_next, dis + 1))
cur = v
path = []
while cur != u:
    path.append(cur)
    cur = parent[cur]

path_dict = {j : i for i, j in enumerate(path)}
already = set()

def dfs(ind, cur_dis):
    res = 0
    already.add(ind)
    for _next in graph[ind]:
        parent[_next] = ind
        if _next in already:
            continue
        if _next in path:
            if path_dict[_next] <= cur_dis:
                continue
            else:
                res = max(res, dfs(_next, cur_dis + 1) - 1)
        else:
            res = max(res, dfs(_next, cur_dis + 1) + 1)
    return res

res = dfs(u, 0)
if res == 0:
    print(distance - 1)
else:
    print(distance + res - 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,u,v = map(int,input().split())
l = [[] for _ in range(n+1)]
x = [0 for _ in range(n+1)]
y = [0 for _ in range(n+1)]
for i in range(n-1):
  ai,bi = map(int,input().split())
  l[ai].append(bi)
  l[bi].append(ai)
def s(p,a,m):
  global x
  for li in l[a]:
    if li != p:
      x[li] = m+1
      s(a,li,m+1)
  return
def t(p,a,m):
  global y
  for li in l[a]:
    if li != p:
      y[li] = m+1
      t(a,li,m+1)
  return
s(-1,u,0)
t(-1,v,0) 
mx = 0
for i in range(1,n+1):
  if x[i] < y[i]:
    if y[i] -1 > mx:
      mx = y[i]-1
print(mx)

Submission status: Time Limit Exceeded

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 = [set() for _ in range(N)]
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 aoki_nodes
    aoki_nodes[d].add(s)
    for t in lines[s]:
        if t !=b:
            dfs(t,s,d+1)
    return

stack = [(A,-1,0)]
aoki_nodes = [set() for _ in range(N)]

while len(stack)>0:
    s,b,d = stack.pop()
    aoki_nodes[d].add(s)
    for t in lines[s]:
        if t != b and d < N:
            stack.append((t,s,d+1))

turn = 0
takahashi = [set() for _ in range(N)]
takahashi[0].add(T)
while True:
    taka = takahashi[turn] - aoki_nodes[turn]
    next = set()
    for s in taka:
        takahashi[turn+1] |= lines[s]
    takahashi[turn+1] -= aoki_nodes[turn]

    if len(takahashi[turn+1]) == 0:
        print(turn)
        break
    turn += 1
    assert turn<N+5, "error"

Submission status: Time Limit Exceeded

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

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)

    def dfs(c,p,d):
        dep[c] = d
        for to in G[c]:
            if to != p:
                dfs(to, c, d+1)

    dep = [0]*n
    dfs(v, -1, 0)
    a = dep[:]
    dfs(u, -1, 0)
    b = dep

    ans = 0
    for i in range(n):
        if b[i] >= a[i]:
            continue
        tmp = 0
        d = b[i]
        if d != 0:
            tmp = 2*d
            aoki = d
        else:
            aoki = 0
        tak = a[i]
        m = tak-aoki
        if m%2==1:
            tmp += 2*m -1
        else:
            tmp += 2*(m-1)
        ans = max(ans, tmp)
    print(ans//2)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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.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):
    pp = par[now]
    que = deque([pp])
    while que:
        i = que.pop()
        m = max(m, depth[i])
        for nv in G[i]:
            if depth[nv]<depth[i] or nv == pp:
                continue
            que.append(nv)
    now = pp
print(m-1)

Submission status: Time Limit Exceeded

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


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)

is_leaf = [0]*n
def dfs(c,p,d):
    dep[c] = d
    f = True
    for to in G[c]:
        if to != p:
            dfs(to, c, d+1)
            f = False
    if f:
        is_leaf[c] = 1


dep = [0]*n
dfs(v, -1, 0)
a = dep[:]
leaf = is_leaf[:]
dfs(u, -1, 0)
b = dep

ans = 0
for i in range(n):
    if not leaf[i]:
        continue
    if b[i] >= a[i]:
        continue
    tmp = 0
    d = b[i]
    if d != 0:
        tmp = 2*d
        aoki = d
    else:
        aoki = 0
    tak = a[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: Time Limit Exceeded

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

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

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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


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


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

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

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


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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 = [set() for _ in range(N)]
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 aoki_nodes
    aoki_nodes[d].add(s)
    for t in lines[s]:
        if t !=b:
            dfs(t,s,d+1)
    return

stack = [(A,-1,0)]
aoki_nodes = [set() for _ in range(N)]

while len(stack)>0:
    s,b,d = stack.pop()
    aoki_nodes[d].add(s)
    for t in lines[s]:
        if t != b and d < N:
            stack.append((t,s,d+1))

turn = 0
takahashi = [set() for _ in range(N)]
takahashi[0].add(T)
while True:
    for s in takahashi[turn]:
        if s in aoki_nodes[turn]:
            continue
        else:
            takahashi[turn+1] |= lines[s] - aoki_nodes[turn]
    if len(takahashi[turn+1]) == 0:
        print(turn)
        break
    turn += 1
    assert turn<N+5, "error"

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys

    input = sys.stdin.readline

    sys.setrecursionlimit(10 ** 7)

    def dfs(v, dist):
        for u in g[v]:
            if dist[u] == -1:
                dist[u] = dist[v] + 1
                dfs(u, dist)

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

    g = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        g[a].add(b)
        g[b].add(a)

    dist_from_a = [-1] * N
    dist_from_a[v] = 0
    dfs(v, dist_from_a)

    def dfs2(v, d):
        ret = d
        for u in g[v]:
            if dist_from_a[u] > d + 1:
                ret = max(ret, dfs2(u, d + 1))
            elif dist_from_a[u] == d + 1:
                ret = max(ret, d + 1)
        return ret

    print(dfs2(u, 0))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, V, U = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]

if V == U:
    print(0)
    exit()

V -= 1
U -= 1
graph = [[] for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

# 深い方に逃げるべき
# 子どものうち一番深い場所の深さ
children_depths = [-1 for _ in range(N)]
parents = [None for _ in range(N)]

stack = [(U, None)]
while stack:
    v, parent = stack.pop()
    parents[v] = parent
    for u in graph[v]:
        if u == parent:
            continue
        stack.append((u, v))

v = V
dist = 1
while parents[v] != U:
    v = parents[v]
    dist += 1

stack = []
for v in range(N):
    if len(graph[v]) == 1:
        stack.append((v, 0))
while stack:
    v, depth = stack.pop()
    if v is None:
        continue
    children_depths[v] = max(children_depths[v], depth)
    stack.append((parents[v], depth + 1))

# 何回親側に上がるか
p_cnt = 0
v = V
ans = 0
while dist > 0:
    ans = max(ans, dist - 1 + children_depths[v] + p_cnt)
    v = parents[v]
    p_cnt += 1
    dist -= 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,u,v=[int(i) for i in input().split(" ")]
u-=1
v-=1
graph=[[0 for i in range(N)] for j in range(N)]
for i in range(N-1):
    A,B=[int(j) for j in input().split(" ")]
    graph[A-1][B-1]=1
    graph[B-1][A-1]=1

dist_takahashi=[-1 for i in range(N)]
dist_takahashi[u]=0
next=[u]
d=1
while -1 in dist_takahashi:
    _next=[]
    for n in next:
        for i in range(N):
            if graph[n][i]==1 and dist_takahashi[i]==-1:
                _next.append(i)
    for n in _next:
        dist_takahashi[n]=d
    next=_next
    d+=1

dist_aoki=[-1 for i in range(N)]
dist_aoki[v]=0
next=[v]
d=1
while -1 in dist_aoki:
    _next=[]
    for n in next:
        for i in range(N):
            if graph[n][i]==1 and dist_aoki[i]==-1:
                _next.append(i)
    for n in _next:
        dist_aoki[n]=d
    next=_next
    d+=1


retval=0

for i in range(N):
    if dist_aoki[i]<dist_takahashi[i]:
        continue

    retval=max(retval,dist_aoki[i]-1)


print(retval)

Submission status: Time Limit Exceeded

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 = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = inpl()
    lines[a-1].append(b-1)
    lines[b-1].append(a-1)

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

stack = [(A,-1,0)]
aoki_nodes = [set() for _ in range(N)]

while len(stack)>0:
    s,b,d = stack.pop()
    aoki_nodes[d].add(s)
    for t in lines[s]:
        if t != b and d < N:
            stack.append((t,s,d+1))

turn = 0
takahashi = [set() for _ in range(N)]
takahashi[0].add(T)
while True:
    nexts = set()
    for s in takahashi[turn]:
        if s in aoki_nodes[turn]:
            continue
        for t in lines[s]:
            if t not in aoki_nodes[turn]:
                takahashi[turn+1].add(t)
    if len(takahashi[turn+1]) == 0:
        print(turn)
        break
    turn += 1
    assert turn<N+5, "error"

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

n,u,v = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n-1)]
tree = [list() for i in range(n)]
depth = [0] * n
depth2 = [0] * n
already = [1] * n
already[v-1] = 0
q = deque([v-1])
for a,b in ab:
  a,b = a-1,b-1
  tree[a].append(b)
  tree[b].append(a)
d = 0
while True:
  q2 = deque()
  while q:
    now = q.popleft()
    depth[now] = d
    for i in tree[now]:
      if already[i]:
        q2.append(i)
        already[i] = 0
  if q2:
    q = copy.copy(q2)
    d += 1
  else:
    break
# print(depth)
q = deque([u-1])
d = 0
ans = 0
while True:
  q2 = deque()
  while q:
    now = q.popleft()
    if depth[now] == d:
      ans = max(ans,d)
      continue
    elif depth[now] < d:
      ans = max(ans,d-1)
      continue
    for i in tree[now]:
      q2.append(i)
  if q2:
    q = copy.copy(q2)
    d += 1
  else:
    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, V, U = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]

if V == U:
    print(0)
    exit()

V -= 1
U -= 1
graph = [[] for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

# 深い方に逃げるべき
# 子どものうち一番深い場所の深さ
children_depths = [-1 for _ in range(N)]
parents = [None for _ in range(N)]

stack = [(U, None)]
while stack:
    v, parent = stack.pop()
    parents[v] = parent
    for u in graph[v]:
        if u == parent:
            continue
        stack.append((u, v))

v = V
dist = 1
while parents[v] != U:
    v = parents[v]
    dist += 1

stack = []
for v in range(N):
    if len(graph[v]) == 1:
        stack.append((v, 0))
while stack:
    v, depth = stack.pop()
    if v == None:
        continue
    children_depths[v] = max(children_depths[v], depth)
    stack.append((parents[v], depth + 1))

# 何回親側に上がるか
p_cnt = 0
v = V
ans = 0
while dist > 0:
    ans = max(ans, dist - 1 + children_depths[v] + p_cnt)
    v = parents[v]
    p_cnt += 1
    dist -= 2
print(ans)