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: Runtime Error

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline
n = int(input())
m = {}
np = [deque([]) for _ in range(n)]
for _ in range(n-1):
    a, b, c = [int(x) for x in input().strip().split()]
    m[(a, b)] = c
    m[(b, a)] = c
    np[a-1].append(b)
    np[b-1].append(a)

q, k = [int(x) for x in input().strip().split()]
master = [-1 for _ in range(n)]
master[k-1] = 0

def dfs(cur, pre, master):
    #print('cur = {}, pre = {}'.format(cur, pre))
    for p in np[cur-1]:
        if p == pre:
            continue
        master[p-1] = master[cur-1] + m[(cur, p)]
        dfs(p, cur, master)

dfs(k, -1, master)

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

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
m = {}
np = [deque([]) for _ in range(n)]
for _ in range(n-1):
    a, b, c = [int(x) for x in input().strip().split()]
    m[(a, b)] = c
    m[(b, a)] = c
    np[a-1].append(b)
    np[b-1].append(a)

q, k = [int(x) for x in input().strip().split()]
master = [-1 for _ in range(n)]
master[k-1] = 0

def dfs(cur, pre, master):
    #print('cur = {}, pre = {}'.format(cur, pre))
    for p in np[cur-1]:
        if p == pre:
            continue
        master[p-1] = master[cur-1] + m[(cur, p)]
        dfs(p, cur, master)

dfs(k, -1, master)

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

Submission status: Runtime Error

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

def search_unseen(fr,to,cost):  
  cost_from_k[to] += cost_from_k[fr] + cost
  for n_to,n_cost in es[to]:
    if cost_from_k[n_to] == 0 and k!=n_to:
      search_unseen(to, n_to, n_cost)

n = int(input())
es = {i:[] for i in range(n)}
for i in range(n-1):
  a,b,c = map(int,input().split())
  es[a-1].append((b-1,c))
  es[b-1].append((a-1,c))      
      
q,k = map(int,input().split())
xy = [list(map(int,input().split())) for _ in range(q)]
k -=1

cost_from_k = [0]*n      
search_unseen(k, k, 0)

for x,y in xy:
  print(cost_from_k[x-1] + cost_from_k[y-1])

Submission status: Runtime Error

Solution code:
INF = float('inf')

def search_unseen(fr,to,cost):  
  cost_from_k[to] += cost_from_k[fr]+cost
  for n_to,n_cost in es[to]:
    if cost_from_k[n_to] == 0 and k!=n_to:
      search_unseen(to,n_to,n_cost)

n = int(input())
es = {i:[] for i in range(n)}
for i in range(n-1):
  a,b,c = map(int,input().split())
  es[a-1].append((b-1,c))
  es[b-1].append((a-1,c))      
      
q,k = map(int,input().split())
xy = [list(map(int,input().split())) for _ in range(q)]
k -=1

cost_from_k = [0]*n      
search_unseen(k,k,0)

for x,y in xy:
  print(cost_from_k[x-1] + cost_from_k[y-1])

Submission status: Runtime Error

Solution code:
N=int(input())

R=[[] for i in range(N)]

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

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

def dfs(s,g,d):
    chk[s]=1
    for j,c in R[s]:
        if j==g:
            return d+c
        else:
            if chk[j]:
                continue
            else:
                temp=dfs(j,g,d+c)
                if temp!=None:
                    return temp
                else:continue

C=[0]*N
for i in range(N):
    if i==K-1:
        C[i]=0
    else:
        chk = [0] * N
        C[i]=dfs(K-1,i,0)

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

Submission status: Runtime Error

