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:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from collections import defaultdict

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 = []
  iroot = k
  def dfs(inode, score=0):
    visited.append(inode)
    for ichild in tree[inode]['children']:
      if ichild in visited:
        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()

Submission status: Runtime Error

Solution code:
n = int(input())
G = [[] for _ in range(n)] 
for i 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])

vis = [False] * n
d = [-1] * n
def dfs(k, depth):
    vis[k] = True
    d[k] = depth
    for i in G[k]: # i: [to, cost]
        if not vis[i[0]]: dfs(i[0], depth + i[1])

q, k = map(int, input().split())
dfs(k - 1, 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:
N = int(input())
edges = [[] for _ in range(N)]
for _ in range(1, N):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    edges[a].append([b, c])
    edges[b].append([a, c])

Q, K = map(int, input().split())
K -= 1
dist = [10**9 + 1] * N
dist[K] = 0


def dfs(s, before=-1):
    for edge in edges[s]:
        to = edge[0]
        c = edge[1]
        if to != before:
            dist[to] = dist[s] + c
            dfs(to, s)


dfs(K)
X = []
Y = []
for _ in range(Q):
    x, y = map(int, input().split())
    X.append(x-1)
    Y.append(y-1)

for i in range(Q):
    print(dist[X[i]] + dist[Y[i]])

Submission status: Runtime Error

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

Q, K = map(int, input().split())
K -= 1
dist = [pow(10, 9) + 1] * N
dist[K] = 0


def dfs(s, before=-1):
    for edge in edges[s]:
        to = edge[0]
        c = edge[1]
        if to != before:
            dist[to] = dist[s] + c
            dfs(to, s)


dfs(K)
X = []
Y = []
for _ in range(Q):
    x, y = map(int, input().split())
    X.append(x-1)
    Y.append(y-1)

for i in range(Q):
    print(dist[X[i]] + dist[Y[i]])

Submission status: Runtime Error

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

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

dist = [pow(10, 9) + 1] * N
dist[K] = 0


def dfs(s, before=-1):
    for edge in edges[s]:
        to = edge[0]
        c = edge[1]
        if to != before:
            dist[to] = dist[s] + c
            dfs(to, s)


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

Submission status: Runtime Error

Solution code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int acs(const void *a, const void *b) { 
  return *(int*)a - *(int*)b;
} /* 1,2,3,4.. */
int des(const void *a, const void *b) {
  return *(int*)b - *(int*)a;
} /* 8,7,6,5.. */
int cmp_char(const void *a, const void *b) { 
  return *(char*)a - *(char*)b;
} /* a,b,c,d.. */
int cmp_str(const void *a, const void *b) {
  return strcmp(*(const char **)a, *(const char **)b);
} /* aaa,aab.. */
#define min(a,b) (a < b ? a : b)
#define max(a,b) (a > b ? a : b)
#define rep(i, l, r) for (int i = l; i < r; i++)
#define MAX 100001
#define MOD 1000000007
#define INF 1000000009
typedef long long int lli;

typedef struct list {
  int node;
  int dist;
  struct list *next;
} list;

list *graph[MAX];

void initGraph(void) {
  for (int i = 0; i < MAX; i++)
    graph[i] = NULL;
}

void addEdge(int node1, int node2, int dist)
{
  list *new1 = (list *)malloc(sizeof(list *));
  new1->node = node2;
  new1->dist = dist;
  new1->next = graph[node1];
  graph[node1] = new1;

  list *new2 = (list *)malloc(sizeof(list *));
  new2->node = node1;
  new2->dist = dist;
  new2->next = graph[node2];
  graph[node2] = new2;
}

// 頂点k(根)からの距離
int kyori[MAX];

void dfs(int n, int p) {
  list *c = graph[n];
  for ( ; c != NULL; c = c->next ) {
    int cn = c->node;
    if ( cn == p ) continue;
    kyori[cn] = kyori[n] + c->dist;
    dfs(cn, n);
  }
}

int main(void) {
  int n;
  scanf("%d", &n);
  initGraph();
  rep(i, 0, n-1) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    addEdge(a, b, c);
  }
  int q, k;
  scanf("%d %d", &q, &k);
  int x[MAX], y[MAX];
  rep(i, 0, q) scanf("%d %d", &x[i], &y[i]);

  // 頂点kが根
  kyori[k] = 0;
  dfs(k, 0);

  rep(i, 0, q) {
    printf("%d\n", kyori[x[i]] + kyori[y[i]]);
  }
  return 0;
}

