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:
N = int(input())
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
    ai, bi, ci = map(int, input().split())
    edges[ai].append((bi, ci))
    edges[bi].append((ai, ci))
Q, K = map(int, input().split())

weighted_nodes = [0]*(N+1)
def add_weight(k, pre):
    for v in edges[k]:
        d, w = v
        if d != pre:
            weighted_nodes[d] = w + weighted_nodes[k]
            add_weight(d, k)
add_weight(K, -1)

for _ in range(Q):
    s, e = map(int, input().split()))
    print(weighted_nodes[s] + weighted_nodes[e])

Submission status: Runtime Error

Solution code:
def dfs_rec(start, cost, aa, bb, cc):
    use_index = []
    for i in range(aa.count(start)):
        use_index.append(aa.index(start))
    for i in range(bb.count(start)):
        use_index.append(bb.index(start))
    use_index = sorted(use_index)[::-1]
    # この点から行けるところがないとき
    if len(use_index) == 0:
        return
    for i in use_index:
        p = aa[i] if bb[i] == start else bb[i]
        DP_modoki[p-1] = cc[i] + cost
        aa.pop(i)
        bb.pop(i)
        cc.pop(i)
        dfs_rec(p, DP_modoki[p-1], aa, bb, cc)


# ダイクストラとDP?
#ある頂点pからKまでの最短距離のリストがあれば良い?
# 結局Q個その都度検索したほうが早いか?
# 意地悪なサンプルでTLEするかも
N = int(input())
a, b, c = [], [], []
for i in range(N-1):
    s1, s2, s3 = list(map(int, input().split()))
    a.append(s1)
    b.append(s2)
    c.append(s3)
Q, K = list(map(int, input().split()))
x, y = [], []
for i in range(Q):
    s1, s2 = list(map(int, input().split()))
    x.append(s1)
    y.append(s2)
# Kまでの最短距離が必要な頂点のリスト
keisan_list = list(set(x).intersection(set(y)))
# 0からN-1に注意
DP_modoki = [0 for _ in range(N)]

#ここからDP?→ではなく、深さ優先探索で全探索
# 閉路がないなら、辿っていけば最短距離?
dfs_rec(K, 0, a, b, c)
for i in range(Q):
    print(DP_modoki[x[i]-1] + DP_modoki[y[i]-1])

Submission status: Runtime Error

Solution code:
N = int(input())
g = {i: [] for i in range(1, N+1)}    

l = [0] * (N + 1)
visited = []
def dfs2(v, p, d):
    l[v] = d
    visited.append(v)
    for i,ln in g[v]:
        if i == p or i in visited:
            continue
        dfs2(i, v, d+ln)

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())

dfs2(K, -1 , 0)

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

Submission status: Runtime Error

Solution code:
INF = 1000000000000000
V = int(input())
E = V - 1
graph = {x:[] for x in range(V)}
cost = {}
flag = [0 for i in range(V)]
d = [0 for i in range(V)]
#****#

def rootLen(v,p,t):
    d[v] = t  # !
    flag[v] = 1
    for i in range(V):
        if flag[i] == 0 and i in graph[v]:
            rootLen(i,v,t+cost[(i,v)])
        else:
            continue
    return

if __name__ == '__main__':
    
    for i in range(E):
        nums=[int(x) for x in input().split()]
        a,b,c = nums[0]-1,nums[1]-1,nums[2]
        graph[a].append(b)
        graph[b].append(a)
        cost[(a,b)] = c
        cost[(b,a)] = c

    nums=[int(x) for x in input().split()]
    Q,K = nums[0],nums[1]-1
    rootLen(K,-1,0)

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

Submission status: Runtime Error

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

import numpy as np

n = raw_input()
n = int(n)

tree = np.zeros([n,n],dtype=np.int64)
for i in range(n-1):
    abc = raw_input()
    abc = abc.split()
    abc = map(int, abc)
    tree[abc[0]-1,abc[1]-1] = abc[2]
    tree[abc[1]-1,abc[0]-1] = abc[2]

qk = raw_input()
qk = qk.split()
q,k = map(int,qk)

question = []
for i in range(q):
    xy = raw_input()
    xy = xy.split()
    xy = map(int,xy)
    question.append(xy)

