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
sys.setrecursionlimit(10**6)

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

def dfs(node, count,li):
    li[node] = count
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i, count + 1,li)
def search_path(node,t):
    if node == t:
        return
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            pre_node[i] = node
            search_path(i, t)
finished = set()
dfs(u,0,takahashi)
finished = set()
dfs(v,0,aoki)
finished = set()
path = []
pre_node = [0 for i in range(n+1)]
#最短炉を出す
search_path(u,v)
while v != u:
    path = [v] + path
    v = pre_node[v]
start = u

#ギリギリまで高橋君に近づく
for i in range(len(path)-1):
    if aoki[path[i+1]] <= i+1:
        start = path[i]
        break
finished = set()
#近づいたとこからdfs
ans_path = [0 for i in range(n+1)]
dfs(start,0,ans_path)
ans = 0
for i in range(1,n+1):
    if aoki[i] >= takahashi[start] + ans_path[i]:
        ans = max(ans, ans_path[i])
print(ans + aoki[start] - 1)

Submission status: Time Limit Exceeded

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

read = sys.stdin.read
N, u, v, *AB = map(int, read().split())
AB = np.array(AB, np.int32).reshape(N - 1, 2)

a = AB[:, 0]
b = AB[:, 1]
d = np.ones_like(a, np.int32)

graph = coo_matrix((d, (a, b)), shape=(N + 1, N + 1))
graph.tocsr()
takahashi = dijkstra(graph, directed=False, indices=u)
aoki = dijkstra(graph, directed=False, indices=v)

print(int(aoki[takahashi < aoki].max()) - 1)

Submission status: Time Limit Exceeded