Submission status: Runtime Error

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

depth = [0] * N

def dfs(v, p, d):
    depth[v] = d
    for e in edges[v]:
        if e[0] == p:
            continue
        dfs(e[0], v, d + e[1])


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(depth[x] + depth[y])

Submission status: Runtime Error

Solution code:
def rec(p, sum, prev):
  global dist
  global G
  if dist[p] != 0:
    return

  dist[p] = sum
  for g in G[p]:
    if g[0] == prev:
      continue
    rec(g[0], g[1]+sum, p)

N = int(input())
li = [list(map(int, input().split())) for n in range(N-1)]
Q, K = map(int, input().split())
Ques = [list(map(int, input().split())) for q in range(Q)]
dist = [0] * N

G = [[] for n in range(N)]

for i in li:
  G[i[0]-1].append([i[1]-1, i[2]])
  G[i[1]-1].append([i[0]-1, i[2]])

rec(K-1, 0, -1)

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

Submission status: Runtime Error

Solution code:
def rec(p, sum, prev):
  global dist
  global G

  dist[p] = sum
  for g in G[p]:
    if g[0] == prev:
      continue
    rec(g[0], g[1]+sum, p)

N = int(input())
li = [list(map(int, input().split())) for n in range(N-1)]
Q, K = map(int, input().split())
Ques = [list(map(int, input().split())) for q in range(Q)]
dist = [0] * N

G = [[] for n in range(N)]

for i in li:
  G[i[0]-1].append([i[1]-1, i[2]])
  G[i[1]-1].append([i[0]-1, i[2]])

rec(K-1, 0, -1)

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

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    edges=[[] for _ in range(n)]
    for i in range(n-1):
        a,b,c=map(int,input().split())
        a-=1
        b-=1
        edges[a].append([b,c])
        edges[b].append([a,c])
    q,k=map(int,input().split())
    k-=1
    
    dist=[10**9+1]*n
    dist[k]=0
    
    def dfs(s,before=-1):
       for edge in edges[s]:
           to=edge[0]
           c=edge[1]
           if to!=before:
               dist[to]=dist[s]+c
               dfs(to,s) 
              
    dfs(k)
    for i in range(q):
        x,y=map(int,input().split())
        x-=1
        y-=1
        print(dist[x]+dist[y])
if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
def dfs(num,cost):
    visited[num]=cost
    for item in way[num]:
        if visited[item[0]]==-1:
            dfs(item[0],cost+item[1])
    return
    
N=int(input())

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


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

Submission status: Runtime Error

Solution code:
from collections import defaultdict


def dfs(v, parent, d):
    depth[v] = d
    for to, cost in tree[v]:
        if to == parent:
            continue
        dfs(to, v, d + cost)