distance = []
for i in range(n):
    distance.append(-1)

distance[k-1] = 0

while 1:
    status = 0
    for i in range(len(distance)):
        if distance[i] == -1:
            status = 1
        else:
            for j in range(n):
                if not tree[i][j] == 0 and distance[j] == -1:
                    distance[j] = distance[i] + tree[i][j]
    if status == 0:
        break

for line in question:
    ans = distance[line[0]-1] + distance[line[1]-1]
    print ans

Submission status: Runtime Error

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

import numpy as np

n = raw_input()
n = int(n)

tree = np.zeros([n,n],dtype=np.int64)
for i in range(n-1):
    abc = raw_input()
    abc = abc.split()
    abc = map(int, abc)
    tree[abc[0]-1,abc[1]-1] = abc[2]
    tree[abc[1]-1,abc[0]-1] = abc[2]

qk = raw_input()
qk = qk.split()
q,k = map(int,qk)

question = []
for i in range(q):
    xy = raw_input()
    xy = xy.split()
    xy = map(int,xy)
    question.append(xy)

distance = []
for i in range(n):
    distance.append(-1)

distance[k-1] = 0

while 1:
    status = 0
    for i in range(len(distance)):
        if distance[i] == -1:
            status = 1
        else:
            for j in range(n):
                if tree[i][j] == 0:
                    pass
                elif distance[j] == -1:
                    distance[j] = distance[i] + tree[i][j]
    if status == 0:
        break

for line in question:
    ans = distance[line[0]-1] + distance[line[1]-1]
    print ans

Submission status: Runtime Error

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

import numpy as np

n = raw_input()
n = int(n)

tree = np.zeros([n,n],dtype=np.int64)
for i in range(n-1):
    abc = raw_input()
    abc = abc.split()
    abc = map(int, abc)
    tree[abc[0]-1,abc[1]-1] = abc[2]
    tree[abc[1]-1,abc[0]-1] = abc[2]

qk = raw_input()
qk = qk.split()
q,k = map(int,qk)


distance = []
for i in range(n):
    distance.append(-1)

distance[k-1] = 0

while 1:
    for i in range(len(distance)):
        if distance[i] == -1:
            pass
        else:
            status = 0
            for j in range(n):
                if tree[i][j] == 0:
                    pass
                elif distance[j] == -1:
                    distance[j] = distance[i] + tree[i][j]
                if distance[j] == -1:
                    status = 1
    if status == 0:
        break

answers = []
for i in range(q):
    xy = raw_input()
    xy = xy.split()
    xy = map(int,xy)
    ans = distance[xy[0]-1] + distance[xy[1]-1]
    answers.append(ans)

for ans in answers:
    print ans

Submission status: Runtime Error

Solution code:
def d():
    N = int(input())
    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        ai, bi, ci = map(int, input().split())
        edges[ai].append((bi, ci))
        edges[bi].append((ai, ci))
    Q, K = map(int, input().split())
    queries = [tuple(map(int, input().split())) for _ in range(Q)]

    weighted_nodes = [0]*(N+1)
    used = {K}
    def add_weight(k):
        for v in edges[k]:
            d, w = v
            if d in used:
                continue
            used.add(d)
            weighted_nodes[d] = w + weighted_nodes[k]
            add_weight(d)
    add_weight(K)

    for q in queries:
        s, e = q
        print(weighted_nodes[s] + weighted_nodes[e])

d()

Submission status: Runtime Error

Solution code:
def d():
    N = int(input())
    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        ai, bi, ci = map(int, input().split())
        edges[ai].append((bi, ci))
        edges[bi].append((ai, ci))
    Q, K = map(int, input().split())
    queries = [tuple(map(int, input().split())) for _ in range(Q)]

    weighted_nodes = [0]*(N+1)
    def add_weight(k):
        for v in edges[k]:
            d, w = v
            if (weighted_nodes[d] != 0) or (d == K):
                continue
            weighted_nodes[d] = w + weighted_nodes[k]
            add_weight(d)
    add_weight(K)

    for q in queries:
        s, e = q
        print(weighted_nodes[s] + weighted_nodes[e])

d()

Submission status: Runtime Error