Solution code:
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 = []
step = [0 for _ in range(n+1)]
q.append([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.append([node,v+1])
            visied.add(node)           
q =[]
q.append((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.append(add)
                queue.add(add)
                p=1
        else:
            value = max(value,step[node])
    if p ==0:
        mx = max(mx,value)
# print(step)
print(mx)

Submission status: Time Limit Exceeded

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

read = sys.stdin.read
N, u, v, *AB = map(int, read().split())
AB = np.array(AB, np.int32).reshape(N - 1, 2)

a = AB[:, 0]
b = AB[:, 1]
d = np.ones_like(a, np.int32)

graph = csr_matrix((d, (a, b)), shape=(N + 1, N + 1))
takahashi = dijkstra(graph, directed=False, indices=u)
aoki = dijkstra(graph, directed=False, indices=v)

print(int(aoki[takahashi < aoki].max()) - 1)

Submission status: Time Limit Exceeded

Solution code:
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 = []
step = [0 for _ in range(n+1)]
q.append([v,0])
visied = set()
visied.add(v)
inqueue = set()
while len(q)>0:
    a,v = q.pop()
    visied.add(a)
    for node in edge[a]:
        if node not in visied:
            step[node] = v+1
            if node not in inqueue:
                q.append([node,v+1])
                inqueue.add(node)
q =[]
q.append((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.append(add)
                queue.add(add)
                p=1
        else:
            value = max(value,step[node])
    if p ==0:
        mx = max(mx,value)
# print(step)
print(mx)

Submission status: Time Limit Exceeded

Solution code:
import sys; readline = sys.stdin.readline
from collections import deque
sys.setrecursionlimit(1000000000)

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

A = [a - 1 for a, b in AB]
B = [b - 1 for a, b in AB]

U, V = U - 1, V - 1

conn = {}
for a, b in zip(A, B):
    if not a in conn:
        conn[a] = []
    conn[a].append(b)

    if not b in conn:
        conn[b] = []
    conn[b].append(a)

t = [0 for i in range(N)]

def dfsU(u, parent, depth):
    t[u] = depth

    for _u in conn[u]:
        if _u != parent:
            dfsU(_u, u, depth + 1)

dfsU(V, -1, 0)

maxv = 0
maxu = U
def dfsV(v, parent, depth):
    global maxv
    global maxu
    if depth < t[v]:
        if t[v] > maxv:
            maxv = t[v]
            maxu = depth
        for _v in conn[v]:
            if _v != parent:
                dfsV(_v, v, depth + 1)

dfsV(U, -1, 0)
if (maxv - maxu) % 2 == 1:
    print(maxv - 1)
else:
    print(maxv - 1)

Submission status: Time Limit Exceeded

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

read = sys.stdin.read
N, u, v, *AB = map(int, read().split())
AB = np.array(AB, np.int32).reshape(N - 1, 2)

a = AB[:, 0]
b = AB[:, 1]
d = np.ones_like(a, np.int32)

graph = csr_matrix((d, (a, b)), shape=(N + 1, N + 1))
takahashi, aoki = dijkstra(graph, directed=False, indices=[u, v])

print(int(aoki[takahashi < aoki].max()) - 1)

Submission status: Time Limit Exceeded

Solution code:
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 = []
step = [0 for _ in range(n+1)]
q.append([v,0])
visied = set()
visied.add(v)
while len(q)>0:
    a,v = q.pop()
    visied.add(a)
    for node in edge[a]:
        if node not in visied:
            step[node] = v+1
            q.append([node,v+1])
q =[]
q.append([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.append(add)
                queue.add(add)
                p=1
        else:
            value = max(value,step[node])
    if p ==0:
        mx = max(mx,value)
# print(step)
print(mx)

Submission status: Time Limit Exceeded

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

read = sys.stdin.read
N, u, v, *AB = map(int, read().split())

a = AB[::2]
b = AB[1::2]
d = [1] * (N - 1)

graph = coo_matrix((d, (a, b)), shape=(N + 1, N + 1))
takahashi, aoki = dijkstra(graph, directed=False, indices=[u, v])

print(int(aoki[takahashi < aoki].max()) - 1)

Submission status: Time Limit Exceeded

Solution code:
import sys; readline = sys.stdin.readline
from collections import deque
sys.setrecursionlimit(1000000)

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

A = [a - 1 for a, b in AB]
B = [b - 1 for a, b in AB]

U, V = U - 1, V - 1

conn = {}
for a, b in zip(A, B):
    if not a in conn:
        conn[a] = []
    conn[a].append(b)

    if not b in conn:
        conn[b] = []
    conn[b].append(a)

t = [0 for i in range(N)]

def dfsU(u, parent, depth):
    t[u] = depth

    for _u in conn[u]:
        if _u != parent:
            dfsU(_u, u, depth + 1)

dfsU(V, -1, 0)

maxv = 0
maxu = U
def dfsV(v, parent, depth):
    global maxv
    global maxu
    if depth < t[v]:
        if t[v] > maxv:
            maxv = t[v]
            maxu = depth
        for _v in conn[v]:
            if _v != parent:
                dfsV(_v, v, depth + 1)

dfsV(U, -1, 0)
if (maxv - maxu) % 2 == 1:
    print(maxv - 1)
else:
    print(maxv - 1)

Submission status: Time Limit Exceeded

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


def get_path(start, goal, pred):
    return get_path_row(start, goal, pred[start])


def get_path_row(start, goal, pred_row):
    path = []
    i = goal
    while i != start and pred_row[i] > 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]


read = sys.stdin.read
N, u, v, *AB = map(int, read().split())

a = AB[::2]
b = AB[1::2]
d = [1] * (N - 1)

graph = coo_matrix((d, (a, b)), shape=(N + 1, N + 1))
takahashi, aoki = dijkstra(graph, directed=False, indices=[u, v])
n = np.where(takahashi < aoki)
print(int(aoki[n].max()) - 1)

Submission status: Time Limit Exceeded

Solution code:
N,u,v = map(int,input().split())
inf = 10**9
d = [[inf for i in range(N+1)] for j in range(N+1)]
G = [[] for i in range(N+1)]
for i in range(1,N+1):
    d[i][i] = 0
for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
    d[a][b] = 1
    d[b][a] = 1
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(1,N+1):
        for i in range(1,N+1):
            for j in range(1,N+1):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
warshall_floyd(d)

F = [v]
list = []
HA = []
while len(F) > 0:
    x = F.pop(0)
    list.append(x)
    h = []
    for j in G[x]:
        if j not in F:
            if j not in list:
                F.append(j)
                h.append(j)
    if len(h) == 0:
        HA.append(x)
ans = 0
for i in HA:
    x = d[u][i]
    y = d[v][i]
    if y > x:
        a = x + (y-x)//2
        ans = max(a,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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 = []
step = [0 for _ in range(n+1)]
q.append([v,0])
visied = set()
visied.add(v)
while len(q)>0:
    a,v = q.pop()
    visied.add(a)
    for node in edge[a]:
        if node not in visied:
            step[node] = v+1
            q.append([node,v+1])
q =[]
q.append([u,0])
mx= 0
while len(q)>0:
    a, v = q.pop()
    p=0
    for node in edge[a]:
        cur = v+1
        if cur<step[node]:
            q.append([node,cur])
            p=1
        else:
            mx = max(mx,step[node])
    if p ==0:
        # print(node,step[node])
        mx = max(mx,step[node])
# print(step)
print(mx)

Submission status: Time Limit Exceeded

Solution code:
import sys


n,u,v = [int(_) for _ in input().split()]
dic = {}
for i in range(n-1):
    a,b = [int(_) for _ in input().split()]
    if a in dic:
        dic[a].append(b)
    else:
        dic[a] = [b]
    if b in dic:
        dic[b].append(a)
    else:
        dic[b] = [a]
# print(dic)
que = []
seen = {}
dic2 = {}
ans_l = []
for i in range(1,n+1):
    seen[i] = 0
    dic2[i] = 0
# print(seen)
que.append(v)
seen[v] = 1
while len(que) != 0:
    tem_v = que.pop()
    d = dic2[tem_v]
    if len(dic[tem_v]) == 1 and seen[dic[tem_v][0]] == 1:
        ans_l.append((tem_v, d))
        # print(tem_v, dic[tem_v])
    for node in dic[tem_v]:
        if seen[node] == 0:
            que.append(node)
            seen[node] = 1
            dic2[node] = d + 1
# print(dic2)
# print(seen)
ans_l = sorted(ans_l, reverse=True, key=lambda x: x[1])
# print(ans_l)
d_taka = dic2[u]
# print(d_taka)
que.append(u)
way = [u]
while len(que) != 0:
    tem_u = que.pop()
    d = dic2[tem_u]
    for node in dic[tem_u]:
        if dic2[node] < d:
            que.append(node)
            way.append(node)
# print(way)
for i in range(len(ans_l)):
    node, tem_d = ans_l[i]
    que.append(node)
    while len(que) != 0:
        tem_u = que.pop()
        d = dic2[tem_u]
        if tem_u in way:
            ans = tem_u
        else:
            for node2 in dic[tem_u]:
                if node2 in way:
                    ans = node2
                if dic2[node2] < d and node2 not in way:
                    que.append(node2)
    # print('ans', ans)
    if dic2[ans] * 2 > d_taka:
        print(tem_d - 1)
        sys.exit()

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import*
n,t,a,*x=map(int,open(0).read().split())
t,a=csgraph.johnson(csr_matrix(([1]*~-n,(x[::2],x[1::2])),[n+1]*2),0,[t,a])
print(int(max(a[t<a])-1))

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import*
n,t,a,*x=map(int,open(0).read().split())
t,a=csgraph.dijkstra(csr_matrix(([1]*~-n,(x[::2],x[1::2])),[n+1]*2),0,[t,a])
print(int(max(a[t<a])-1))

Submission status: Time Limit Exceeded

Solution code:
N,u,v = map(int,input().split())
inf = 10**9
d = [[inf for i in range(N+1)] for j in range(N+1)]
G = [[] for i in range(N+1)]
for i in range(1,N+1):
    d[i][i] = 0
for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
    d[a][b] = 1
    d[b][a] = 1
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(1,N+1):
        for i in range(1,N+1):
            for j in range(1,N+1):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
warshall_floyd(d)
n = d[u][v]

a = n//2
if (n % 2 == 0):
    for i in range(N):
        if (d[u][i] == a) & (d[v][i] == a):
            s = i
            break
    for j in G[s]:
        if d[u][j] == a-1:
            u = j
        if d[v][j] == a-1:
            v = j
    G[u].remove(s)
else:
    for j in range(N+1):
        if (d[u][j] == a) & (d[v][j] == a+1):
            x = j
        elif (d[v][j] == a) & (d[u][j] == a+1):
            y = j
    u = x
    v = y
    G[u].remove(v)

ans = (n-1)//2

F = [u]
list = []
while len(F) > 0:
    x = F.pop(0)
    list.append(x)
    for j in G[x]:
        if j not in F:
            if j not in list:
                F.append(j)
m = 0
for i in list:
    m = max(m,d[u][i])
ans += m + ((n-1)%2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,u,v = map(int,input().split())
inf = 10**9
d = [[inf for i in range(N+1)] for j in range(N+1)]
G = [[] for i in range(N+1)]
for i in range(1,N+1):
    d[i][i] = 0
for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
    d[a][b] = 1
    d[b][a] = 1
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(1,N+1):
        for i in range(1,N+1):
            for j in range(1,N+1):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
warshall_floyd(d)
n = d[u][v]

a = n//2
if (n % 2 == 0):
    for i in range(N):
        if (d[u][i] == a) & (d[v][i] == a):
            s = i
            break
    for j in G[s]:
        if d[u][j] == a-1:
            u = j
        if d[v][j] == a-1:
            v = j
    G[u].remove(s)
else:
    for j in range(N+1):
        if (d[u][j] == a) & (d[v][j] == a+1):
            x = j
        elif (d[v][j] == a) & (d[u][j] == a+1):
            y = j
    u = x
    v = y
    G[u].remove(v)

ans = (n-1)//2

F = [u]
list = []
while len(F) > 0:
    x = F.pop(0)
    list.append(x)
    for j in G[x]:
        if j not in F:
            if j not in list:
                F.append(j)
m = 0
for i in list:
    m = max(m,d[u][i])
ans += m + ((n-1)%2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def p_f():
    from sys import stdin
    input = stdin.readline
    N, u, v = map(int, input().split())
    edges = [list(map(int, input().split())) for i in range(N - 1)]
    if u == v:
        print(0)
        exit()

    def BFS(K, edges, N):
        roots = [[] for i in range(N)]
        for a, b in edges:
            roots[a - 1] += [(b - 1, 1)]
            roots[b - 1] += [(a - 1, 1)]
        dist = [-1] * N
        stack = []
        stack.append(K)
        dist[K] = 0
        while stack:
            label = stack.pop(-1)
            for i, c in roots[label]:
                if dist[i] == -1:
                    dist[i] = dist[label] + c
                    stack += [i]
        return dist

    dist_v = BFS(v - 1, edges, N)
    dist_u = BFS(u - 1, edges, N)
    # print(dist_v)
    # print(dist_u)
    maxIndex = [i for i, x in enumerate(dist_v) if x == max(dist_v)]
    for i in maxIndex:
        if max(dist_v) > dist_u[i]:
            print(max(dist_v) - 1)
            exit()
    if dist_v[u - 1] > max(dist_v) - dist_v[u - 1]:
        print(max(dist_v) - 1)
    else:
        print(dist_v[u - 1] - 1)


if __name__ == '__main__':
    p_f()

Submission status: Time Limit Exceeded

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

n, u, v = map(int, sys.stdin.readline().split())
a, b = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(-1, 2).T - 1
graph = csr_matrix(([1] * (n-1), (a, b)), (n, n))

def main():
    dist_u, dist_v = dijkstra(graph, directed=False, indices=[u-1, v-1])
    
    ans = np.amax(dist_v[dist_v >= dist_u]) - 1
    return int(ans)

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, U, V = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
U -= 1
V -= 1

g = [[] for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

WHITE = 0
GRAY = 1
BLACK = 2


def dfs(s):
    color = [WHITE] * n
    d = [-1] * n
    f = [-1] * n
    p = [-1] * n
    t = 0
    stack = [s]
    color[s] = GRAY
    d[s] = t
    t += 1
    while stack:
        u = stack[-1]
        for v in g[u]:
            if color[v] == WHITE:
                color[v] = GRAY
                d[v] = t
                p[v] = u
                t += 1
                stack.append(v)
                break
        else:
            color[u] = BLACK
            f[u] = t
            t -= 1
            stack.pop()

    return d


dv = dfs(V)

du = dfs(U)

ans = 0
for due, dve in zip(du, dv):
    if dve > due:
        ans = max(ans, dve - 1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import*
n,t,a,*x=map(int,open(0).read().split())
print(int(max(a-1for t,a in zip(*csgraph.dijkstra(csr_matrix(([1]*~-n,(x[::2],x[1::2])),[n+1]*2),0,[t,a],0,0))if t<a)))

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

n, U, V = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
U -= 1
V -= 1

g = [[] for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

WHITE = 0
GRAY = 1
BLACK = 2

color = [WHITE] * n
d = [-1] * n
f = [-1] * n
p = [-1] * n
t = 0


def dfs(s):
    if color[s] == BLACK:
        return
    global t
    stack = [s]
    color[s] = GRAY
    d[s] = t
    t += 1
    while stack:
        u = stack[-1]
        for v in g[u]:
            if color[v] == WHITE:
                color[v] = GRAY
                d[v] = t
                p[v] = u
                t += 1
                stack.append(v)
                break
        else:
            color[u] = BLACK
            f[u] = t
            t -= 1
            stack.pop()

dfs(V)
d_cp = deepcopy(d)

color = [WHITE] * n
d = [-1] * n
f = [-1] * n
p = [-1] * n
t = 0
dfs(U)

ans = 0
for cpe, de in zip(d_cp, d):
    if cpe > de:
        ans = max(ans, cpe - 1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import*
n,t,a,*x=map(int,open(0).read().split())
print(int(max(a-1for t,a in zip(*csgraph.dijkstra(csr_matrix(([1]*~-n,(x[::2],x[1::2])),[n+1]*2),0,[t,a]))if t<a)))

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import*
n,t,a,*x=map(int,open(0).read().split())
print(max(int(a-1)for t,a in zip(*csgraph.dijkstra(csr_matrix(([1]*~-n,(x[::2],x[1::2])),[n+1]*2),0,[t,a]))if t<a))

Submission status: Time Limit Exceeded

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

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()
dis_dict = {i : 0 for i in range(n)}
stack = [(u, 0, 0)]
while len(stack) > 0:
    ind, cur_dis, minus = stack.pop(-1)
    already.add(ind)
    dis_dict[ind] = cur_dis - minus
    for _next in graph[ind]:
        parent[_next] = ind
        if _next in already:
            continue
        if _next in path:
            if path_dict[_next] <= cur_dis + 1:
                continue
            else:
                stack.append((_next, cur_dis + 1, minus + 2))
        else:
            stack.append((_next, cur_dis + 1, minus))

res = max(dis_dict.values())


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

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 = [(0, aoki)]
aoki_dist = [-1] * n
closed = 0

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

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

index = 0
while index < len(q):
    c0, i = q[index]
    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]
        q.append((c, l))

    index += 1

print(max_dist - 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**5)
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:
def find_most_deep(s):
  global nodes
  check=nodes[s][2][:]
  rt=0
  if len(check)==0:
    return 0
  for i in range(len(check)):
    rt=max(rt,1+find_most_deep(check[i]))
  return rt

Nuv=input().split(" ")
N=int(Nuv[0])
u=int(Nuv[1])-1
v=int(Nuv[2])-1
edge=[]
for i in range(N-1):
  ab=input().split(" ")
  a=int(ab[0])-1
  b=int(ab[1])-1
  edge+=[[min(a,b),max(a,b)]]
edge.sort()
#print(N)
#print(u)
#print(v)
#print(edge)

nodes=[0]*N #[深さ,1つ浅いノード,[1つ深いノード]]
for i in range(N):
  nodes[i]=[-1,-1,-1]
  nodes[i][2]=[]

nodes[v]=[0,-1,[]]
next_depth=[v]
new_next_depth=[]

while len(next_depth)>0:
  for j in range(len(next_depth)):
    i=0
    while i<len(edge):
      if edge[i][0]==next_depth[j]:
        nodes[next_depth[j]][2]+=[edge[i][1]]
        nodes[edge[i][1]][0]=nodes[next_depth[j]][0]+1
        nodes[edge[i][1]][1]=next_depth[j]
        new_next_depth+=[edge[i][1]]
        edge.pop(i)
      elif edge[i][1]==next_depth[j]:
        nodes[next_depth[j]][2]+=[edge[i][0]]
        nodes[edge[i][0]][0]=nodes[next_depth[j]][0]+1
        nodes[edge[i][0]][1]=next_depth[j]
        new_next_depth+=[edge[i][0]]
        edge.pop(i)
      else:
        i+=1
  next_depth=new_next_depth[:]
  new_next_depth=[]
  
#print(nodes)
#[深さ,1つ浅いノード,[1つ深いノード]]
ans=0
ans+=(nodes[u][0]-1)//2
is_odd=nodes[u][0]%2
#print(ans)
for i in range(ans):
  u=nodes[u][1]
#print(u)
#find most deep
#print(find_most_deep(u))
if is_odd:
  print(ans+find_most_deep(u))
else:
  print(ans+find_most_deep(u)+1)

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s, n,  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,u,v = map(int,input().split())

cnt = [0 for i in range(n)]
cost = [[float(10 ** 10) for i in range(n)] for i in range(n)]

for i in range(n-1):
    x, y = map(int, input().split())
    cost[x-1][y-1] = 1
    cost[y-1][x-1] = 1
    cnt[x-1] += 1
    cnt[y-1] += 1

ans = 0
a = dijkstra(u-1,n,cost)
b = dijkstra(v-1,n,cost)
for i in range(n):
    if a[i] <= b[i]:
        if cnt[i] == 1:
            if b[i]-a[i]-1 > 0:
                ans = max(ans,b[i]-1)
        else:
            ans = max(ans,b[i])
print(ans)

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


import heapq

class Dijkstra(object):
    def dijkstra(self, adj, start, goal=None):
        num = len(adj)          # グラフのノード数
        dist = [float('inf') for i in range(num)] # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)] # 最短経路における，その頂点の前の頂点のIDを格納する

        dist[start] = 0
        q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start)) # 始点をpush

        while len(q) != 0:
            prov_cost, src = heapq.heappop(q) # pop

            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest in range(num):
                cost = adj[src][dest]
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost # distの更新
                    heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
                    prev[dest] = src                      # 前の頂点を記録

        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]           # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))


Ta1 =  Dijkstra()
Ta = Ta1.dijkstra(adj=A,start=u-1)
Ao1 = Dijkstra()
Ao = Ao1.dijkstra(adj=A,start=v-1)
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:
N,u,v = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    

dicT = {u-1:0}
dicA = {v-1:0}
ans = 0
while len(dicT) > 0 and len(dicA) > 0:
    tempT = {}
    for t in dicT:
        for e in edge[t]:
            if e not in dicA:
                tempT[e] = 0
                
    dicT = tempT
    if not dicT:
        break
    tempA = {}
    for a in dicA:
        for e in edge[a]:
            if e in dicT:
                dicT[e] = 1
            else:
                tempA[e] = 0
    
    dicA = tempA
    
    tempT = {}
    for t in dicT:
        if dicT[t] == 0:
            tempT[t] = 0
            
    dicT = tempT
    ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s, n,  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


################################
# n:頂点数　w:辺の数
n,u,v = map(int,input().split())

cnt = [0 for i in range(n)]
cost = [[float(10 ** 10) for i in range(n)] for i in range(n)]
# cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(n-1):
    x, y = map(int, input().split())
    cost[x-1][y-1] = 1
    cost[y-1][x-1] = 1
    cnt[x-1] += 1
    cnt[y-1] += 1

ans = 0
a = dijkstra(u-1,n,cost)
b = dijkstra(v-1,n,cost)
for i in range(n):
    if a[i] <= b[i]:
        if cnt[i] == 1:
            if b[i]-a[i]-1 > 0:
                ans = max(ans,b[i]-1)
        else:
            ans = max(ans,b[i])
print(ans)