depth = defaultdict(int)
tree = defaultdict(list)
n = int(input())
for i in range(n-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].append((b, c))
    tree[b].append((a, 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(depth[x] + depth[y])

Submission status: Runtime Error

Solution code:
N = int(input())
Edges = [[] for i in range(N)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    a,b = a-1,b-1
    Edges[a].append((b,c))
    Edges[b].append((a,c))
D = [float('inf') for i in range(N)]
def dfs(v,p,d):
    D[v] = d
    for e1,e2 in Edges[v]:
        if e1 != p:
            dfs(e1,v,d+e2)
Q,K = map(int,input().split())
dfs(K-1,-1,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
from collections import deque
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline
N = int(input())
p = [deque([]) for _ in range(N)]

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

Q, K = [int(x) for x in input().strip().split()]

c = [-1] * N
f = [False] * N

def search(cp, cost):
    f[cp-1] = True
    for np, cos in p[cp-1]:
        if f[np-1]:
            continue
        c[np-1] = cost + cos
        f[np-1] = True
        search(np, cost + cos)

search(K, 0)
for q in range(Q):
    x, y = [int(x) for x in input().strip().split()]
    print(c[x-1]+c[y-1])

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
p = [deque([]) for _ in range(N)]

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

Q, K = [int(x) for x in input().strip().split()]

c = [-1] * N
f = [False] * N

def search(cp, cost):
    f[cp-1] = True
    for np, cos in p[cp-1]:
        if f[np-1]:
            continue
        c[np-1] = cost + cos
        f[np-1] = True
        search(np, cost + cos)

search(K, 0)
for q in range(Q):
    x, y = [int(x) for x in input().strip().split()]
    print(c[x-1]+c[y-1])

Submission status: Runtime Error

Solution code:
N = int(input())

# 頂点 -> 隣接している頂点と距離のリスト
V = [[] for _ in range(N)]
for _ in range(N - 1):
	a, b, c = map(int, input().split())
	V[a - 1].append([b - 1, c])
	V[b - 1].append([a - 1, c])
	
Q, K = map(int, input().split())

# クエリをリストに格納
query = []
for _ in range(Q):
	x, y = map(int, input().split())
	query.append([x - 1, y - 1])
	
	
# 頂点Kからの距離を求める
# 距離は-1で初期化
dist = [-1 for _ in range(N)]
def dfs(v, d):
	dist[v] = d
	for adj in V[v]:
		adj_v, adj_d = adj
		if dist[adj_v] != -1: continue # 木だから訪問している=最短距離導出済み
		dist[adj_v] = d + adj_d
		dfs(adj_v, d + adj_d)

dfs(K - 1, 0)

# 完成！

for i in range(Q):
	print(dist[query[i][0]] + dist[query[i][1]])

Submission status: Runtime Error

Solution code:
N = int(input())

# 頂点 -> 隣接している頂点と距離のリスト
V = [[] for _ in range(N)]
for _ in range(N - 1):
	a, b, c = map(int, input().split())
	V[a - 1].append([b - 1, c])
	V[b - 1].append([a - 1, c])
	
Q, K = map(int, input().split())

query = []
for _ in range(Q):
	x, y = map(int, input().split())
	query.append([x - 1, y - 1])
	
# 頂点Kからの距離を求める
# 距離は-1で初期化
dist = [-1 for _ in range(N)]
def dfs(v, d):
	dist[v] = d
	for adj in V[v]:
		adj_v, adj_d = adj
		if dist[adj_v] != -1: continue
		dist[adj_v] = d + adj_d
		dfs(adj_v, d + adj_d)

dfs(K - 1, 0)

# 完成！

for i in range(Q):
	print(dist[query[i][0]] + dist[query[i][1]])

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

d = []
ABC = []


sys.setrecursionlimit(10 ** 5 + 1)
def solve(i, dis):
    global d
    global ABC
    d[i] = dis

    for n, c in ABC[i]:
        if d[n] == -1:
            solve(n, dis + c)


def main():
    N = int(input())
    global ABC
    ABC = [[] for _ in range(N + 1)]
    global d
    d = [-1] * (N + 2)
    for _ in range(N - 1):
        a, b, c = [int(x) for x in input().split()]
        ABC[a - 1].append([b - 1, c])
        ABC[b - 1].append([a - 1, c])

    Q, K = [int(x) for x in input().split()]

    solve(K - 1, 0)

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

d = []
ABC = []


def solve(i, dis):
    global d
    global ABC
    d[i] = dis

    for n, c in ABC[i]:
        if d[n] == -1:
            solve(n, dis + c)


def main():
    N = int(input())
    global ABC
    ABC = [[] for _ in range(N + 1)]
    global d
    d = [-1] * (N + 2)
    for _ in range(N - 1):
        a, b, c = [int(x) for x in input().split()]
        ABC[a - 1].append([b - 1, c])
        ABC[b - 1].append([a - 1, c])

    Q, K = [int(x) for x in input().split()]

    solve(K - 1, 0)

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

d = []
ABC = []


def solve(i, dis):
    global d
    global ABC
    d[i] = dis

    for n, c in ABC[i]:
        if d[n] == -1:
            solve(n, dis + c)


def main():
    N = int(input())
    global ABC
    ABC = [[] for j in range(N)]
    global d
    d = [-1] * N
    for _ in range(N - 1):
        a, b, c = [int(x) for x in input().split()]
        ABC[a - 1].append([b - 1, c])
        ABC[b - 1].append([a - 1, c])

    Q, K = [int(x) for x in input().split()]

    solve(K - 1, 0)

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

d = []
ABC = []

def solve(i, dis):
    global d
    global ABC
    d[i] = dis

    for n, c in ABC[i]:
        if d[n] == -1:
            solve(n, dis + c)



def main():
    N = int(input())
    global ABC
    ABC = [[] for j in range(N)]
    global d
    d = [-1] * N
    for _ in range(N - 1):
        a, b, c = [int(x) for x in input().split()]
        ABC[a - 1].append((b - 1, c))
        ABC[b - 1].append((a - 1, c))

    Q, K = [int(x) for x in input().split()]

    solve(K - 1, 0)

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, csgraph_from_dense

input = sys.stdin.readline


def main():
    N = int(input())
    edge = [[0] * N for j in range(N)]
    for _ in range(N - 1):
        a, b, c = [int(x) for x in input().split()]
        edge[a - 1][b - 1] = c
        edge[b - 1][a - 1] = c

    G = csgraph_from_dense(edge, null_value=0)
    d = shortest_path(G)

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

(Q, K) = map(int, input().split())
d = [-1] * (N+1)
d[K] = 0

def fill(i):
  for v in g[i]:
    if(d[v[0]] == -1):
      d[v[0]] = d[i] + v[1]
      fill(v[0])
  return
  
fill(K)

q = list()
for i in range(Q):
  q.append(input())
for i in range(Q):
  (x, y) = map(int, q[i].split())
  print(d[x] + d[y])

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

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


n = int(input())
lines = sys.stdin.readlines()
edges = [ [] for _ in range(n+1) ]
for i in range(n-1):
    e = tuple(map(int, lines[i].split(" ")))
    log(e)
    edges[e[0]].append((e[1],e[2]))
    edges[e[1]].append((e[0],e[2]))

q,k = map(int, lines[n-1].split(" "))

ddd = [0] * (n+1)


que = deque()
que.append(k)
def bfs(x):
    for y, d in edges[x]:
        if ddd[y]:
            continue
        ddd[y] = ddd[x] + d
        que.append(y)


while que:
    bfs(que.pop())

for i in range(n, n+q):
    x, y = map(int, lines[i].split(" "))
    log(x,y)
    print(ddd[x] + ddd[y])

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from scipy.sparse.csgraph import shortest_path
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
graph = np.zeros((N, N)) #0-indexed
for _ in range(N-1):
    a, b, c = lr()
    graph[a-1, b-1] = c

dist = shortest_path(graph, directed=False).astype(int)
Q, K = lr()
K_dist = dist[K-1].tolist()
for _ in range(Q):
    x, y = lr()
    print(K_dist[x-1] + K_dist[y-1])

# 20

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from scipy.sparse.csgraph import shortest_path
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
graph = np.zeros((N, N)) #0-indexed
for _ in range(N-1):
    a, b, c = lr()
    graph[a-1, b-1] = c

dist = shortest_path(graph, directed=False).astype(int)
Q, K = lr()
K_dist = dist[K-1]
for _ in range(Q):
    x, y = lr()
    print(K_dist[x-1] + K_dist[y-1])

# 20

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from scipy.sparse.csgraph import shortest_path
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
graph = np.zeros((N, N)) #0-indexed
for _ in range(N-1):
    a, b, c = lr()
    graph[a-1, b-1] = c

dist = shortest_path(graph, directed=False).astype(int)
Q, K = lr()
for _ in range(Q):
    x, y = lr()
    print(dist[x-1, K-1] + dist[K-1, y-1])

# 20

Submission status: Runtime Error

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
graph = np.zeros((N, N)) #0-indexed
for _ in range(N-1):
    a, b, c = lr()
    graph[a-1, b-1] = c

dist = shortest_path(graph, directed=False).astype(int)
Q, K = lr()
for _ in range(Q):
    x, y = lr()
    print(dist[x-1, K-1] + dist[K-1, y-1])

# 20

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n-1):
    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())
k -= 1
xy = []
for _ in range(q):
    x, y = map(int, input().split())
    x-=1
    y-=1
    xy.append((x, y))

def DFS(node, p_node, length):
    l[node] = length
    for i, j in graph[node]:
        if i==p_node:
            continue
        DFS(i, node, length+j)
sys.setrecursionlimit(2 * N)
l = [0]*n
DFS(k, -1, 0)
for x, y in xy:
    print(l[x]+l[y])

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n-1):
    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())
