Problem:


Score : 400 points

Problem Statement

You are given a tree with N vertices.

Here, a tree is a kind of graph, and more specifically, a connected undirected graph with N-1 edges, where N is the number of its vertices.

The i-th edge (1≤i≤N-1) connects Vertices a_i and b_i, and has a length of c_i.

You are also given Q queries and an integer K. In the j-th query (1≤j≤Q):

find the length of the shortest path from Vertex x_j and Vertex y_j via Vertex K.

Constraints

3≤N≤10^5 

1≤a_i,b_i≤N (1≤i≤N-1) 

1≤c_i≤10^9 (1≤i≤N-1) 

The given graph is a tree.

1≤Q≤10^5 

1≤K≤N 

1≤x_j,y_j≤N (1≤j≤Q) 

x_j≠y_j (1≤j≤Q) 

x_j≠K,y_j≠K (1≤j≤Q) 

Input

Input is given from Standard Input in the following format:  

N  
a_1 b_1 c_1  
:  
a_{N-1} b_{N-1} c_{N-1}
Q K
x_1 y_1
:  
x_{Q} y_{Q}

Output

Print the responses to the queries in Q lines.

In the j-th line j(1≤j≤Q), print the response to the j-th query.

Sample Input 1

5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5

Sample Output 1

3
2
4

The shortest paths for the three queries are as follows:

Query 1: Vertex 2 → Vertex 1 → Vertex 2 → Vertex 4 : Length 1+1+1=3 

Query 2: Vertex 2 → Vertex 1 → Vertex 3 : Length 1+1=2 

Query 3: Vertex 4 → Vertex 2 → Vertex 1 → Vertex 3 → Vertex 5 : Length 1+1+1+1=4 

Sample Input 2

7
1 2 1
1 3 3
1 4 5
1 5 7
1 6 9
1 7 11
3 2
1 3
4 5
6 7

Sample Output 2

5
14
22

The path for each query must pass Vertex K=2.

Sample Input 3

10
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
1 1
9 10

Sample Output 3

17000000000



Sample input:
5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5


Sample output:
3
2
4

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop

import sys
sys.setrecursionlimit(100000000)

n = int(input())
G = [[] for _ in range(n + 1)]

for _ in range(n - 1):
    ai, bi, ci = map(int, input().split())
    G[ai].append((bi, ci))
    G[bi].append((ai, ci))

Q, K = map(int, input().split())

# 頂点KからDFSする
d = [None for _ in range(n + 1)]
d[K] = 0

def dfs(v, dist):
    for (u, cvu) in G[v]:
        if d[u] is None:
            d[u] = dist + cvu
            dfs(u, dist + cvu)

dfs(K, 0)

for _ in range(Q):
    xi, yi = map(int, input().split())
    print(d[xi] + d[yi])

Submission status: Time Limit Exceeded

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

N = int(input())
edge = np.array([tuple(map(int, input().split())) for _ in range(N - 1)]).T
Q, K = map(int, input().split())
query = [tuple(map(int, input().split())) for _ in range(Q)]

matr = csr_matrix((edge[2], (edge[0] - 1, edge[1] - 1)), (N, N))
way = tuple(dijkstra(matr, indices=K - 1, directed=False).astype(np.int64))
for x, y in query:
    print(way[x - 1] + way[y - 1])

Submission status: Time Limit Exceeded

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

N = int(input())
edge = np.array([tuple(map(int, input().split())) for _ in range(N - 1)]).T
Q, K = map(int, input().split())
query = [tuple(map(int, input().split())) for _ in range(Q)]

matr = csr_matrix((edge[2], (edge[0] - 1, edge[1] - 1)), (N, N))
way = dijkstra(matr, indices=K - 1, directed=False).astype(np.int64)
for x, y in query:
    print(way[x - 1] + way[y - 1])

Submission status: Time Limit Exceeded

Solution code:
import heapq