Solution code:
N=int(input())
Branch=[[] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  Branch[a-1].append([b-1,c])
  Branch[b-1].append([a-1,c])
Q,K=map(int,input().split())
DistK=[float("Inf") for i in range(N)]
flag = [0 for i in range(N)]

def dfs(s,dist,flag,Branch,DistK):
  DistK[s]=dist
  flag[s]=1
  
  for i in range(len(Branch[s])):
    if flag[Branch[s][i][0]]==0:
      dfs(Branch[s][i][0],dist+Branch[s][i][1],flag,Branch,DistK)
      
  return 1
dfs(K-1,0,flag,Branch,DistK)
for i in range(Q):
  x,y = map(int,input().split())
  print(DistK[x-1]+DistK[y-1])

Submission status: Runtime Error

Solution code:
N=int(input())
Branch=[[] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  Branch[a-1].append([b-1,c])
  Branch[b-1].append([a-1,c])
Q,K=map(int,input().split())
DistK=[float("Inf") for i in range(N)]
flag = [0 for i in range(N)]

def dfs(s,dist):
  DistK[s]=dist
  flag[s]=1
  
  for i in range(len(Branch[s])):
    if flag[Branch[s][i][0]]==0:
      dfs(Branch[s][i][0],dist+Branch[s][i][1])
dfs(K-1,0)
      
for i in range(Q):
  x,y = map(int,input().split())
  print(DistK[x-1]+DistK[y-1])

Submission status: Runtime Error

Solution code:
N=int(input())
Branch=[[] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  Branch[a-1].append([b-1,c])
  Branch[b-1].append([a-1,c])
Q,K=map(int,input().split())
DistK=[float("Inf") for i in range(N)]
flag = [0 for i in range(N)]

def dfs(s,dist):
  DistK[s]=dist
  flag[s]=1
  
  for branch in Branch[s]:
    if flag[branch[0]]==0:
      dfs(branch[0],dist+branch[1])
dfs(K-1,0)
      
for i in range(Q):
  x,y = map(int,input().split())
  print(DistK[x-1]+DistK[y-1])

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(100000)
N = int(input())
graph = [[] for _ in range(N+1)]
for i in range(1, N):
    tmpa, tmpb, tmpc = map(int, input().split())
    graph[tmpa].append((tmpb, tmpc))
    graph[tmpb].append((tmpa, tmpc))

Q, K = map(int, input().split())
question = [[] for _ in range(Q+1)]
for i in range(1, Q+1):
    question[i] = list(map(int, input().split()))

#print(graph)
#print(question)
seen = [False] * (N+1)
dist = [0] * (N+1)
#Kからdfs
def dfs(here, seen, kyori):
    seen[here] = True
    dist[here] = kyori
    #print(f"here:{here} kyori:{kyori}")
    for node in graph[here]:
        nextkyori = kyori
        if not seen[node[0]]:
            nextkyori += node[1]
            dfs(node[0], seen, nextkyori)

dfs(K, seen, 0)
for quest in question[1:]:
    print(dist[quest[0]] + dist[quest[1]])

Submission status: Runtime Error

Solution code:
from collections import deque
N = int(input())
graph = [[] for _ in range(N+1)]
for i in range(1, N):
    tmpa, tmpb, tmpc = map(int, input().split())
    graph[tmpa].append((tmpb, tmpc))
    graph[tmpb].append((tmpa, tmpc))

Q, K = map(int, input().split())
question = [[] for _ in range(Q+1)]
for i in range(1, Q+1):
    question[i] = list(map(int, input().split()))

#print(graph)
#print(question)
seen = [False] * (N+1)
dist = [0] * (N+1)
#Kからdfs
def dfs(here, seen, kyori):
    seen[here] = True
    dist[here] = kyori
    #print(f"here:{here} kyori:{kyori}")
    for node in graph[here]:
        nextkyori = kyori
        if not seen[node[0]]:
            nextkyori += node[1]
            dfs(node[0], seen, nextkyori)

dfs(K, seen, 0)
for quest in question[1:]:
    print(dist[quest[0]] + dist[quest[1]])

Submission status: Runtime Error

Solution code:
# disjoint setかと思いきやDFS
n = int(input())
graph = [[] for _ in range(n)]

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

q, k = map(int, input().split())
k = k - 1
# kからスタートしてぜんぶたどる
ans_list = [0 for _ in range(n)]


def dfs(node, used, weight):
    for data in graph[node]:
        if data[0] not in used:
            next_used = used[:]
            next_used.append(data[0])
            dfs(data[0], next_used, weight + data[1])
    ans_list[node] = weight


dfs(k, [k], 0)

for _ in range(q):
    a, b = map(lambda x: int(x) - 1, input().split())
    print(ans_list[a] + ans_list[b])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

N = int(sys.stdin.buffer.readline())

graph = [[]*N for _ in range(N)]

for _ in range(N-1):
    a, b, c = map(int, sys.stdin.buffer.readline().split())
    graph[a-1].append((b-1, c))
    graph[b-1].append((a-1, c))

Q, K = map(int, sys.stdin.buffer.readline().split())
dist_K = [-1]*N

def cal_dist_K(u = K-1, current_dist = 0):
    dist_K[u] = current_dist
    for v,c in graph[u]:
        if dist_K[v] == -1:
            cal_dist_K(v, current_dist + c)

cal_dist_K()

ans = []
for _ in range(Q):
    x, y = map(int, sys.stdin.buffer.readline().split())
    ans.append(int(dist_K[x-1] + dist_K[y-1]))

print("\n".join(map(str, ans)))

Submission status: Runtime Error

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

N = int(sys.stdin.buffer.readline())

graph = np.zeros((N,N))

for _ in range(N-1):
    a, b, c = map(int, sys.stdin.buffer.readline().split())
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

Q, K = map(int, sys.stdin.buffer.readline().split())
dist_K = np.array(dijkstra(graph, indices=K-1))

ans = np.zeros(Q)
for i in range(Q):
    x, y = map(int, sys.stdin.buffer.readline().split())
    ans[i] = dist_K[x-1] + dist_K[y-1]

for x in ans:
    print(int(x))

Submission status: Runtime Error

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

N = int(sys.stdin.buffer.readline())

graph = np.zeros((N,N))

for _ in range(N-1):
    a, b, c = map(int, sys.stdin.buffer.readline().split())
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

Q, K = map(int, sys.stdin.buffer.readline().split())
dist_K = dijkstra(graph, indices=K-1)

ans = np.zeros(Q, dtype = np.int64)
for i in range(Q):
    x, y = map(int, sys.stdin.buffer.readline().split())
    ans[i] = dist_K[x-1] + dist_K[y-1]

print("\n".join(map(str, ans)))

Submission status: Runtime Error

Solution code:
N = int(input())
edge = [[] for _ in range(N+1)]
for _ in range(N-1):
    a,b,c = map(int,input().split())
    edge[a].append((b,c))
    edge[b].append((a,c))
Q,K = map(int,input().split())
distance = [None] * (N+1)
def dfs(v1,d):
    distance[v1] = d
    for v2,dd in edge[v1]:
        if distance[v2] is not None:
            continue
        dfs(v2,d+dd)

dfs(K,0)

ans = [0] * Q
for i in range(Q):
    x,y = map(int,input().split())
    ans[i] = distance[x]+distance[y]
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
N = int(input())
edge = [[] for _ in range(N+1)]
for _ in range(N-1):
    a,b,c = map(int,input().split())
    edge[a].append((b,c))
    edge[b].append((a,c))
Q,K = map(int,input().split())
distance = [-1] * (N+1)
def dfs(v1,d):
    distance[v1] = d
    for v2,dd in edge[v1]:
        if distance[v2] is not -1:
            continue
        dfs(v2,d+dd)

dfs(K,0)

ans = [0] * Q
for i in range(Q):
    x,y = map(int,input().split())
    ans[i] = distance[x]+distance[y]
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
N = int(input())
edge = [[] for _ in range(N+1)]
for _ in range(N-1):
    a,b,c = map(int,input().split())
    edge[a].append((b,c))
    edge[b].append((a,c))
Q,K = map(int,input().split())
distance = [-1] * (N+1)
def dfs(v1,d):
    distance[v1] = d
    for v2,dd in edge[v1]:
        if distance[v2] is not -1:
            continue
        dfs(v2,d+dd)

dfs(K,0)
print(distance)
ans = [0] * Q
for i in range(Q):
    x,y = map(int,input().split())
    ans[i] = distance[x]+distance[y]
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
N = int(input())
edge = [[] for _ in range(N+1)]
for _ in range(N-1):
    a,b,c = map(int,input().split())
    edge[a].append((b,c))
    edge[b].append((a,c))
Q,K = map(int,input().split())
distance = [-1] * (N+1)
def dfs(v1,d):
    distance[v1] = d
    for v2,dd in edge[v1]:
        if distance[v2] != -1:
            continue
        else:
            dfs(v2,d+dd)

dfs(K,0)
ans = [0] * Q
for i in range(Q):
    x,y = map(int,input().split())
    ans[i] = distance[x]+distance[y]
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
N=int(input())
abc=[tuple(map(int,input().split())) for i in range(N-1)]
g=[set() for i in range(N)]
for a,b,c in abc:
  g[a-1].add((b-1,c))
  g[b-1].add((a-1,c))
memo=[0]*N
memo[K-1]=0
Q,K=map(int,input().split())
import collections
q=collections.deque([(K-1,0)])
while(q):
  x,w = q.popleft()
  for a,b in g[x]:
    if memo[a]==-1:
      memo[a]=w+b
      q.append((a,w+b))
  
for i in range(Q):
  x,y=map(int,input().split())
  print(memo[a-1]+memo[b-1])

Submission status: Runtime Error

Solution code:
n = int(input())
abc = [list(map(int, input().split())) for _ in range(n - 1)]
Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(Q)]

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

def main():
    cost = [[0] * n for _ in range(n)]

    for i in range(len(abc)):
        a = abc[i][0] - 1
        b = abc[i][1] - 1
        c = abc[i][2]
        cost[a][b] = c

    graph = csr_matrix(cost)
    dist_matrix = dijkstra(csgraph=graph, directed=False, indices=K-1, return_predecessors=False)

    for goal1, goal2 in xy:
        print(d[goal1 - 1] + d[goal2 - 1])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def dijkstra(n, edges, s):
    min_dist = [float('inf')] * n
    min_dist[s] = 0
    next_v = []
    heapq.heappush(next_v, (0, s))
    path = [-1] * n
    
    while True:
        if len(next_v) == 0: break
        d, v = heapq.heappop(next_v)
        
        for u, d in edges[v]:
            if min_dist[u] > min_dist[v] + d:
                min_dist[u] = min_dist[v] + d
                heapq.heappush(next_v, (min_dist[u], u))
                path[u] = v
                
    return min_dist, path

n = int(input())
edges = [[] for _ in range(n)]

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

dist = [None] * n
for i in range(n):
    dist[i], _ = dijkstra(n, edges, i)

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

Submission status: Runtime Error

Solution code:
n=int(input())

import numpy as np
dist=np.full((n,n),-1,dtype=int)
for i in range(n-1):
  dist[i][i]=0
  a,b,c=map(int,input().split())
  dist[a-1][b-1]=c
  dist[b-1][a-1]=c

Q,K=map(int,input().split())
distFromK=np.full(n,-1,dtype=int)

# start from K
stack=[]
stack.append([K-1,0,-1])
while stack:
  node=stack.pop()
  num=node[0]
  d=node[1]
  parent=node[2]
  if distFromK[num]==-1:
    distFromK[num]=d
  else:
    distFromK[num]=min(d,distFromK[num])
  targets=dist[num]
  for i in range(len(targets)):
    if i==parent or i==num:
      continue
    if targets[i]==-1:
      continue
    stack.append([i,targets[i]+d,num])
    
for i in range(Q):
  x,y=map(int,input().split())
  print(distFromK[x-1]+distFromK[y-1])

Submission status: Runtime Error

Solution code:
n=int(input())

import numpy as np
dist=np.full((n,n),-1,dtype=int)
for i in range(n-1):
  dist[i][i]=0
  a,b,c=map(int,input().split())
  dist[a-1][b-1]=c
  dist[b-1][a-1]=c

Q,K=map(int,input().split())
distFromK=np.full(n,-1,dtype=int)

# start from K
stack=[]
stack.append([K-1,0,-1])
while stack:
  node=stack.pop()
  num=node[0]
  d=node[1]
  parent=node[2]
  if distFromK[num]==-1:
    distFromK[num]=d
  else:
    distFromK[num]=np.minimum(d,distFromK[num])
  targets=dist[num]
  for i in range(len(targets)):
    if i==parent or i==num:
      continue
    if targets[i]==-1:
      continue
    stack.append([i,targets[i]+d,num])
    
for i in range(Q):
  x,y=map(int,input().split())
  print(distFromK[x-1]+distFromK[y-1])

Submission status: Runtime Error

Solution code:
n = int(input())
# 値の初期化
path = [None]*(n + 1)
adjacent_list = [[] for i in range(n+1)]

for i in range(n - 1):
    a, b, c = list(map(int, input().split()))
    adjacent_list[a].append([b, c])
    adjacent_list[b].append([a, c])
# ノード番号、そこまでの距離,検索済みの要素を受け取る。


def dfs(node_n, distance, finished):
    # 検索済みに追加
    finished.add(node_n)
    # そこまでの距離を代入。値の更新などは特にない（はず）
    path[node_n] = distance
    # 対象ノードに対する隣接リストをforで回す
    for i in adjacent_list[node_n]:
        next = i[0]
        if next not in finished:
            # 検索済みでなかった場合、そこまでのコストを追加し再帰
            dfs(next, distance + i[1], finished)


q, k = list(map(int, input().split()))
dfs(k, 0, set())
# 各クエリへの返答
for i in range(q):
    s, g = list(map(int, input().split()))
    if path[s] is not None and path[g] is not None:
        print(path[s] + path[g])

Submission status: Runtime Error

Solution code:
n = int(input())
#値の初期化
path = [None]*(n + 1)
adjacent_list = [[] for i in range(n+1)]

for i in range(n - 1):
    a, b, c = list(map(int,input().split()))
    adjacent_list[a].append([b,c])
    adjacent_list[b].append([a,c])
#ノード番号、そこまでの距離,検索済みの要素を受け取る。
def dfs(node_n ,distance,finished):
    #検索済みに追加
    finished.add(node_n)
    #そこまでの距離を代入。値の更新などは特にない（はず）
    path[node_n] = distance
    #対象ノードに対する隣接リストをforで回す
    for i in adjacent_list[node_n]:
        next = i[0]
        if next not in finished:
            #検索済みでなかった場合、そこまでのコストを追加し再帰
            dfs(next, distance + i[1],finished)

q,k = list(map(int, input().split()))
dfs(k, 0, set())
#各クエリへの返答
for i in range(q):
    s, g = list(map(int, input().split()))
    is path[s] is not None and path[g] is not None:
        print(path[s] + path[g])

Submission status: Runtime Error

Solution code:
n = int(input())
#値の初期化
path = [None]*(n + 1)
adjacent_list = [[] for i in range(n+1)]

for i in range(n - 1):
    a, b, c = list(map(int,input().split()))
    adjacent_list[a].append([b,c])
    adjacent_list[b].append([a,c])
#ノード番号、そこまでの距離,検索済みの要素を受け取る。
def dfs(node_n ,distance,finished):
    #検索済みに追加
    finished.add(node_n)
    #そこまでの距離を代入。値の更新などは特にない（はず）
    path[node_n] = distance
    #対象ノードに対する隣接リストをforで回す
    for i in adjacent_list[node_n]:
        next = i[0]
        if next not in finished:
            #検索済みでなかった場合、そこまでのコストを追加し再帰
            dfs(next, distance + i[1],finished)

q,k = list(map(int, input().split()))
dfs(k, 0, set())
#各クエリへの返答
for i in range(q):
    s, g = list(map(int, input().split()))
    print(path[s] + path[g])

Submission status: Runtime Error

Solution code:
n = int(input())
path = [None]*(n + 1)
adjacent_list = [[] for i in range(n+1)]
for i in range(n - 1):
    a, b, c = list(map(int,input().split()))
    adjacent_list[a].append([b,c])
    adjacent_list[b].append([a,c])
#ノード番号、そこまでの距離,検索済みの要素を受け取る。
def dfs(node_n ,distance,finished):
    finished.add(node_n)
    path[node_n] = distance
    for i in adjacent_list[node_n]:
        next = i[0]
        if next not in finished:
            dfs(next, distance + i[1],finished)
q,k = list(map(int, input().split()))
dfs(k,0,set())
for i in range(q):
    s, g = list(map(int, input().split()))
    print(path[s]+path[g])

Submission status: Runtime Error

Solution code:
import collections

graph = collections.defaultdict(list)

N = int(input())
for i in range(N-1):
    # print(i)
    a, b, c = map(int, input().split(' '))
    a -= 1
    b -= 1
    graph[a].append([b, c])
    graph[b].append([a, c])


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

dist = [-1 for _ in range(N)]
dist[K-1] = 0

def dfs(a):
    for b, c in graph[a]:
        if dist[b] == -1:
            dist[b] = dist[a] + c
            dfs(b)
dfs(K-1)
# print(dist)


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

Submission status: Runtime Error

Solution code:
fron collections import deque
n=int(input())
g=[[] for i in range(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())
qu=deque([[k-1,0]])
v=[0]*n
d=[0]*n
while len(qu)>0:
    s=qu.popleft()
    v[s[0]]=1
    for j in g[s[0]]:
        if not v[j[0]]:
            v[j[0]]=1
            d[j[0]]=s[1]+j[1]
            qu+=[[j[0],d[j[0]]]]
for i in range(q):
    x,y=map(int,input().split())
    print(d[x-1]+d[y-1])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
n=int(input())
visitedlist=[-1 for  i in range(n)]
kilist=[[] for i in range(n)]
anslist=[0 for i in range(n)]
searchedlist=[-1 for i in range(n)]
for i in range(n-1):
        a,b,c=map(int,input().split())
        kilist[a-1].append((b,c))
        kilist[b-1].append((a,c))
def search(i):
        searchedlist[i-1]=1
        visitedlist[i-1]=1
        flag=0
        for j in kilist[i-1]:
            if visitedlist[j[0]-1]<0:
                visitedlist[j[0]-1]=1
                flag+=1
                anslist[j[0]-1]=anslist[i-1]+j[1]
        else:
            pass

        if flag>0:    
            for k in kilist[i-1]:
                if searchedlist[k[0]-1]==-1:
                    search(k[0])

q,k=map(int,input().split())
List=[0 for i in range(q)]
search(k)
for i in range(q):
    x,y=map(int,input().split())
    List[i]=anslist[x-1]+anslist[y-1]
for j in List:
    print(j)

Submission status: Runtime Error

Solution code:
import sys
from scipy.sparse.csgraph import dijkstra, csgraph_from_dense, shortest_path
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N = int(readline())
INF = float('inf')
graph = [[INF] * (N + 1) for _ in range(N + 1)]
for i in range(N + 1):
    graph[i][i] = 0

for _ in range(N - 1):
    a, b, c = map(int, readline().split())
    graph[a][b] = c
    graph[b][a] = c

Q, K = map(int, readline().split())
graph = csgraph_from_dense(graph, null_value=INF)
distance = shortest_path(graph, indices=K)

xy = map(int, read().split())
for x, y in zip(xy, xy):
    print(int(distance[x] + distance[y]))

Submission status: Runtime Error

Solution code:
import sys, scipy
import numpy as np
from scipy.sparse import csr_matrix, isspmatrix_csr, isspmatrix_csc, isspmatrix
from scipy.sparse.csgraph._shortest_path import shortest_path
n=int(input())

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

G=csr_matrix(g)

q,k=map(int,input().split())
k-=1
d=shortest_path(G, method="D", indices=k)

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

Submission status: Runtime Error

Solution code:
n=int(input())
g=[[] for i in range(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())
qu=[[k-1,0]]
v=[0]*n
d=[0]*n
while len(qu)>0:
    s0,s1=qu[0]
    qu=qu[1:]
    v[s0]=1
    for j in g[s0]:
        j0,j1=j
        if not v[j0]:
            v[j0]=1
            d[j0]=s[1]+j1
            qu+=[[j0,d[j0]]]
for i in range(q):
    x,y=map(int,input().split())
    print(d[x-1]+d[y-1])

Submission status: Runtime Error

Solution code:
n=int(input())
g=[[] for i in range(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())
qu=[[k-1,0]]
v=[0]*n
d=[0]*n
while len(qu)>0:
    s=qu.pop(0)
    v[s[0]]=1
    for j in g[s]:
        if not v[j[0]]:
            v[j[0]]=1
            d[j[0]]=s[1]+j[1]
            qu.append([j[0],d[j[0]]])
for i in range(q):
    x,y=map(int,input().split())
    print(d[x-1]+d[y-1])

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
 
 
class Dijk:
    def __init__(self, n):
        self.table = [[] for i in range(n+1)]
        self.n = n+1
 
    def add(self, x, y, f):
        self.table[x].append((y, f))
 
    def di(self, s):
        inf = float('inf')
        self.val = [inf] * self.n
        self.val[s] = 0
        h = []
        heappush(h, (0, s))
        while h:
            q, i = heappop(h)
            if self.val[i] < q:
                continue
            for x, c in self.table[i]:
                if self.val[x] > self.val[i] + c:
                    self.val[x] = self.val[i] + c
                    heappush(h, (self.val[x], x))
 
    def dist(self, s, t):
        return self.val[t]

n= int(input())
dijk=Dijk(n)

for i in range(n-1):
    a,b,c=map(int,input().split())
    dijk.add(a,b,c)
    dijk.add(b,a,c)
q,k=map(int,input().split())
for i in range(q):
    x,y=map(int,input().split())
    dijk.di(x)
    ans=dijk.dist(x,i+1)
    dijk.di(i+1)
    ans+=dijk.dist(i+1,y)
    print(ans)

Submission status: Runtime Error

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

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

dist = [0] * N

def dfs(v, pv, dis):
    for i in to[v]:
        if i[0] != pv:
            dfs(i[0], v, dis+i[1])
    dist[v] = dis

dfs(K-1, -1, 0)

for q in xy:
    print(dist[q[0]-1] + dist[q[1]-1])

Submission status: Runtime Error

Solution code:
def dfs(v,d):
    memo[v] = d
    for i in graph[v]:
        if memo[i[0]] != -1:continue
        dfs(i[0],d+i[1])

n = int(input())
graph = [[] for _ in range(n)]
memo = [-1]*n
for i in range(n-1):
    x,y,z = map(int,input().split())
    graph[x-1].append([y-1,z])
    graph[y-1].append([x-1,z])
q,k = map(int,input().split())
ary = [list(map(int,input().split())) for _ in range(q)]
dfs(k-1,0)
for x,y in ary:
    print(memo[x-1]+memo[y-1])

Submission status: Runtime Error

Solution code:
def dfs(prev, now, fromK, t, d):
  d[now] = fromK
  for nl in (t[now]):
    if nl[0] != prev:
      dfs(now, nl[0], fromK+nl[1], t, d)

N = int(input())
T  = [[] for _ in range(N+1)]
for _ in range(N-1):
  a, b, l = map(int, input().split())
  T[a].append([b,l])
  T[b].append([a, l])
Q, K = map(int, input().split())
D = [0] * (N+1)
dfs(-1, K, 0, T, D)
for _ in range(Q):
  x, y = map(int, input().split())
  print(D[x]+D[y])

Submission status: Runtime Error

Solution code:
def dfs(v,d,p):
    memo[v] = d
    flag = False
    for i in graph[v]:
        if memo[i[0]] != -1:continue
        dfs(i[0],d+i[1],v)
    sub_tree[v].append(v)
    for j in graph[v]:
        if j[0] == p:continue
        sub_tree[v] += sub_tree[j[0]]
    if p == k-1:arr.append(sub_tree[v])
n = int(input())
graph = [[] for _ in range(n)]
memo = [-1]*n

for i in range(n-1):
    x,y,z = map(int,input().split())
    graph[x-1].append([y-1,z])
    graph[y-1].append([x-1,z])
q,k = map(int,input().split())
sub_tree = [[] for _ in range(n)]
arr = []
ary = [list(map(int,input().split())) for _ in range(q)]
dfs(k-1,0,0)
arr.pop()
a = [0,0]
for i in range(q):
    for j in range(len(arr)):
        if ary[i][0] in arr[j]:
            a[0] = j
        if ary[i][1] in arr[j]:
            a[1] = j
    if a[0] == a[1]:
        print(memo[ary[i][0]-1]+memo[ary[i][1]-1])
    else:
        print(memo[ary[i][0]-1]+memo[ary[i][1]-1])

Submission status: Runtime Error

Solution code:
#%%
n = int(input())
a, b, c = [0] * n, [0] * n, [0] * n
for i in range(n-1):
    a[i], b[i], c[i] = map(int, input().split())

q, k = map(int, input().split())
x, y = [0] * q, [0] * q
for i in range(q):
    x[i], y[i] = map(int, input().split())

l = [[] for _ in range(n+1)]
for i in range(n-1):
    l[a[i]].append((b[i],c[i]))
    l[b[i]].append((a[i],c[i]))

d = [0] * (n+1)
check = False * (n+1)
check[k] = True
que = [k]

while len(que) > 0:
    tmp = que.pop(0)
    for i in l[tmp]:
        if check[i[0]] :
            que.append(i[0])
            check[i[0]] = True
            d[i[0]] = d[tmp] + i[1]
        else:
            pass

for i in range(q):
    ans = d[x[i]] + d[y[i]]
    print(ans)

Submission status: Runtime Error

Solution code:
#%%
n = int(input())
a, b, c = [0] * n, [0] * n, [0] * n
for i in range(n-1):
    a[i], b[i], c[i] = map(int, input().split())

q, k = map(int, input().split())
x, y = [0] * q, [0] * q
for i in range(q):
    x[i], y[i] = map(int, input().split())

l = [[] for _ in range(n+1)]
for i in range(n-1):
    l[a[i]].append((b[i],c[i]))
    l[b[i]].append((a[i],c[i]))

d = [0] * (n+1)
check = False * (n+1)
check[k] = 1
que = [k]

while len(que) > 0:
    tmp = que.pop(0)
    for i in l[tmp]:
        if check[i[0]] :
            que.append(i[0])
            check[i[0]] = True
            d[i[0]] = d[tmp] + i[1]
        else:
            pass

for i in range(q):
    ans = d[x[i]] + d[y[i]]
    print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
graph = [list() for i in range(n+1)]

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

len_list = [float("inf")] * (n + 1)
q, k = map(int, input().split())

def dfs(pre, now, c):
    len_list[now] = min(len_list[now], len_list[pre] + c)

    while graph[now]:
        n, c = graph[now].pop()
        dfs(now, n, c)

len_list[k] = 0
dfs(k, k, 0)

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

Submission status: Runtime Error

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

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = [[v, T[K][v], K] for v in T[K].keys()]

for _ in range(Q):
    x, y = map(int, input().split())
    while len(queue) > 0 or (shortest_path[x] != 0 and shortest_path[y] != 0):
        v = queue.pop(0)
        shortest_path[v[0]] = v[1]
        queue += [[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]]
    print(shortest_path[x] + shortest_path[y])

Submission status: Runtime Error

Solution code:
import heapq
N = int(input())
node = [[] for _ in range(N)]
for _ in range(N-1):
  a,b,c = map(int,input().split())
  node[a-1].append([c,b-1])
  node[b-1].append([c,a-1])
Q,K = map(int,input().split())

flag = [True]*N
ques = [[0,K-1]]
D = [0]*N
while ques:
  d1,l1 = heapq.heappop(ques)
  if flag[l1]:
    flag[l1]=False
    D[l1] = d1
    for d2,l2 in node[l1]:
      if flag[l2]:
        heapq.heappush([d1+d2,l2])
for _ in range(Q):
  x,y = map(int,input().split())
  print(D[x-1]+D[y-1])