Solution code:
def d():
    N = int(input())
    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        ai, bi, ci = map(int, input().split())
        edges[ai].append((bi, ci))
        edges[bi].append((ai, ci))
    Q, K = map(int, input().split())
    queries = [tuple(map(int, input().split())) for _ in range(Q)]

    for edge in edges[1:]:

        if K == edge:
            pass
    weighted_nodes = [0]*(N+1)
    def add_weight(k):
        for v in edges[k]:
            d, w = v
            if (weighted_nodes[d] != 0) or (d == K):
                continue
            weighted_nodes[d] = w + weighted_nodes[k]
            add_weight(d)
    add_weight(K)

    for q in queries:
        s, e = q
        print(weighted_nodes[s] + weighted_nodes[e])

d()

Submission status: Runtime Error

Solution code:
n=int(input())-1

edges = {}
lens = {}
for _ in range(n):
    [a, b, c] = map(int, input().split())
    if a > b:
        a,b=b,a
    edges.setdefault(a, []).append(b)
    edges.setdefault(b, []).append(a)
    lens[(a,b)] = c

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

dists = {}
def build(x, d=0):
    dists[x] = d
    for c in edges.get(x, []):
        if c not in dists:
            if (min(x,c), max(x,c)) not in  lens:
                import time
                time.sleep(3)
            build(c, d + lens[(min(x,c), max(x,c))])

build(k)

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import collections

def dfs(n, pre, T, dist, d) :
	dist[n] = d
	for i in T[n] :
		if i[0] != pre :
			dfs(i[0], n, T, dist, d + i[1])


N = int(input())
T = collections.defaultdict(lambda : [])
for i in range(N-1) :
	a, b, c = map(int, input().split())
	T[a].append((b, c))
	T[b].append((a, c))
Q, K = map(int, input().split())

d = {}
dfs(K, -1, T, d, 0)

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

Submission status: Runtime Error

Solution code:
# encoding:utf-8
import sys

def main():
	n = int(input())
	vers = [list(map(int, input().split())) for _ in range(n - 1)]
	q, k = list(map(int, input().split()))
	queries = [list(map(int, input().split())) for _ in range(q)]

	#n = 10 ** 5
	#vers = [[i + 1, i + 2, 10 ** 9] for i in range(n - 1)]

	new_vers = mapping(n, vers)
	dist = calcMinDist(n, new_vers, k, queries)
	calcQueries(dist, queries, k)
	
def mapping(n, vers):
	new_vers = {i :[] for i in range(n)}
	for ver in vers:
		new_vers[ver[0] - 1].append((ver[1], ver[2]))
		new_vers[ver[1] - 1].append((ver[0], ver[2]))
	return new_vers

def calcMinDist(n, new_vers, k, queries):
	dist = [- 1 for _ in range(n)]
	flag = [False for _ in range(n)]
	dist[k - 1] = 0
	flag[k - 1] = True
	dfs(new_vers, dist, flag, k)
	return dist

def dfs(new_vers, dist, flag, frm):
	flag[frm - 1] = True
	vs = new_vers[frm - 1]
	for v in vs:
		if flag[v[0] - 1] == False:
			dist[v[0] - 1] = dist[frm - 1] + v[1]
			new_ver, dist, flag, _ = dfs(new_vers, dist, flag, v[0])

	return [new_vers, dist, flag, frm]

def calcQuery(dist, query, k):
	print(dist[query[0] - 1] + dist[query[1] - 1])

def calcQueries(dist, queries, k):
	for query in queries:
		calcQuery(dist, query, k)

if __name__ == '__main__':
	sys.setrecursionlimit(100000)
	main()

Submission status: Runtime Error

Solution code:
n=int(input())-1

edges = {}
lens = {}
for _ in range(n):
    [a, b, c] = map(int, input().split())
    if a > b:
        a,b=b,a
    edges.setdefault(a, []).append(b)
    edges.setdefault(b, []).append(a)
    lens[(a,b)] = c

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

dists = {}
def build(x, d=0):
    dists[x] = d
    for c in edges[x]:
        if c not in dists:
            build(c, d + lens[(min(x,c), max(x,c))])

build(k)


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

Submission status: Runtime Error

Solution code:
# encoding:utf-8