class Dijkstra:
    def __init__(self,s,n,e,cost):
        #s:始点 n:頂点数,　e:辺の数, cost[u][v] : uからvのコスト(存在しないときはinf)
        self.s = s
        self.n = n
        self.e = e
        self.cost = cost


    def execute(self):

        dist = [float("inf") for _ in range(self.n)]
        prev = [float("inf") for _ in range(self.n)]

        dist[self.s] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.s))
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest in range(self.n):
                cost_ = cost[src][dest]
                if dist[dest] > dist[src] + cost_:
                    dist[dest] = dist[src] + cost_
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src

        return dist

    def get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))

n = int(input())
cost = [[float('inf') for i in range(n)] for j in range(n)]

for _ in range(n-1):
    a, b, c = map(int, input().split())
    cost[a-1][b-1] = c
    cost[b-1][a-1] = c

q, k = map(int, input().split())

d = Dijkstra(k-1,n,n-1,cost).execute()


ans = [0]*q

for i in range(q):
    x, y = map(int, input().split())
    ans[i] = d[x-1]+d[y-1]

print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : uからvのコスト(存在しないときは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):
            if d[j] > d[v]+cost[v][j]: # vを使った場合と使わない場合の最短値で比較
                d[j] = d[v]+cost[v][j]

    return d

n = int(input())
cost = [[float('inf') for i in range(n)] for j in range(n)]

for _ in range(n-1):
    a, b, c = map(int, input().split())
    cost[a-1][b-1] = c
    cost[b-1][a-1] = c

q, k = map(int, input().split())

d = dijkstra(k-1,n,n-1,cost)

ans = [0]*q

for i in range(q):
    x, y = map(int, input().split())
    ans[i] = d[x-1]+d[y-1]

print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n= int(input())
tab = [[0 for _ in range(n)] for _ in range(n)]
branchdict = {}
for i in range(n-1):
    a,b,c= map(int,input().split())
    tab[a-1][b-1] = c
    tab[b-1][a-1] = c
    branchdict[a-1] = branchdict.get(a-1,[]) + [b-1]
    branchdict[b-1] = branchdict.get(b-1,[]) + [a-1]
q,k= map(int,input().split())
start = k-1
que = deque()
que.append(start)
passed = set()
passed.add(start)
cost = [0] * n
while len(que)!=0:
    node = que.pop()
    for abr in branchdict[node]:
        if not abr in passed:
            cost[abr] = cost[node] + tab[node][abr]
            passed.add(abr)
            que.append(abr)