k -= 1
xy = []
for _ in range(q):
    x, y = map(int, input().split())
    x-=1
    y-=1
    xy.append((x, y))

def DFS(node, p_node, length):
    l[node] = length
    for i, j in graph[node]:
        if i==p_node:
            continue
        DFS(i, node, length+j)

l = [0]*n
DFS(k, -1, 0)
for x, y in xy:
    print(l[x]+l[y])

Submission status: Runtime Error

Solution code:
import sys
from heapq import heappush, heappop, heapify
input = sys.stdin.readline
    
def dfs(v, c, p=-1):
    dist[v] = c
    for u, d in g[v]:
        if u == p: continue
        dfs(u, c+d, v)

def main():    
    for i 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
    
    dfs(K, 0)
    
    for i in range(Q):
        x, y = map(int, input().split())
        print(dist[x-1]+dist[y-1])
    
if __name__ == '__main__':
    N = int(input())
    g = [[] for i in range(N)]
    dist = [0] * N
    main()

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
  a, b, c = map(int, input().split())
  graph[a].append((b, c))
  graph[b].append((a, c))
q, k = map(int, input().split())
xy = []
for _ in range(q):
  x, y = map(int, input().split())
  xy.append((x, y))

l = [0]*(n+1)
def DFS(node, p_node, length):
  l[node] = length
  for i, j in graph[node]:
    try:
      if i==p_node:
        continue
    except TypeError:
      sys.exit(0)
    DFS(i, node, length+j)

