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 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
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 v_next:
                continue
            if np in u_next:
                # print("touched!!!")
                ans = count
                u_next.remove(np)

            v_next.add(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
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 u_next:
                # print("touched!!!")
                ans = count
                u_next.remove(np)
            else:
                v_next.add(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
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 u_next:
                # print("touched!!!")
                ans = count
                u_next.remove(np)
            v_next.add(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
import math
sys.setrecursionlimit(1000000)

class DFS():
    def __init__(self, tree, N, root):
        self.tree = tree
        self.N = N
        self.dist = [-1]*(self.N)   # distance from root
    
        self.dfs(root, 0)

    def dfs(self, v, d):
        self.dist[v] = d
        for child in self.tree[v]:
            if self.dist[child] < 0:
                self.dfs(child, d + 1)

N, u, v = list(map(int, input().split()))
tree = [[] for i in range(N)]

u -= 1
v -= 1

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

dfs_u = DFS(tree, N, u)
dfs_v = DFS(tree, N, v)

d_max = 0
for i in range(N):
    if dfs_u.dist[i] < dfs_v.dist[i]:
        if d_max <= dfs_v.dist[i]:
            d_max = dfs_v.dist[i]

print(d_max - 1)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]
def parent_children(start, g):
    parent, children, depth, q = [-1]*len(g), make_list(len(g), 0), [-1]*len(g), deque([start]); depth[start] = 0
    while q:
        i = q.popleft()
        for j in g[i]:
            if depth[j] != -1: parent[i] = j
            else: depth[j] = depth[i] + 1; children[i].append(j), q.append(j)
    return parent, children, depth
def adjacency_list(N, edges):
    g = make_list(N, 0)
    for a, b in edges: g[a].append(b), g[b].append(a)
    return g

sys.setrecursionlimit(1000000)
dire, dire8 = [[1, 0], [0, 1], [-1, 0], [0, -1]], [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets, ALPHABETS = "abcdefghijklmnopqrstuvwxyz", "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD, INF = 1000000007, float("inf")

def main():
    N, u, v = LI()
    AB = LIR1(N-1)
    max_dist = [None] * N
    g = adjacency_list(N, AB)
    parent, children, depth = parent_children(v-1, g)

    def dfs(i):
        dist = max([0] + [dfs(j) for j in children[i]])
        max_dist[i] = dist
        return dist + 1
    dfs(v-1)

    mid = u-1
    for _ in range((depth[u-1] - 1)//2):
        mid = parent[mid]
    print(depth[mid] + max_dist[mid] - 1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import defaultdict,deque
    from math import ceil
    from sys import setrecursionlimit
    setrecursionlimit(10**6)
    f = lambda :map(int,input().split())
    n,u,v = f() # u:高橋
    edge = defaultdict(list)
    for i in range(n-1):
        a,b = f()
        edge[a].append(b)
        edge[b].append(a)
    
    distance = [[-1]*2 for _ in range(n+1)]
    distance[u][0] = 0
    distance[v][1] = 0
    def dfs(parent, start):
        distance_parent = distance[parent][start]
        for child in edge[parent]:
            if distance[child][start] == -1:
                distance[child][start] = distance_parent + 1
                dfs(child, start)
    dfs(u,0)
    dfs(v,1)
    ans = 0
    for u_d, v_d in distance:
        if u_d < v_d:
            ans = max(ans,v_d)
    print(ans-1)


        


main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys


sys.setrecursionlimit(10 ** 6)


def find_path_on_tree(adj, to_node, node, parent=None):
    if node == to_node:
        return [to_node]
    for child in adj[node]:
        if child == parent:
            continue
        p = find_path_on_tree(adj, to_node, child, node)
        if p is None:
            continue
        return [node] + p
    return None


def depth(adj, node, parent=None):
    ret = 0
    for child in adj[node]:
        if child == parent:
            continue
        d = depth(adj, child, node) + 1
        ret = max(ret, d)
    return ret


def main():
    N, U, V = list(map(int, input().split(' ')))
    U -= 1
    V -= 1
    adj = defaultdict(list)
    for _ in range(N - 1):
        A, B = list(map(lambda x: int(x) - 1, input().split(' ')))
        adj[A].append(B)
        adj[B].append(A)
    path = find_path_on_tree(adj, U, V)  # to U from V
    dist = len(path) - 1
    partial_depth = depth(adj, path[(dist // 2) + 1], path[dist // 2])
    print(partial_depth + (dist // 2))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys


sys.setrecursionlimit(10 ** 6)


def find_path(adj, to_node, node, parent=None):
    if node == to_node:
        return [to_node]
    path = None
    for child in adj[node]:
        if child == parent:
            continue
        p = find_path(adj, to_node, child, node)
        if p is None:
            continue
        p = p + [node]
        if path is None or len(path) > len(p):
            path = p
    return path


def depth(adj, node, parent=None):
    ret = 0
    for child in adj[node]:
        if child == parent:
            continue
        d = depth(adj, child, node) + 1
        ret = max(ret, d)
    return ret


def main():
    N, U, V = list(map(int, input().split(' ')))
    U -= 1
    V -= 1
    adj = defaultdict(list)
    for _ in range(N - 1):
        A, B = list(map(lambda x: int(x) - 1, input().split(' ')))
        adj[A].append(B)
        adj[B].append(A)
    path = find_path(adj, U, V)  # to U from V
    path.reverse()
    dist = len(path) - 1
    partial_depth = depth(adj, path[(dist // 2) + 1], path[dist // 2])
    print(partial_depth + (dist // 2))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys


sys.setrecursionlimit(10 ** 6)


def find_path(adj, to_node, node, parent=None):
    if node == to_node:
        return [to_node]
    path = None
    for child in adj[node]:
        if child == parent:
            continue
        p = find_path(adj, to_node, child, node)
        if p is None:
            continue
        p = [node] + p
        if path is None or len(path) > len(p):
            path = p
    return path


def depth(adj, node, parent=None):
    ret = 0
    for child in adj[node]:
        if child == parent:
            continue
        d = depth(adj, child, node) + 1
        ret = max(ret, d)
    return ret


def main():
    N, U, V = list(map(int, input().split(' ')))
    U -= 1
    V -= 1
    adj = defaultdict(list)
    for _ in range(N - 1):
        A, B = list(map(lambda x: int(x) - 1, input().split(' ')))
        adj[A].append(B)
        adj[B].append(A)
    path = find_path(adj, U, V)  # to U from V
    dist = len(path) - 1
    partial_depth = depth(adj, path[(dist // 2) + 1], path[dist // 2])
    print(partial_depth + (dist // 2))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

dist=[[-1, -1] for _ in range(n)]
dist[v][0]=0
dist[u][1]=0

def dfs1(graph,v):
    vv=graph[v]
    for vvv in vv:
        if dist[vvv][0]==-1:
            dist[vvv][0]=dist[v][0]+1
            dfs1(graph,vvv)

def dfs2(graph,v):
    vv=graph[v]
    for vvv in vv:
        if dist[vvv][1]==-1:
            dist[vvv][1]=dist[v][1]+1
            dfs2(graph,vvv)

dfs1(graph,v)
dfs2(graph,u)
dist.sort(reverse=True)

for i in range(10**6):
    if dist[i][0]-dist[i][1]>=1:
        print(dist[i][0]-1)
        break

Submission status: Time Limit Exceeded

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,u,v = map(int,ipt().split())
    way = [[] for _ in range(n+1)]
    for _ in range(n-1):
        a,b = map(int,ipt().split())
        way[a].append(b)
        way[b].append(a)

    ta = [-1]*(n+1)
    tt = [-1]*(n+1)
    ta[v] = 0 #AOKI
    qa = queue.Queue()
    qt = queue.Queue()
    qt.put((0,u))
    qa.put((0,v))
    while (not qt.empty()) or (not qa.empty()):
        nqt = queue.Queue()
        nqa = queue.Queue()
        while not qt.empty():
            ti,pi = qt.get()
            if ta[pi] != -1:
                continue
            for i in way[pi]:
                if ta[i] == -1:
                    tt[i] = ti+1
                    nqt.put((ti+1,i))
        while not qa.empty():
            ti,pi = qa.get()
            for i in way[pi]:
                if ta[i] == -1:
                    ta[i] = ti+1
                    nqa.put((ti+1,i))
        qt = nqt
        qa = nqa
    ma = 0
    for i,tti in enumerate(tt[1::]):
        tai = ta[i+1]
        if tti == -1:
            continue
        if ma < tti+(tai-tti)//2:
            ma = tti+(tai-tti)//2
    print(ma)


    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,u,v = map(int,ipt().split())
    way = [[] for _ in range(n+1)]
    for _ in range(n-1):
        a,b = map(int,ipt().split())
        way[a].append(b)
        way[b].append(a)

    t = 0
    ta = [-1]*(n+1)
    tt = [-1]*(n+1)
    ta[v] = 0 #AOKI
    hqt = [(0,u)]
    hqa = [(0,v)]
    mt = 0
    while hqt or hqa:
        while hqt and hqt[0][0] == t:
            ti,pi = hpq.heappop(hqt)
            if ta[pi] != -1:
                continue
            for i in way[pi]:
                if ta[i] == -1:
                    tt[i] = ti+1
                    hpq.heappush(hqt,(ti+1,i))
        while hqa and hqa[0][0] == t:
            ti,pi = hpq.heappop(hqa)
            for i in way[pi]:
                if ta[i] == -1:
                    ta[i] = ti+1
                    hpq.heappush(hqa,(ti+1,i))
        t += 1
    ma = 0
    for i in range(1,n+1):
        if tt[i] == -1:
            continue
        if ma < tt[i]+(ta[i]-tt[i])//2:
            ma = tt[i]+(ta[i]-tt[i])//2
    print(ma)


    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,u,v = map(int,ipt().split())
    way = [[] for _ in range(n+1)]
    for _ in range(n-1):
        a,b = map(int,ipt().split())
        way[a].append(b)
        way[b].append(a)

    t = 0
    tp = [-1]*(n+1)
    tp[v] = 0 #AOKI
    hqt = [(0,u)]
    hqa = [(0,v)]
    while hqt:
        f = False
        while hqt and hqt[0][0] == t:
            ti,pi = hpq.heappop(hqt)
            if tp[pi] == 0:
                continue
            for i in way[pi]:
                if tp[i] == -1:
                    f = True
                    hpq.heappush(hqt,(ti+1,i))
        while hqa and hqa[0][0] == t:
            ti,pi = hpq.heappop(hqa)
            for i in way[pi]:
                if tp[i] == -1:
                    tp[i] = 0
                    hpq.heappush(hqa,(ti+1,i))
        if f:
            t += 1
    print(t)

    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
import math
import bisect
def input():
    return sys.stdin.readline()[:-1]

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)
seen = [-1 for i in range(n)]
taka = []
aok = []
def dfs(s,lis):
    nec = g[s]
    if len(nec)==1:
        lis.append(s)
    for i in nec:
        if seen[i]!=-1:
            continue
        seen[i] = seen[s]+1
        dfs(i,lis)

seen[u]=0
dfs(u,taka)
takadist = [i for i in seen]
seen = [-1 for i in range(n)]
seen[v]=0
dfs(v,aok)
ans = 0
for i in aok:
    if takadist[i]<seen[i]:
        ans = max(ans,seen[i])
if g[u]==[v]:
    print(0)
else:
    print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as d

def bfs(adj, start, n):
	visited = [False] * (n + 1)
	tab = [0] * n
	queue = []
	queue.append(start)
	visited[start] = True
	while queue:
		s = queue.pop(0)
		for i in adj[s]:
			if visited[i] == False:
				queue.append(i)
				visited[i] = True
				tab[i - 1] = tab[s - 1] + 1
	return tab

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

takahashi = bfs(adj, u, n)
aoki = bfs(adj, v, n)
res = -1
for i in range(n):
	if takahashi[i] <= aoki[i]:
		res = max(res, aoki[i] - 1)

print(res)

Submission status: Time Limit Exceeded

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

n, u, v = map(int, input().split())
u, v = u-1, v-1
edges = [[] for i in range(n)]
for i in range(n-1):
    ai, bi = map(int, input().split())
    ai, bi = ai-1, bi-1
    edges[ai].append(bi)
    edges[bi].append(ai)

def dfs(already, node, depth):
    depth += 1
    children = edges[node]
    for child in children:
        if already[child] == 0:
            already[child] = depth
            already = dfs(already, child, depth)
    return already

already_u = [0 for i in range(n)]
already_u[u] = -1
already_u = dfs(already_u, u, 0)
already_u[u] = 0
already_v = [0 for i in range(n)]
already_v[v] = -1
already_v = dfs(already_v, v, 0)
already_v[v] = 0

maxi = 0
for i in range(n):
    if already_u[i] < already_v[i]:
        maxi = max(maxi, already_v[i])
print(maxi-1)

Submission status: Time Limit Exceeded

Solution code:
N,u,v=map(int,input().split())
dist_v=[-1 for _ in range(N+1)]
dist_u=[-1 for _ in range(N+1)]
Graph=[[] for _ in range(N+1) for _ in range(N+1)]

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

def dfs(v,dist=0):
    dist_v[v]=dist
    for nv in Graph[v]:
        if dist_v[nv]!=-1:
            continue
        dfs(nv,dist+1)  

def dfs_u(u,dist=0):
    dist_u[u]=dist
    for nu in Graph[u]:
        if dist_u[nu]!=-1:
            continue
        dfs(nu,dist+1)  
dfs(v)
dfs_u(u)
ans=0
for i in range(1,N+1):
    if dist_v[i]<=dist_u[i]:
        continue
    ans=max(ans,dist_v[i]-1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7
    
    # u高橋, s青木
    n,u,s = map(int, input().split())
    adj = [[] 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)
    ta = [-1]*n
    ao = [-1]*n

    d = deque([s-1])
    ao[s-1] = 0
    while d:
        v = d.popleft()
        for nv in adj[v]:
            if ao[nv] == -1:
                ao[nv] = ao[v] + 1
                d.append(nv)

    d = deque([u-1])
    ta[u-1] = 0
    while d:
        v = d.popleft()
        for nv in adj[v]:
            if ta[v]+1 <= ao[nv] and ta[v] < ao[v]:
                ta[nv] = ta[v] + 1
                d.append(nv)
    print(max(ta))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**5)
def input(): return sys.stdin.readline().strip()

def main():
    N, u, v = map(int, input().split())
    u -= 1
    v -= 1
    repn = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b = map(int, input().split())
        repn[a - 1].append((b - 1, i))
        repn[b - 1].append((a - 1, i)) # (to, id)

    """
    まずu, vを結ぶ単純パス上にあるnodeを列挙する。
    これはvを根とする根付き木に対するdfs（再帰）により求まる（参考：ABC152F）
    """

    path = []
    def connected(v, tv, p=-1):
        if v == tv:
            return True
        for w, _ in repn[v]:
            if w == p:
                continue
            elif connected(w, tv, v):
                path.append(w)
                return True
        return False
    connected(v, u)
    path.append(v)
    #print("path={}".format(path))

    """
    次にu, vを結ぶ単純パスP上の各頂点wに対して、wからPに沿わない向きにどれだけ深く潜れるかを求める。
    しかし最終的には「頂点vから（高橋君が逃げ込める中で）最も遠い頂点」を求めればよいので、
    uvの中点からdfsすれば十分。
    """

    def dfs(v, p): # Pと異なる頂点方向にdfsして深さを求める
        d = -1
        for w, _ in repn[v]:
            if w == p:
                continue
            else:
                d = max(d, dfs(w, v))
        return d + 1
    
    dist = len(path)
    mid = path[dist // 2 - 1]
    par = path[dist // 2]
    ans = dfs(mid, par)
    print(ans + (dist - 1) // 2)
   


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().strip()

def main():
    N, u, v = map(int, input().split())
    u -= 1
    v -= 1
    repn = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b = map(int, input().split())
        repn[a - 1].append((b - 1, i))
        repn[b - 1].append((a - 1, i)) # (to, id)

    """
    まずu, vを結ぶ単純パス上にあるnodeを列挙する。
    これはvを根とする根付き木に対するdfs（再帰）により求まる（参考：ABC152F）
    """

    path = []
    def connected(v, tv, p=-1):
        if v == tv:
            return True
        for w, _ in repn[v]:
            if w == p:
                continue
            elif connected(w, tv, v):
                path.append(w)
                return True
        return False
    connected(v, u)
    path.append(v)
    #print("path={}".format(path))

    """
    次にu, vを結ぶ単純パスP上の各頂点wに対して、wからPに沿わない向きにどれだけ深く潜れるかを求める。
    ただしu-v間のuより半分だけ求めれば十分。全く潜れない場合を０とする。
    """

    def dfs(v, P): # Pに含まれない頂点方向にdfsして深さを求める
        d = -1
        for w, _ in repn[v]:
            if w in P:
                continue
            else:
                d = max(d, dfs(w, [v]))
        return d + 1
    
    depth = []
    dist = len(path)
    for i, w in enumerate(path):
        if i == 0:
            depth.append(dfs(w, path[:2]))
        elif i < dist // 2:
            depth.append(dfs(w, [path[i - 1],path[i + 1]]))
        else:
            break
    #print("depth={}".format(depth))

    """
    これで準備は完了。あとはu-v間の距離から高橋君が青木君から逃げるのにpath上の
    どの頂点から潜るのかを求めればよい。
    """

    ans = 0
    for i in range(dist // 2):
        val = (dist - i - 1) + depth[i] - 1
        ans = max(ans, val)
    print(ans)
   


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().strip()

def main():
    N, u, v = map(int, input().split())
    u -= 1
    v -= 1
    repn = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b = map(int, input().split())
        repn[a - 1].append((b - 1, i))
        repn[b - 1].append((a - 1, i)) # (to, id)

    """
    まずu, vを結ぶ単純パス上にあるnodeを列挙する。
    これはvを根とする根付き木に対するdfs（再帰）により求まる（参考：ABC152F）
    """

    path = []
    def connected(v, tv, p=-1):
        if v == tv:
            return True
        for w, _ in repn[v]:
            if w == p:
                continue
            elif connected(w, tv, v):
                path.append(w)
                return True
        return False
    connected(v, u)
    path.append(v)
    #print("path={}".format(path))

    """
    次にu, vを結ぶ単純パスP上の各頂点wに対して、wからPに沿わない向きにどれだけ深く潜れるかを求める。
    ただしu-v間のuより半分だけ求めれば十分。全く潜れない場合を０とする。
    """

    def dfs(v, P): # Pに含まれない頂点方向にdfsして深さを求める
        d = -1
        for w, _ in repn[v]:
            if w in P:
                continue
            else:
                d = max(d, dfs(w, [v]))
        return d + 1
    
    depth = []
    dist = len(path)
    for i, w in enumerate(path):
        if i < dist // 2:
            depth.append(dfs(w, path))
        else:
            break
    #print("depth={}".format(depth))

    """
    これで準備は完了。あとはu-v間の距離から高橋君が青木君から逃げるのにpath上の
    どの頂点から潜るのかを求めればよい。
    """

    ans = 0
    for i in range(dist // 2):
        val = (dist - i - 1) + depth[i] - 1
        ans = max(ans, val)
    print(ans)
   


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def dfs(G, v, p, d, depth):
    depth[v] = d
    for nv in G[v]:
        if nv == p:
            continue
        dfs(G, nv, v, d+1, depth)
    return G, depth


n, T, A = map(int,input().split())
T, A = T-1, A-1
g = [[] for _ in range(n)]
for i in range(n-1):
    x, y = map(int,input().split())
    x, y = x-1, y-1
    g[x].append(y)
    g[y].append(x)

depth = [0]*n
GT = copy.deepcopy(g)
GT[T].append(-1)
GT, dt = dfs(GT, T, -1, 0, depth)

depth = [0]*n
GA = copy.deepcopy(g)
GA[A].append(-1)
GA, da = dfs(GA, A, -1, 0, depth)

def dfs2(G, v, p, md):
    for nv in G[v]:
        if nv == p:
            continue
        if dt[nv] <= da[nv]:
            md[0] = max(md[0], da[nv])
        else:
            continue
        dfs2(G, nv, v, md)
    return md


maxd = dfs2(GT, T, -1, [da[T]])
print(maxd[0]-1)

Submission status: Time Limit Exceeded

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

def dfs(G, v, p, d):
    depth[v] = d
    for nv in G[v]:
        if nv == p:
            continue
        dfs(G, nv, v, d+1)


n, T, A = map(int,input().split())
T, A = T-1, A-1
g = [[] for _ in range(n)]
for i in range(n-1):
    x, y = map(int,input().split())
    x, y = x-1, y-1
    g[x].append(y)
    g[y].append(x)

depth = [0]*n
GT = copy.deepcopy(g)
GT[T].append(-1)
root = T
dfs(GT, root, -1, 0)
dt = depth.copy()

depth = [0]*n
GA = copy.deepcopy(g)
GA[A].append(-1)
root = A
dfs(GA, root, -1, 0)
da = depth.copy()

def dfs2(GT, v, p):
    for nv in GT[v]:
        if nv == p:
            continue
        if dt[nv] <= da[nv]:
            maxd[0] = max(maxd[0], da[nv])
        else:
            continue
        dfs2(GT, nv, v)


maxd = [da[T]]
root = T
dfs2(GT, root, -1)
print(maxd[0]-1)

Submission status: Time Limit Exceeded

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


def BFS(g, s):
    d = 0
    dt = dict()
    visited = set()
    visited.add(s)
    Q = [s]

    while len(Q):
        d += 1
        Qs = len(Q)
        for _ in range(Qs):
            Qpop = Q[0]
            Q = Q[1:]
            for node in g[Qpop]:
                if node not in visited:
                    Q.append(node)
                    visited.add(node)
                    dt[node] = d
    return dt


def main():
    l = [int(e) for e in si().split()]
    n, u, v = l[0], l[1], l[2]
    graph = [[] for _ in range(n+1)]
    for _ in range(n-1):
        l = [int(e) for e in si().split()]
        graph[l[0]].append(l[1])
        graph[l[1]].append(l[0])

    udt = BFS(graph, u)
    vdt = BFS(graph, v)
    udt[u], vdt[v] = 0, 0

    vdmax = 0
    for i in range(1, n+1):
        if (vdt[i]-udt[i]) > 0 and vdt[i] > vdmax:
            vdmax = vdt[i]
    print(vdmax-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
inf = 10 ** 6
import sys
sys.setrecursionlimit(inf)

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

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

amemo = [inf] * N
tmemo = [inf] * N
def dfs_a(i, c):
    if amemo[i] != inf:
        return
    amemo[i] = c
    for j in tree[i]:
        dfs_a(j, c+1)
def dfs_t(i, c):
    if tmemo[i] != inf:
        return
    tmemo[i] = c
    for j in tree[i]:
        dfs_t(j, c+1)
dfs_a(v, 0)
dfs_t(u, 0)
ans = 0
for t, a in zip(tmemo, amemo):
    if t < a:
        ans = max(ans, a)

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
n,u,v=map(int,input().split())
edge=[[] for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
ans=0
a=set([v])
t=set([u])
j=1
while t:
    if j:
        tl=t
        j^=1
        t=set()
        for i in tl:
            t|=set(edge[i])
        t-=a
    else:
        tl=a
        j^=1
        a=set()
        for i in tl:
            a|=set(edge[i])
        t-=a
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)


def input():
    return sys.stdin.readline()


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

uu = [0] * n
vv = [0] * n


def dfs(ve, r=u, d=0, rr=-1):
    ve[r] = d
    for i in e[r]:
        if i == rr:
            continue
        dfs(ve, i, d + 1, r)


dfs(uu, u)
dfs(vv, v)


ans = 0
for i, j in zip(uu, vv):
    if i <= j:
        ans = max(ans, j)
print(ans-1)