for i in range(q):
    x,y= map(int,input().split())
    print(cost[x-1]+cost[y-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import heapq
N=int(input())
numbers=[[] for _ in range(N)]
for _ in range(N-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    numbers[a].append((b,c))
    numbers[b].append((a,c))
Q,K=map(int,input().split())
K-=1
keika=[]
for _ in range(Q):
    x,y=map(int,input().split())
    keika.append([x-1,y-1])
inf=pow(10,10)
visited=[inf for _ in range(N)]
visited[K]=0
stack=[K]
heapq.heapify(stack)
while len(stack)>0:
    n=heapq.heappop(stack)
    for s,t in numbers[n]:
        if visited[s]==inf:
            heapq.heappush(stack,s)
            visited[s]=min(visited[s],visited[n]+t)
for z in keika:
    print(visited[z[0]]+visited[z[1]])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N=int(input())
numbers=[[] for _ in range(N)]
for _ in range(N-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    numbers[a].append((b,c))
    numbers[b].append((a,c))
Q,K=map(int,input().split())
K-=1
keika=[]
for _ in range(Q):
    x,y=map(int,input().split())
    keika.append([x-1,y-1])
inf=pow(10,10)
visited=[inf for _ in range(N)]
visited[K]=0
stack=deque([K])
while len(stack)>0:
    n=stack.pop()
    for s,t in numbers[n]:
        if visited[s]==inf:
            stack.appendleft(s)
            visited[s]=min(visited[s],visited[n]+t)
for z in keika:
    print(visited[z[0]]+visited[z[1]])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N=int(input())
numbers=[[] for _ in range(N)]
for _ in range(N-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    numbers[a].append((b,c))
    numbers[b].append((a,c))
Q,K=map(int,input().split())
K-=1
keika=[]
for _ in range(Q):
    x,y=map(int,input().split())
    keika.append([x-1,y-1])
inf=pow(10,10)
visited=[inf for _ in range(N)]
visited[K]=0
stack=deque([K])
while len(stack)>0:
    n=stack.pop()
    for s,t in numbers[n]:
        if visited[s]==inf:
            stack.appendleft(s)
        visited[s]=min(visited[s],visited[n]+t)
for z in keika:
    print(visited[z[0]]+visited[z[1]])

Submission status: Time Limit Exceeded

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

N = int(input())
T, D = {i: [] for i in range(N)}, [-1] * N
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    T[a - 1].append((b - 1, c))
    T[b - 1].append((a - 1, c))


def dfs(p, c, d):
    D[c] = d
    for c2, d2 in T[c]:
        if c2 != p:
            dfs(c, c2, d + d2)


Q, K = map(int, input().split())
dfs(-1, K - 1, 0)
for _ in range(Q):
    x, y = map(int, input().split())
    print(D[x - 1] + D[y - 1])

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    from heapq import heappush, heappop

    # 長点数V、直接移動先とコストを記したリストg、スタート地点rをとって、
    # rからiに行くまでの最低コストがdist[i]であることを意味するリストdistを返す関数
    def dijkstra(V, g, r):

        dist = [INF] * V
        queue = [(0, r)]  # queueの要素(c,v)は、コストcで直接vに行けることを意味する
        dist[r] = 0  # スタート地点rにはコスト0で行ける

        while queue:
            c, v = heappop(queue)
            if dist[v] < c:  # すでに記録されているコストの方が小さいので更新不要
                continue
            for cost, t in g[v]:
                if dist[v] + cost < dist[t]:
                    dist[t] = dist[v] + cost
                    heappush(queue, (dist[t], t))

        return dist

    N=int(input())
    V, E= N,N-1
    g = [[] for i in range(V)]

    for i in range(E):
        s, t, d = map(int, input().split())
        s,t,d=s-1,t-1,d
        g[s].append((d, t))
        g[t].append((d, s))# g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する

    INF = 10 ** 20

    Q,K=map(int,input().split())
    l1=[INF]*V
    l2=[INF]*V
    for i in range(V):
        l1[i]=dijkstra(V, g, i)[K - 1]
        l2[i] = dijkstra(V, g, K-1)[i]

    for j in range(Q):
        x,y=map(int,input().split())
        print(l1[x-1]+l2[y-1])


resolve()

Submission status: Time Limit Exceeded

Solution code:
# import bisect
# from collections import Counter, deque
# from copy import copy, deepcopy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

def resolve():
    from heapq import heappush, heappop

    # 長点数V、直接移動先とコストを記したリストg、スタート地点rをとって、
    # rからiに行くまでの最低コストがdist[i]であることを意味するリストdistを返す関数
    def dijkstra(V, g, r):

        dist = [INF] * V
        queue = [(0, r)]  # queueの要素(c,v)は、コストcで直接vに行けることを意味する
        dist[r] = 0  # スタート地点rにはコスト0で行ける

        while queue:
            c, v = heappop(queue)
            if dist[v] < c:  # すでに記録されているコストの方が小さいので更新不要
                continue
            for cost, t in g[v]:
                if dist[v] + cost < dist[t]:
                    dist[t] = dist[v] + cost
                    heappush(queue, (dist[t], t))

        return dist

    N=int(input())
    V, E= N,N-1
    g = [[] for i in range(V)]

    for i in range(E):
        s, t, d = map(int, input().split())
        s,t,d=s-1,t-1,d
        g[s].append((d, t))
        g[t].append((d, s))# g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する

    INF = 10 ** 20

    Q,K=map(int,input().split())
    for j in range(Q):
        x,y=map(int,input().split())
        print(dijkstra(V,g,x-1)[K-1]+dijkstra(V,g,K-1)[y-1])



resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
INF = 10**5
n = int(input())

graph = [[] for _ in range(n+1)]
d = [[INF]*(n+1) for _ in range(n+1)]

for _ in range(n-1):
    a, b, c = map(int, input().split())
    d[a][b] = d[b][a] = c
    graph[a].append(b)
    graph[b].append(a)

q, k = map(int, input().split())
dist = [INF]*(n+1)


def dfs(v1, parent, add):
    dist[v1] = add
    for v2 in graph[v1]:
        if v2 == parent:
            continue
        dfs(v2, v1, add + d[v1][v2])

dfs(k, -1, 0)

for _ in range(q):
    x, y = map(int, input().split())
    print(dist[x]+dist[y])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n = int(input())
tree = dict()
graph = defaultdict(list)

for i in range(n-1):
    a,b,c = (int(x) for x in input().split())
    tree[a,b] = c
    tree[b,a] = c
    graph[a].append(b)
    graph[b].append(a)

q, k = (int(x) for x in input().split())

dist = dict()
stack = [k,]
visited = [False for _ in range(n+1)]
dist[k] = 0
visited[k] = True
while stack:
    new_stack = []
    for node in stack:
        for next_node in graph[node]:
            if not visited[next_node]:
                visited[next_node]  = True
                dist[next_node] = dist[node] + tree[node, next_node]
                new_stack.extend(graph[node])
    stack = new_stack
for _ in range(q):
    x, y = (int(x) for x in input().split())
    print(dist[x] + dist[y])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n = int(input())
tree = dict()
graph = defaultdict(list)

for i in range(n-1):
    a,b,c = (int(x) for x in input().split())
    tree[a,b] = c
    tree[b,a] = c
    graph[a].append(b)
    graph[b].append(a)

q, k = (int(x) for x in input().split())

dist = dict()
stack = [k,]
visited = set()
dist[k] = 0
visited.add(k)
while stack:
    new_stack = []
    for node in stack:
        for next_node in graph[node]:
            if next_node not in visited:
                visited.add(next_node)
                dist[next_node] = dist[node] + tree[node, next_node]
                new_stack.extend(graph[node])
    stack = new_stack
for _ in range(q):
    x, y = (int(x) for x in input().split())
    print(dist[x] + dist[y])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
G=[[] for _ in range(N)]
for i in range(N-1):
  x,y,d=map(int,input().split())
  x-=1
  y-=1
  G[x].append((y,d))
  G[y].append((x,d))
Q,K=map(int,input().split())
stack=[K-1]
seen=[]
dist=[float('inf')]*N
dist[K-1]=0
while stack:
  u=stack.pop()
  seen.append(u)
  for v,d in G[u]:
    if v not in seen:
      dist[v]=min(dist[v],dist[u]+d)
      stack.append(v)
for q in range(Q):
  x,y=map(int,input().split())
  print(dist[x-1]+dist[y-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys
N=int(input())
G=defaultdict(list)
for i in range(N-1):
  x,y,d=map(int,input().split())
  G[x].append((y,d))
  G[y].append((x,d))
Q,K=map(int,input().split())
stack=deque()
stack.append(K)
seen=[]
dist=[float('inf')]*N
dist[K-1]=0
while stack:
  u=stack.pop()
  seen.append(u)
  for v,d in G[u]:
    if v not in seen:
      dist[v-1]=min(dist[v-1],dist[u-1]+d)
      stack.append(v)
for q in range(Q):
  x,y=map(int,input().split())
  print(dist[x-1]+dist[y-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)
def dfs(cur,par,d):
    dist[cur]=d
    for nx,nx_dist in G[cur]:
        if nx==par:continue
        dfs(nx,cur,d+nx_dist)

n=int(input())
G=[[] for i in range(n)]
dist=[0]*n
for i in range(n-1):
    a,b,c=map(int,input().split())
    G[a-1].append([b-1,c])
    G[b-1].append([a-1,c])
q,k=map(int,input().split())
k-=1
dfs(k,-1,0)
for i in range(q):
    x,y=map(int,input().split())
    x-=1
    y-=1
    print(dist[x]+dist[y])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

edges = {}

for _ in range(N-1):
    a, b, c = map(int, input().split())

    edges[(a, b)] = c
    edges[(b, a)] = c

Q, K = map(int, input().split())
xy = []
for _ in range(Q):
    xy.append(tuple(map(int, input().split())))


d = [10**14] * (N+1)
d[K] = 0

for n in range(N):
    for e in edges:
        if d[e[0]] > d[e[1]] + edges[e]:
            d[e[0]] = d[e[1]] + edges[e]


for x, y in xy:
    print(d[x] + d[y])

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(start, matrix, n):
    d = [float("inf")] * n
    fixed = [False] * n
    fixed[start] = True
    d[start] = 0
    now = start

    while True:
        rep = -1
        dist = float("inf")
        for i in range(n):
            if not fixed[i]:
                if (0 <= matrix[now][i]):
                    d[i] = d[now] + matrix[now][i]
                if d[i] < dist:
                    rep = i
                    dist = d[i]
        if rep == -1:
            break
        fixed[rep] = True
        now = rep
        for i in range(n):
            if (0 <= matrix[now][i]):
                cost = d[now] + matrix[now][i]
                if (0 <= cost < d[i]):
                    d[i] = cost
    return d


n = int(input().strip())
matrix = [[-1] * n for _ in range(n)]
for i in range(n - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    matrix[a][b] = c
    matrix[b][a] = c
q, k = map(int, input().split())
k -= 1
queries = [tuple(map(int, input().split())) for _ in range(q)]
from_k = dijkstra(k, matrix, n)
for query in queries:
    start = query[0] - 1
    goal = query[1] - 1
    print(from_k[start] + from_k[goal])

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(start, matrix, n):
    d = [float("inf")] * n
    fixed = [False] * n
    fixed[start] = True
    d[start] = 0
    now = start

    while True:
        rep = -1
        dist = float("inf")
        for i in range(n):
            if not fixed[i]:
                if (0 <= matrix[now][i]):
                    d[i] = d[now] + matrix[now][i]
                if d[i] < dist:
                    rep = i
                    dist = d[i]
        if rep == -1:
            break
        fixed[rep] = True
        now = rep
        for i in range(n):
            if (0 <= matrix[now][i]):
                cost = d[now] + matrix[now][i]
                if (0 <= cost < d[i]):
                    d[i] = cost
    return d


n = int(input().strip())
matrix = [[-1] * n for _ in range(n)]
for i in range(n - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    matrix[a][b] = c
    matrix[b][a] = c
q, k = map(int, input().split())
k -= 1
queries = [tuple(map(int, input().split())) for _ in range(q)]
from_k = dijkstra(k, matrix, n)
for query in queries:
    start = query[0] - 1
    goal = query[1] - 1
    print(dijkstra(start, matrix, n)[k] + from_k[goal])

Submission status: Time Limit Exceeded

Solution code:
### bfs ###
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
N = int(input())
G = [[] for _ in range(N)]
dis = [-1]*N
que = []
for _ in range(N-1):
    a, b, c = map(int, input( ).split( ))
    a -= 1
    b -= 1
    G[a].append([b,c])
    G[b].append([a,c])
Q, K = map(int, input().split())
K -= 1
dis[K] = 0
que.append(K) #dfs
while que:
    p = que.pop(0)
    for i in range(len(G[p])):
        n_p, d = G[p][i]
        if dis[n_p] != -1:
            continue
        que.append(n_p)
        dis[n_p] = dis[p] + d

for i in range(Q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    ans = dis[x]+dis[y]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
## bfs ##
N = int(input())
G = [[] for _ in range(N)]
dis = [-1]*N
que = []
for _ in range(N-1):
    a, b, c = map(int, input( ).split( ))
    a -= 1
    b -= 1
    G[a].append([b,c])
    G[b].append([a,c])
Q, K = map(int, input().split())
K -= 1
dis[K] = 0
que.append(K) 
while que:
    p = que.pop(0)
    for i in range(len(G[p])):
        n_p, d = G[p][i]
        if dis[n_p] != -1:
            continue
        que.append(n_p)
        dis[n_p] = dis[p] + d

for i in range(Q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    ans = dis[x]+dis[y]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())

nodes = [set() for i in range(n+1)]
dis = [dict() for i in range(n+1)]
ans = [-1 for i in range(n+1)]

for _ in range(n-1):
    a,b,c = map(int,input().split())
    nodes[a].add(b)
    nodes[b].add(a)
    dis[a][b] = c
    dis[b][a] = c

#print(nodes)
#print(dis)

Q,K = map(int,input().split())

q = [K]
d = 0
ans[K] = 0
c = 0
while True:
    now = q[-1]
    nex = -1
    for x in nodes[now]:
        if ans[x] == -1:
            nex = x
            break
    if nex == -1:
        if c >= n-1:
            break
        else:
            q.pop()
            d -= dis[now][q[-1]]

    else:
        nodes[now].remove(nex)
        nodes[nex].remove(now)
        d += dis[now][nex]
        q.append(nex)
        ans[nex] = d
        c += 1

#print(ans)

for _ in range(Q):
    x,y = map(int,input().split())
    print(ans[x] + ans[y])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())

nodes = [set() for i in range(n+1)]
dis = [dict() for i in range(n+1)]
ans = [-1 for i in range(n+1)]

for _ in range(n-1):
    a,b,c = map(int,input().split())
    nodes[a].add(b)
    nodes[b].add(a)
    dis[a][b] = c
    dis[b][a] = c

#print(nodes)
#print(dis)

Q,K = map(int,input().split())

q = [K]
d = 0
ans[K] = 0
c = 0
while True:
    now = q[-1]
    nex = -1
    for x in nodes[now]:
        if ans[x] == -1:
            nex = x
            break
    if nex == -1:
        if c >= n-1:
            break
        else:
            q.remove(now)
            d -= dis[now][q[-1]]

    else:
        nodes[now].remove(nex)
        nodes[nex].remove(now)
        d += dis[now][nex]
        q.append(nex)
        ans[nex] = d
        c += 1

#print(ans)

for _ in range(Q):
    x,y = map(int,input().split())
    print(ans[x] + ans[y])

Submission status: Time Limit Exceeded

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

def dfs(v, u, k):
    for i in d[v]:
        if i[0] == u:
            continue
        dnp[i[0]] = k + i[1]
        dfs(i[0], v, k + i[1])

N = int(input())
d = [[] for _ in range(N)]
for i in range(N - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a].append((b, c))
    d[b].append((a, c))
kkyori = [0] * N
dnp = np.array(kkyori)
Q, K = map(int, input().split())
dfs(K - 1, -1, 0)
for i in range(Q):
    x, y = map(int, input().split())
    print(dnp[x - 1] + dnp[y - 1])

Submission status: Time Limit Exceeded

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

def dfs(v, u, k):
    for i in d[v]:
        if i[0] == u:
            continue
        kkyori[i[0]] = k + i[1]
        dfs(i[0], v, k + i[1])

N = int(input())
d = [[] for _ in range(N)]
for i in range(N - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a].append((b, c))
    d[b].append((a, c))
kkyori = [0] * N

Q, K = map(int, input().split())
dfs(K - 1, -1, 0)
for i in range(Q):
    x, y = map(int, input().split())
    print(kkyori[x - 1] + kkyori[y - 1])

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

from heapq import heappop, heappush

def dijkstra(E, start):
    N_d = len(E)
    dist = [INF] * N_d
    dist[start] = 0
    q = [(0, start)]
    while q:
        dist_v, v = heappop(q)
        if dist[v] != dist_v:
            continue
        for u, dist_vu in E[v]:
            dist_u = dist_v + dist_vu
            if dist_u < dist[u]:
                dist[u] = dist_u
                heappush(q, (dist_u, u))
    return dist

N = INT()
abc = [LIST() for i in range(N-1)]
Q, K = MAP()
xy = [LIST() for i in range(Q)]

graph = defaultdict(list)

for a, b, c in abc:
    graph[a-1].append((b-1, c))
    graph[b-1].append((a-1, c))

    # graph[a-1].append((b-1, c))

# print(dijkstra(graph, 1))
for x, y in xy:
    # ans = dijkstra(graph, x-1)[K-1] + dijkstra(graph, K-1)[y-1]
    d = dijkstra(graph, K-1)
    ans = d[x-1] + d[y-1]
    # dijkstra(graph, x-1)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

###
N = INT()
A = []
B = []
C = []
for i in range(N-1):
    a, b, c = MAP()
    A.append(a-1)
    B.append(b-1)
    C.append(c)

Q, K = MAP()
K = K - 1
X = []
Y = []
for i in range(Q):
    x, y = MAP()
    X.append(x-1)
    Y.append(y-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

cost = [[float("inf") for i in range(N)] for i in range(N)]
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
W = N - 1
for a, b, c in zip(A, B, C):
    cost[a][b] = c
    cost[b][a] = c

for i in range(Q):
    ans = dijkstra(X[i], N, W, cost)[K] + dijkstra(K, N, W, cost)[Y[i]]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

from heapq import heappop, heappush

def dijkstra(E, start):
    N_d = len(E)
    dist = [INF] * N_d
    dist[start] = 0
    q = [(0, start)]
    while q:
        dist_v, v = heappop(q)
        if dist[v] != dist_v:
            continue
        for u, dist_vu in E[v]:
            dist_u = dist_v + dist_vu
            if dist_u < dist[u]:
                dist[u] = dist_u
                heappush(q, (dist_u, u))
    return dist

N = INT()
abc = [LIST() for i in range(N-1)]
Q, K = MAP()
xy = [LIST() for i in range(Q)]

graph = defaultdict(list)

for a, b, c in abc:
    graph[a-1].append((b-1, c))
    graph[b-1].append((a-1, c))

    # graph[a-1].append((b-1, c))

# print(dijkstra(graph, 1))
for x, y in xy:
    ans = dijkstra(graph, x-1)[K-1] + dijkstra(graph, K-1)[y-1]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

###
N = INT()
A = []
B = []
C = []
for i in range(N-1):
    a, b, c = MAP()
    A.append(a-1)
    B.append(b-1)
    C.append(c)

Q, K = MAP()
K = K - 1
X = []
Y = []
for i in range(Q):
    x, y = MAP()
    X.append(x-1)
    Y.append(y-1)
###

d = [[float("inf")] * N for _ in range(N)]
for a, b, c in zip(A, B, C):
    d[a][b] = c
    d[b][a] = c
for i in range(N):
    d[i][i] = 0

def warshall_floyd(d):
    # d[i][j]: iからjへの最短距離
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

w_d = warshall_floyd(d)

for i in range(Q):
    ans = w_d[X[i]][K] + w_d[K][Y[i]]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
n = int(input())
INF = 10**13
g = [[INF for __ in range(n)] for _ in range(n)]

for _ in range(n-1):
    a, b, c = map(int, input().split())
    g[a-1][b-1] = c
    g[b-1][a-1] = c


def dijkstra(s, n, edges):
    # edges[i][j] : the cost of i→j
    # import 'heap'
    d = [INF] * n
    d[s] = 0
    q = [(0, s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in enumerate(edges[u]):
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q, (d[v], v))
    return d


q, k = map(int, input().split())
d = dijkstra(k-1, n, g)

for _ in range(q):
    x, y = map(int, input().split())
    print(d[x-1]+d[y-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)

def main():
  n = int(input())
  tree = defaultdict(lambda : {'parent':-1, 'score':0, 'children':[]})
  weights = dict()
  for _ in range(n-1):
    a, b, c = map(int, input().split())
    tree[a]['children'].append(b)
    tree[b]['children'].append(a)
    weights[(a, b)] = weights[(b, a)] = c
    
  q, k = map(int, input().split())  
  visited = [False] * (n+1)
  iroot = k
  def dfs(inode, score=0):
    visited[inode] = True
    for ichild in tree[inode]['children']:
      if visited[ichild]:
        continue
      tree[ichild]['score'] = weights[(inode, ichild)] + score
      tree[ichild]['parent'] = inode
      dfs(ichild, tree[ichild]['score'])
  dfs(iroot)
  for _ in range(q):
    x, y = map(int, input().split())
    print(tree[x]['score'] + tree[y]['score'])

if __name__=='__main__':
  main()