import sys
sys.setrecursionlimit(100000)

def main():
	n = int(input())
	vers = [list(map(int, input().split())) for _ in range(n - 1)]
	q, k = list(map(int, input().split()))
	queries = [list(map(int, input().split())) for _ in range(q)]

	n = 10 ** 5
	vers = [[i + 1, i + 2, 10 ** 9] for i in range(n - 1)]
	print(vers)

	new_vers = mapping(n, vers)
	dist = calcMinDist(n, new_vers, k, queries)
	print(dist)
	calcQueries(dist, queries, k)
	
def mapping(n, vers):
	new_vers = {i :[] for i in range(n)}
	for ver in vers:
		new_vers[ver[0] - 1].append((ver[1], ver[2]))
		new_vers[ver[1] - 1].append((ver[0], ver[2]))
	return new_vers

def calcMinDist(n, new_vers, k, queries):
	dist = [- 1 for _ in range(n)]
	flag = [False for _ in range(n)]
	dist[k - 1] = 0
	flag[k - 1] = True
	dfs(new_vers, dist, flag, k)
	return dist

def dfs(new_vers, dist, flag, frm):
	flag[frm - 1] = True
	vs = new_vers[frm - 1]
	for v in vs:
		if flag[v[0] - 1] == False:
			dist[v[0] - 1] = dist[frm - 1] + v[1]
			new_ver, dist, flag, _ = dfs(new_vers, dist, flag, v[0])

	return [new_vers, dist, flag, frm]

def calcQuery(dist, query, k):
	print(dist[query[0] - 1] + dist[query[1] - 1])

def calcQueries(dist, queries, k):
	for query in queries:
		calcQuery(dist, query, k)

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

long long d[N];
vector<pair<int, int>> g[N];

void dfs(int u, int f, long long w) {
  d[u] = w;
  for (auto &go : g[u]) {
    if (go.first != f) {
      dfs(go.first, u, w + go.second);
    }
  }
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i < n; ++i) {
    int u, v, w;
    scanf("%d %d %d", &u, &v, &w);
    g[u].push_back({v, w});
    g[v].push_back({u, w});
  }
  int q, k;
  scanf("%d %d", &q, &k);
  dfs(k, k, 0);
  while (q--) {
    int u, v;
    scanf("%d %d", &u, &v);
    cout << d[u] + d[v] << endl;
  }
  return 0;
}

Submission status: Runtime Error

Solution code:
n=int(input())-1

edges = {}
lens = {}
for _ in range(n):
    [a, b, c] = map(int, input().split())
    if a > b:
        a,b=b,a
    edges.setdefault(a, []).append(b)
    edges.setdefault(b, []).append(a)
    lens[(a,b)] = c

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

used = set()
dists = {}
def build(x, d=0):
    dists[x] = d
    for c in edges[x]:
        if c not in used:
            used.add(c)
            build(c, d + lens[(min(x,c), max(x,c))])

build(k)


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

Submission status: Runtime Error

Solution code:
# encoding:utf-8

def main():
	n = int(input())
	vers = [list(map(int, input().split())) for _ in range(n - 1)]
	q, k = list(map(int, input().split()))
	queries = [list(map(int, input().split())) for _ in range(q)]
	new_vers = mapping(n, vers)
	dist = calcMinDist(n, new_vers, k, queries)
	calcQueries(dist, queries, k)
	
def mapping(n, vers):
	new_vers = {i :[] for i in range(n)}
	for ver in vers:
		new_vers[ver[0] - 1].append((ver[1], ver[2]))
		new_vers[ver[1] - 1].append((ver[0], ver[2]))
	return new_vers

def calcMinDist(n, new_vers, k, queries):
	dist = [10000 for _ in range(n)]
	flag = [False for _ in range(n)]
	dist[k - 1] = 0
	flag[k - 1] = True
	dfs(new_vers, dist, flag, k)
	return dist

def dfs(new_vers, dist, flag, frm):
	flag[frm - 1] = True
	vs = new_vers[frm - 1]
	for v in vs:
		if flag[v[0] - 1] == False:
			dist[v[0] - 1] = dist[frm - 1] + v[1]
			new_ver, dist, flag, _ = dfs(new_vers, dist, flag, v[0])

	return [new_vers, dist, flag, frm]