DFS(k, -1, 0)
for x, y in xy:
  print(l[x]+l[y])

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
  a, b, c = map(int, input().split())
  graph[a].append((b, c))
  graph[b].append((a, c))
q, k = map(int, input().split())
xy = []
for _ in range(q):
  x, y = map(int, input().split())
  xy.append((x, y))

l = [0]*(n+1)
def DFS(node, p_node, length):
  try:
    l[node] = length
  except:
    sys.exit(0)
  for i, j in graph[node]:
    if i==p_node:
      continue
    DFS(i, node, length+j)

DFS(k, -1, 0)
for x, y in xy:
  print(l[x]+l[y])

Submission status: Runtime Error

Solution code:
n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
  a, b, c = map(int, input().split())
  graph[a].append((b, c))
  graph[b].append((a, c))
q, k = map(int, input().split())
xy = []
for _ in range(q):
  x, y = map(int, input().split())
  xy.append((x, y))

l = [0]*(n+1)
def DFS(node, p_node, length):
  l[node] = length
  for i, j in graph[node]:
    if i==p_node:
      continue
    DFS(i, node, length+j)
DFS(k, -1, 0)
for x, y in xy:
  print(0)

Submission status: Runtime Error

Solution code:
n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
  a, b, c = map(int, input().split())
  graph[a].append((b, c))
  graph[b].append((a, c))
q, k = map(int, input().split())
xy = []
for _ in range(q):
  x, y = map(int, input().split())
  xy.append((x, y))

l = [0]*(n+1)
def DFS(node, p_node, length):
  l[node] = length
  for i, j in graph[node]:
    if i==p_node:
      continue
    DFS(i, node, length+j)
DFS(k, -1, 0)
for x, y in xy:
  print(l[x]+l[y])

Submission status: Runtime Error

Solution code:
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n-1):
  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())
k-=1
xy = []
for _ in range(q):
  x, y = map(int, input().split())
  xy.append((x-1, y-1))

l = [0]*(n+1)
def DFS(node, p_node, length):
  l[node] = length
  for i, j in graph[node]:
    if i==p_node:
      continue
    DFS(i, node, length+j)
DFS(k, -1, 0)
for x, y in xy:
  print(l[x]+l[y])

Submission status: Runtime Error

Solution code:
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n-1):
  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())
k-=1
xy = []
for _ in range(q):
  x, y = map(int, input().split())
  xy.append((x-1, y-1))

l = [0]*n
def DFS(node, p_node, length):
  l[node] = length
  for i, j in graph[node]:
    if i==p_node:
      continue
    DFS(i, node, length+j)
DFS(k, -1, 0)
for x, y in xy:
  print(l[x]+l[y])

Submission status: Runtime Error

Solution code:
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n-1):
  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())
xy = []
for _ in range(q):
  x, y = map(int, input().split())
  xy.append((x-1, y-1))

k-=1
seen = [False]*n
l = [0]*n
def DFS(node, length):
  l[node] = length
  seen[node] = True
  for i, j in graph[node]:
    if seen[i]:
      continue
    DFS(i, length+j)
DFS(k, 0)
for x, y in xy:
  print(l[x]+l[y])

Submission status: Runtime Error