def calcQuery(dist, query, k):
	print(dist[query[0] - 1] + dist[query[1] - 1])

def calcQueries(dist, queries, k):
	for query in queries:
		calcQuery(dist, query, k)

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
n = int(input())

d = [0 for i in range(n+1)]
adj = [[] for i in range(n+1)]

def dfs(u, par):
    for p in adj[u]:
        v, w = map(int, p)
        # print(v, w)
        if v != par:
            d[v] = d[u]+w
            dfs(v, u)

edge = [list(map(int, input().split())) for i in range(n-1)]
q, k = map(int, input().split())
query = [list(map(int, input().split())) for i in range(q)]

for e in edge:
    adj[e[0]].append([e[1], e[2]])
    adj[e[1]].append([e[0], e[2]])
    
dfs(k, -1)

for p in query:
    print(d[p[0]]+d[p[1]])

Submission status: Runtime Error

Solution code:
n = int(input())
g = []
d = [0] * (n * 2)
for i in range(n * 2):
    g.append([]);
for i in range(n - 1):
    u, v, w = map(int, input().split())
    g[u].append([v, w])
    g[v].append([u, w])
q, k = map(int, input().split())
def dfs(u, f, w):
    d[u] = w;
    for go in g[u]:
        if go[0] != f:
            dfs(go[0], u, go[1] + w)
dfs(k, k, 0)
while q > 0:
    u, v = map(int, input().split())
    print(d[u] + d[v])
    q -= 1

Submission status: Runtime Error

Solution code:
n = int(input())
g = []
d = [0] * (n + 1)
for i in range(n + 1):
    g.append([]);
for i in range(n - 1):
    u, v, w = map(int, input().split())
    g[u].append([v, w])
    g[v].append([u, w])
q, k = map(int, input().split())
def dfs(u, f, w):
    d[u] = w;
    for go in g[u]:
        if go[0] != f:
            dfs(go[0], u, go[1] + w)
dfs(k, k, 0)
while q > 0:
    u, v = map(int, input().split())
    print(d[u] + d[v])
    q -= 1

Submission status: Runtime Error

Solution code:
n=int(input())-1

nodes = {1: (None, 0, 0)}
for _ in range(n):
    [a, b, c] = map(int, input().split())
    if a > b:
        a,b=b,a
    if a not in nodes:
        import time
        time.sleep(3)
    nodes[b] = nodes[a], c, c + nodes[a][2]

def dist(a, b):
    if a == b:
        return 0
    if a[2] < b[2]:
        return b[1] + dist(a, b[0])
    if a[2] > b[2]:
        return a[1] + dist(a[0], b)

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

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

Submission status: Runtime Error

Solution code:
# encoding:utf-8

def main():
	n = int(input())
	vers = [list(map(int, input().split())) for _ in range(n - 1)]
	q, k = list(map(int, input().split()))
	queries = [list(map(int, input().split())) for _ in range(q)]
	#print(vers)
	#print(queries)
	dist = calcMinDist(n, vers, k, queries)
	calcQueries(dist, queries, k)
	
def calcMinDist(n, vers, k, queries):
	dist = [10000 for _ in range(n)]
	flag = [False for _ in range(n - 1)]
	dist[k - 1] = 0
	dfs(vers, dist, flag, k)
	return dist

def dfs(vers, dist, flag, frm):
	#print(frm)
	for i, ver in enumerate(vers):
		if flag[i] == False:
			if ver[0] == frm:
				to = ver[1]
				dist[to - 1] = dist[frm - 1] + ver[2]
				flag[i] = True
				vers, dist, flag, _ = dfs(vers, dist, flag, to)
			elif ver[1] == frm:
				to = ver[0]
				dist[to - 1] = dist[frm - 1] + ver[2]
				flag[i] = True
				vers, dist, flag, _ = dfs(vers, dist, flag, to)

	return [vers, dist, flag, frm]

def calcQuery(dist, query, k):
	print(dist[query[0] - 1] + dist[query[1] - 1])

def calcQueries(dist, queries, k):
	for query in queries:
		calcQuery(dist, query, k)

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
n=int(input())-1

nodes = {1: (None, 0, 0)}
for _ in range(n):
    [a, b, c] = map(int, input().split())
    if a > b:
        a,b=b,a
    nodes[b] = nodes[a], c, c + nodes[a][2]

def dist(a, b):
    if a == b:
        return 0
    if a[2] < b[2]:
        return b[1] + dist(a, b[0])
    if a[2] > b[2]:
        return a[1] + dist(a[0], b)

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

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

Submission status: Runtime Error

Solution code:
def dfs(now, par, d, dist, g):
    dist[now] = d
    for to, cost in g[now]:
        if to == par: continue
        dfs(to, now, d + cost, dist, g)


n = int(raw_input())
g = [[] for _ in xrange(n)]
for i in xrange(n - 1):
    a, b, c = map(int, raw_input().split())
    a -= 1; b -= 1
    g[a].append([b, c])
    g[b].append([a, c])
q, k = map(int, raw_input().split())
k -= 1
dist = [-1] * n
dfs(k, -1, 0, dist, g)
for i in xrange(q):
    x, y = map(int, raw_input().split())
    x -= 1; y -= 1
    print dist[x] + dist[y]

Submission status: Runtime Error

Solution code:
#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>


#define INF 1000000002486618624LL
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)


std::vector<std::vector<std::pair<int, long long>>> G;

std::vector<long long> cost;

int N, Q, K;

void dfs(int i, long long C) {
  int k;

  long long c;
  
  for (const auto& pair : G[i]) {
    std::tie(k, c) = pair;
    
    if (cost[k] < INF)
      continue;

    dfs(k, cost[k] = C + c);
  }
}


int main(int argc, char** argv)
{
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);

  std::cout << std::fixed << std::setprecision(6);

  int a, b, c, x, y;

  std::cin >> N;

  G.resize(N + 1);

  for (int i = 0; i < N - 1; i ++) {
    std::cin >> a >> b >> c;

    G[a].emplace_back(b, c);
    G[b].emplace_back(a, c);
  }

  std::cin >> Q >> K;

  cost.resize(N + 1);

  std::fill(ALL(cost), INF);

  cost[K] = 0;

  dfs(K, 0);

  for (int i = 0; i < Q; i ++) {
    std::cin >> x >> y;

    std::cout << cost[x] + cost[y] << std::endl;
  }

  return 0;
}

Submission status: Runtime Error

Solution code:
n=int(raw_input())
tr=[[] for i in range(n)]
for i in range(n-1) :
  a,b,c=map(int,raw_input().split())
  a -= 1
  b -= 1
  tr[a].append((b,c))
  tr[b].append((a,c))
m,k=map(int,raw_input().split())
k -= 1
dis=[0 for i in range(n)]
def dfs(u,w=-1,l=0) :
  dis[u]=l
  for v,v1 in tr[u] :
    if v!=w :
      dfs(v,u,l+v1)
dfs(k)
for i in range(m) :
  x,y=map(int,raw_input().split())
  x-=1
  y-=1
  print dis[x]+dis[y]

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100001)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
g = []
for i in range(n+1): g.append([])

for i in range(n-1):
    a, b, c = na()
    g[a].append((b,c))
    g[b].append((a,c))

q,k = na()

def dfs(cur, pre, g, par, dw, w):
    dw[cur] = w
    par[cur] = pre
    for e in g[cur]:
        if e[0] != pre:
            dfs(e[0], cur, g, par, dw, w + e[1])

par = [-1] * (n+2)
dw = [-1] * (n+2)
dfs(k, -1, g, par, dw, 0)

for z in range(q):
    x, y = na()
    print(dw[x] + dw[y])

Submission status: Runtime Error

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
g = []
for i in range(n+1): g.append([])

for i in range(n-1):
    a, b, c = na()
    g[a].append((b,c))
    g[b].append((a,c))

q,k = na()

def dfs(cur, pre, g, par, dw, w):
    dw[cur] = w
    par[cur] = pre
    for e in g[cur]:
        if e[0] != pre:
            dfs(e[0], cur, g, par, dw, w + e[1])

par = [-1] * (n+2)
dw = [-1] * (n+2)
dfs(k, -1, g, par, dw, 0)

for z in range(q):
    x, y = na()
    print(dw[x] + dw[y])