Solution code:
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n-1):
  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())
k-=1
seen = [False]*n
l = [0]*n
def DFS(node, length):
  l[node] = length
  seen[node] = True
  for i, j in graph[node]:
    if seen[i]:
      continue
    DFS(i, length+j)

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

Submission status: Runtime Error

Solution code:
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n-1):
  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())
k-=1
seen = [False]*n
l = [0]*n
def DFS(node, length):
  seen[node] = True
  for i, j in graph[node]:
    if seen[i]:
      continue
    l[i] = length+j
    DFS(i, length+j)

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

Submission status: Runtime Error

Solution code:
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n-1):
  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())
k-=1
seen = [False]*n
l = [0]*n
seen[k] = True
def DFS(node, length):
  for i, j in graph[node]:
    if seen[i]:
      continue
    l[i] = length+j
    seen[i] = True
    DFS(i, length+j)

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

Submission status: Runtime Error

Solution code:
N = int(input())
edge = [[] for i in range(N)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    edge[a-1].append((c, b-1))
    edge[b-1].append((c, a-1))
Q, K = map(int, input().split())
query = [tuple(map(int, input().split())) for _ in range(Q)]

import heapq

def dijkstra_heap(s):
    d = [10**12] * N
    used = [False] * N
    d[s] = 0
    used[s] = True
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist, e)
    while len(edgelist):
        min_edge = heapq.heappop(edgelist)
        if used[min_edge[1]]:
            continue
        v = min_edge[1]
        d[v] = min_edge[0]
        used[v] = True
        for e in edge[v]:
            heapq.heappush(edgelist, [e[0] + d[v], e[1]])
    return d

dist = dijkstra_heap(K-1)
for q in query:
    x, y = q[0], q[1]
    x -= 1
    y -= 1
    print(dist[x] + dist[y])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

def dfs(v,d):
    k_shortest[v] = d
    visit[v] = 1
    for i,j in tree[v]:
        if not visit[i]:
            dfs(i,d+j)

N=int(input())
tree=[[] for i in range(N+1)]
visit = [0]*(N+1)
k_shortest = [0]*(N+1)
for i in range(N-1):
    a,b,c=map(int,input().split(' '))
    tree[a].append((b,c))
    tree[b].append((a,c))
Q,K=map(int,input().split(' '))
dfs(K,0)
query = [list(map(int,input().split(' '))) for i in range(Q)]
for i,j in query:
    print(k_shortest[i]+k_shortest[j])

Submission status: Runtime Error

Solution code:
def dfs(v,d):
    k_shortest[v] = d
    visit[v] = 1
    for i,j in tree[v]:
        if not visit[i]:
            dfs(i,d+j)

N=int(input())
tree=[[] for i in range(N+1)]
visit = [0]*(N+1)
k_shortest = [0]*(N+1)
for i in range(N-1):
    a,b,c=map(int,input().split(' '))
    tree[a].append((b,c))
    tree[b].append((a,c))
Q,K=map(int,input().split(' '))
dfs(K,0)
query = [list(map(int,input().split(' '))) for i in range(Q)]
for i,j in query:
    print(k_shortest[i]+k_shortest[j])

Submission status: Runtime Error

Solution code:
import math

def dfs(v,d):
    k_shortest[v] = d
    visit[v] = 1
    for i,j in tree[v]:
        if not visit[i]:
            dfs(i,d+j)

N=int(input())
tree=[[] for i in range(N+1)]
visit = [0]*(N+1)
k_shortest = [math.inf]*(N+1)
for i in range(N-1):
    a,b,c=map(int,input().split(' '))
    tree[a].append((b,c))
    tree[b].append((a,c))
Q,K=map(int,input().split(' '))
dfs(K,0)
query = [list(map(int,input().split(' '))) for i in range(Q)]
for i,j in query:
    print(k_shortest[i]+k_shortest[j])

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
import math
N=int(input())
tree=[[math.inf]*N for i in range(N)]
for i in range(N-1):
    a,b,c=map(int,input().split(' '))
    tree[a-1][b-1] = c
    tree[b-1][a-1] = c
tree = np.array(tree)
Q,K=map(int,input().split(' '))
csr = csr_matrix(tree)
ans = shortest_path(csr,indices=K-1)
for i in range(Q):
    s,e=map(int,input().split(' '))
    print(int(ans[s-1]+ans[e-1]))