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:
def search_dist(g, dist, e):
    for b, c in g.get(e):
        if dist[b] < 10**16:
            continue
        dist[b] = dist[e] + c
        search_dist(g, dist, b)

def main():
    g = {}
    N = int(input())
    for _ in range(N-1):
        a, b, c = list(map(int, input().split(' ')))
        g[a] = g.get(a, []) + [(b, c)]
        g[b] = g.get(b, []) + [(a, c)]
    Q, K = list(map(int, input().split(' ')))
    dist = [10**16]*(N+1)
    dist[K] = 0
    search_dist(g, dist, K)
    for _ in range(Q):
        x, y = list(map(int, input().split(' ')))
        print(dist[x]+dist[y])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:

def search_dist(g, dist, e):
    for b, c in g.get(e):
        if dist[b] < 10**15:
            continue
        dist[b] = dist[e] + c
        search_dist(g, dist, b)

def main():
    g = {}
    N = int(input())
    for _ in range(N-1):
        a, b, c = list(map(int, input().split(' ')))
        g[a] = g.get(a, []) + [(b, c)]
        g[b] = g.get(b, []) + [(a, c)]
    Q, K = list(map(int, input().split(' ')))
    dist = [10**15]*(N+1)
    dist[K] = 0
    search_dist(g, dist, K)
    for _ in range(Q):
        x, y = list(map(int, input().split(' ')))
        print(dist[x]+dist[y])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000000000000000)

tree = dict()
cost = dict()

N = int(input())
for i in range(N - 1):
    a, b, c = map(int, input().split())
    if a in tree:
        tree[a].append(b)
    else:
        tree[a] = []
        tree[a].append(b)
    if b in tree:
        tree[b].append(a)
    else:
        tree[b] = []
        tree[b].append(a)
    cost[(a, b)] = c
    cost[(b, a)] = c
starts = []
ends = []
Q, K = map(int, input().split())
for i in range(Q):
    x, y = map(int, input().split())
    starts.append(x)
    ends.append(y)

depth = [10000000000000000 for i in range(N)]

def dps(position, total_cost):
    if depth[position - 1] > total_cost:
        depth[position - 1] = total_cost
    for next_position in tree[position]:
        if depth[next_position - 1] == 10000000000000000:
            dps(next_position, depth[position - 1] + cost[(position, next_position)])

depth[K-1] = 0
dps(K, 0)

for start, end in zip(starts, ends):
    print(depth[start - 1] + depth[end - 1])

Submission status: Runtime Error

Solution code:
#! -*- coding: utf-8 -*-
import sys

tree = dict()
cost = dict()

N = int(input())
sys.setrecursionlimit(N*10)
for i in range(N - 1):
    a, b, c = map(int, input().split())
    if a in tree:
        tree[a].append(b)
    else:
        tree[a] = []
        tree[a].append(b)
    if b in tree:
        tree[b].append(a)
    else:
        tree[b] = []
        tree[b].append(a)
    cost[(a, b)] = c
    cost[(b, a)] = c
starts = []
ends = []
Q, K = map(int, input().split())
for i in range(Q):
    x, y = map(int, input().split())
    starts.append(x)
    ends.append(y)

depth = [100010 for i in range(N)]

def dps(position, total_cost):
    if depth[position - 1] > total_cost:
        depth[position - 1] = total_cost
    for next_position in tree[position]:
        if depth[next_position - 1] == 100010:
            dps(next_position, depth[position - 1] + cost[(position, next_position)])

depth[K-1] = 0
dps(K, 0)

for start, end in zip(starts, ends):
    print(depth[start - 1] + depth[end - 1])

Submission status: Runtime Error

Solution code:
tree = dict()
cost = dict()

N = int(input())
for i in range(N - 1):
    a, b, c = map(int, input().split())
    if a in tree:
        tree[a].append(b)
    else:
        tree[a] = []
        tree[a].append(b)
    if b in tree:
        tree[b].append(a)
    else:
        tree[b] = []
        tree[b].append(a)
    cost[(a, b)] = c
    cost[(b, a)] = c
starts = []
ends = []
Q, K = map(int, input().split())
for i in range(Q):
    x, y = map(int, input().split())
    starts.append(x)
    ends.append(y)

depth = [10000000000000000 for i in range(N)]

def dps(position, total_cost):
    if depth[position - 1] > total_cost:
        depth[position - 1] = total_cost
    for next_position in tree[position]:
        if depth[next_position - 1] == 10000000000000000:
            dps(next_position, depth[position - 1] + cost[(position, next_position)])

depth[K-1] = 0
dps(K, 0)

for start, end in zip(starts, ends):
    print(depth[start - 1] + depth[end - 1])

Submission status: Runtime Error

Solution code:
tree = dict()
cost = dict()

N = int(input())
for i in range(N - 1):
    a, b, c = map(int, input().split())
    if a in tree:
        tree[a].append(b)
    else:
        tree[a] = []
        tree[a].append(b)
    if b in tree:
        tree[b].append(a)
    else:
        tree[b] = []
        tree[b].append(a)
    cost[(a, b)] = c
    cost[(b, a)] = c
starts = []
ends = []
Q, K = map(int, input().split())
for i in range(Q):
    x, y = map(int, input().split())
    starts.append(x)
    ends.append(y)

depth = [False for i in range(N)]

def dps(position, total_cost):
    if depth[position - 1] > total_cost:
        depth[position - 1] = total_cost
    for next_position in tree[position]:
        if depth[next_position - 1] == False:
            dps(next_position, depth[position - 1] + cost[(position, next_position)])

depth[K-1] = 0
dps(K, 0)

for start, end in zip(starts, ends):
    print(depth[start - 1] + depth[end - 1])

Submission status: Runtime Error

Solution code:
tree = dict()
cost = dict()

N = int(input())
for i in range(N - 1):
    a, b, c = map(int, input().split())
    if a in tree:
        tree[a].append(b)
    else:
        tree[a] = []
        tree[a].append(b)
    if b in tree:
        tree[b].append(a)
    else:
        tree[b] = []
        tree[b].append(a)
    cost[(a, b)] = c
    cost[(b, a)] = c
starts = []
ends = []
Q, K = map(int, input().split())
for i in range(Q):
    x, y = map(int, input().split())
    starts.append(x)
    ends.append(y)

depth = [100000000000001 for i in range(N)]

def dps(position, total_cost):
    if depth[position - 1] > total_cost:
        depth[position - 1] = total_cost
    for next_position in tree[position]:
        if depth[next_position - 1] == 100000000000001:
            dps(next_position, depth[position - 1] + cost[(position, next_position)])

depth[K-1] = 0
dps(K, 0)

for start, end in zip(starts, ends):
    print(depth[start - 1] + depth[end - 1])

Submission status: Runtime Error

Solution code:
#! -*- coding: utf-8 -*-

tree = dict()
cost = dict()

N = int(input())
for i in range(N - 1):
    a, b, c = map(int, input().split())
    if a in tree:
        tree[a].append(b)
    else:
        tree[a] = []
        tree[a].append(b)
    if b in tree:
        tree[b].append(a)
    else:
        tree[b] = []
        tree[b].append(a)
    cost[(a, b)] = c
    cost[(b, a)] = c
starts = []
ends = []
Q, K = map(int, input().split())
for i in range(Q):
    x, y = map(int, input().split())
    starts.append(x)
    ends.append(y)

depth = [100010 for i in range(N)]

def dps(position, total_cost):
    if depth[position - 1] > total_cost:
        depth[position - 1] = total_cost
    for next_position in tree[position]:
        if depth[next_position - 1] == 100010:
            dps(next_position, depth[position - 1] + cost[(position, next_position)])

depth[K-1] = 0
dps(K, 0)

for start, end in zip(starts, ends):
    print(depth[start - 1] + depth[end - 1])

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
const lli mod=1e9+7;
const lli pINF=LLONG_MAX;
const lli nINF=-LLONG_MAX;
void fast() {std::ios::sync_with_stdio(false);cin.tie(NULL);}
lli power(lli a,lli b){lli ans=1;while(b!=0){ if(b%2==1){ans*=a;}b/=2;a*=a;} return ans;}
lli invmod(lli a) {return pow(a,mod-2);}
#define vi vector<int>
#define INT 1000000005 
#define vlli vector<lli>
#define PII pair<int,int>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define si(n) scanf("%d",&n)
#define sli(n) scanf("%lld",&n)
#define printi(n) printf("%d\n",n)
#define printli(n) printf("%lld\n",n)
#define all(v) v.begin(),v.end()
#define forn(i,n) for(int i=0;i<n;i++)
void print(int a[],int n){for(int i=0;i<n;i++) cout<<a[i]<<" ";}
lli dist[100005];
vector< pair<int,lli> > adj[100005];

void dfs(int node,int par,lli cost){
    dist[node]=cost;
    
    for(auto i:adj[node]){
        if(i.F==par) continue;
        dfs(i.F,node,cost+i.S);
    }
}

int main() 
{
    int n,x,y;
    lli cost;
    si(n);
    
    for(int i=0;i<n-1;i++){
        si(x);si(y);sli(cost);
        adj[x].pb(mp(y,cost));
        adj[y].pb(mp(x,cost));
    }
    
    int q,k;
    si(q);si(k);
    
    dfs(k,-1,0);
    
    while(q--){
        si(x);si(y);
        cout<<dist[x]+dist[y]<<endl;
    }
	return 0;
}

Submission status: Runtime Error

Solution code:
import sys
from scipy.sparse import*
f=lambda*z:map(int,sys.stdin.readline().split())
n,=f();a,b,c=zip(*map(f,range(n-1)));q,k=f()
z=csgraph.bellman_ford(csr_matrix((c,(a,b)),[n+1]*2),0,k)
for _ in range(q):x,y=f();print int(z[x]+z[y])

Submission status: Runtime Error

Solution code:
import sys
from scipy.sparse import*
f=lambda*z:map(int,sys.stdin.readline().split())
n,=f();a,b,c=zip(*map(f,[0]*~-n));q,k=f()
z=csgraph.bellman_ford(csr_matrix((c,(a,b)),[n+1]*2),0,k)
for _ in range(q):x,y=f();print int(z[x]+z[y])

Submission status: Runtime Error

Solution code:
import sys
if sys.version_info[0]>=3: raw_input=input

from scipy.sparse import*
f=lambda*z:map(int,sys.stdin.readline().split())
n,=f();a,b,c=zip(*map(f,[0]*~-n));q,k=f()
z=csgraph.shortest_path(csr_matrix((c,(a,b)),[n+1]*2),0,k)
for _ in range(q):x,y=f();print int(z[x]+z[y])

Submission status: Runtime Error

Solution code:
import sys
from scipy.sparse import*
f=lambda*z:map(int,sys.stdin.readline().split())
n,=f();a,b,c=zip(*map(f,[0]*~-n));q,k=f();x,y=zip(*map(f,[0]*q))
z=csgraph.dijkstra(csr_matrix((c,(a,b)),[n+1]*2),0,k)
for _ in range(q):x,y=f();print z[x]+z[y]

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

n = int(input())
tree = [[] for i in range(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))

depth = [0] * (n + 1)
def dfs(v, p, d):
    depth[v] = d
    for to, cost in tree[v]:
        if to != p:
            dfs(to, v, d + cost)

q, k = map(int, input().split())
dfs(k, 0, 0)
xy = [tuple(map(int, input().split())) for i in range(q)]

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

Submission status: Runtime Error

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

depth = [0] * (n + 1)
def dfs(v, p, d):
    depth[v] = d
    for to, cost in tree[v]:
        if to != p:
            dfs(to, v, d + cost)

q, k = map(int, input().split())
dfs(k, 0, 0)
xy = [tuple(map(int, input().split())) for i in range(q)]

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

Submission status: Runtime Error

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

depth = [0] * (n + 1)
def dfs(v, p, d):
    depth[v] = d
    for to, cost in tree[v]:
        if to != p:
            dfs(to, v, d + cost)

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

Submission status: Runtime Error

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

depth = [0] * (n + 1)
def dfs(v, p, d):
    depth[v] = d
    for to, cost in tree[v]:
        if to != p:
            dfs(to, v, d + cost)

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

Submission status: Runtime Error

Solution code:
tree = [[] for i in range(100001)]
depth = [0] * 100001

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

n = int(input())
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, -1, 0)
for i in range(q):
    x, y = map(int, input().split())
    print(depth[x] + depth[y])

Submission status: Runtime Error

Solution code:
#import sys;sys.setrecursionlimit(int(1e7))

class edge():
    def __init__(self,_to,_cost):
        self.to = _to;
        self.cost = _cost;

N = int(input())
tree = [[] for i in range(N+1)]

for i in range(N-1):
    a,b,c = map(int,input().split())
    a = a - 1
    b = b - 1
    tree[a].append(edge(b,c))
    tree[b].append(edge(a,c))
Q,K = map(int,input().split())
K = K - 1
depth = [None]*N

def DFS(v,p,d):
    depth[v] = d
    for e in tree[v]:
        if e.to == p:
            continue
        DFS(e.to, v, d + e.cost)
DFS(K,-1,0)

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

Submission status: Runtime Error

Solution code:
N = int(input())

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

dist = [-1 for _ in range(len(A))]

q = list(range(len(A)))

def DFS(v,d):
  dist[v] = d;
  for i,c in A[v]:
    if dist[i]==-1:
    	DFS(i,d+c)
         

DFS(K-1,0)


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

Submission status: Runtime Error

Solution code:
import heapq
import copy

N = int(input())

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

dist = [-1 for _ in range(len(A))]

q = list(range(len(A)))

def DFS(v,d):
  dist[v] = d;
  for i,c in A[v]:
    if dist[i]==-1:
    	DFS(i,d+c)
         

DFS(K-1,0)


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

Submission status: Runtime Error

Solution code:

class edge():
    def __init__(self,_to,_cost):
        self.to = _to;
        self.cost = _cost;

N = int(input())
tree = {i:[] for i in range(N+1)}

for i in range(N-1):
    a,b,c = list(map(int,input().split()))
    a = a - 1
    b = b - 1
    tree[a].append(edge(b,c))
    tree[b].append(edge(a,c))
Q,K = list(map(int,input().split()))
K = K - 1
depth = [None]*N

def DFS(v,p,d):
    depth[v] = d
    for e in tree[v]:
        if e.to == p:
            continue
        DFS(e.to, v, d + e.cost)
DFS(K,-1,0)

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

Submission status: Runtime Error

Solution code:
class edge():
    def __init__(self,_to,_cost):
        self.to = _to;
        self.cost = _cost;

N = int(input())
tree = [[] for i in range(N+1)]

for i in range(N-1):
    a,b,c = list(map(int,input().split()))
    a = a - 1
    b = b - 1
    tree[a].append(edge(b,c))
    tree[b].append(edge(a,c))
Q,K = list(map(int,input().split()))
K = K - 1
depth = [None]*N

def DFS(v,p,d):
    depth[v] = d
    for e in tree[v]:
        if e.to == p:
            continue
        DFS(e.to, v, d + e.cost)
DFS(K,-1,0)

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

Submission status: Runtime Error

Solution code:

class edge():
    def __init__(self,_to,_cost):
        self.to = _to;
        self.cost = _cost;

N = int(input())
tree = [[] for i in range(N+1)]

for i in range(N-1):
    a,b,c = list(map(int,input().split()))
    a = a - 1
    b = b - 1
    tree[a].append(edge(b,c))
    tree[b].append(edge(a,c))
Q,K = list(map(int,input().split()))
K = K - 1
dmax = 10**14 + 1
depth = [dmax for _ in range(N+1)]

def DFS(v,p,d):
    depth[v] = d
    for e in tree[v]:
        if e.to == p:
            continue
        DFS(e.to, v, d + e.cost)
DFS(K,-1,0)

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

Submission status: Runtime Error

Solution code:

class edge():
    def __init__(self,_to,_cost):
        self.to = _to;
        self.cost = _cost;

N = int(input())
tree = [[] for i in range(N+1)]

for i in range(N-1):
    a,b,c = list(map(int,input().split()))
    a = a - 1
    b = b - 1
    tree[a].append(edge(b,c))
    tree[b].append(edge(a,c))
Q,K = list(map(int,input().split()))
K = K - 1
dmax = 10**14 + 1
depth = [dmax for _ in range(N)]

def DFS(v,p,d):
    depth[v] = d
    for e in tree[v]:
        if e.to == p:
            continue
        DFS(e.to, v, d + e.cost)
DFS(K,-1,0)

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

Submission status: Runtime Error

Solution code:
class edge():
    def __init__(self,_to,_cost):
        self.to = _to;
        self.cost = _cost;

N = int(input())
tree = [[] for i in range(N)]

for i in range(N-1):
    a,b,c = list(map(int,input().split()))
    a = a - 1
    b = b - 1
    tree[a].append(edge(b,c))
    tree[b].append(edge(a,c))
Q,K = list(map(int,input().split()))
K = K - 1
dmax = 10**14 + 1
depth = [dmax for _ in range(N)]
depth[K] = 0

def DFS(v,p,d):
    depth[v] = d
    for e in tree[v]:
        if e.to == p:
            continue
        DFS(e.to, v, d + e.cost)
DFS(K,-1,0)

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

Submission status: Runtime Error

Solution code:

class edge():
    def __init__(self,_to,_cost):
        self.to = _to;
        self.cost = _cost;

N = int(input())
tree = [[] for i in range(N)]

for i in range(N-1):
    a,b,c = list(map(int,input().split()))
    a = a - 1
    b = b - 1
    tree[a].append(edge(b,c))
    tree[b].append(edge(a,c))
Q,K = list(map(int,input().split()))
K = K - 1

depth = [-1] * N

def DFS(v,p,d):
    depth[v] = d
    for e in tree[v]:
        if e.to == p:
            continue
        DFS(e.to, v, d + e.cost)
DFS(K,-1,0)

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

Submission status: Runtime Error

Solution code:
class edge():
    def __init__(self,_to,_cost):
        self.to = _to;
        self.cost = _cost;

N = int(input())
tree = [[] for i in range(N)]

for i in range(N-1):
    a,b,c = list(map(int, input().split()))
    a = a - 1
    b = b - 1
    tree[a].append(edge(b,c))
    tree[b].append(edge(a,c))
Q, K = list(map(int, input().split()))
K = K - 1

depth = [0]*N
def DFS(v,p,d):
    depth[v] = d
    for e in tree[v]:
        if e.to==p :
            continue
        DFS(e.to, v, d + e.cost)
DFS(K,-1,0)

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

Submission status: Runtime Error

Solution code:
N = int(input())

class edge():
    def __init__(self,_to,_cost):
        self.to = _to;
        self.cost = _cost;

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

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

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

def DFS(v,p,d):
    depth[v] = d
    for e in tree[v]:
        if e.to==p :
            continue
        DFS(e.to, v, d + e.cost)

DFS(K,-1,0)

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

Submission status: Runtime Error

Solution code:
N = int(input())

class edge:
    def __init__(self,_to,_cost):
        self.to = _to;
        self.cost = _cost;

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

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

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

def DFS(v,p,d):
    depth[v] = d
    for e in tree[v]:
        if e.to==p :
            continue
        DFS(e.to, v, d + e.cost)

DFS(K,-1,0)

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

Submission status: Runtime Error

Solution code:
import sys
import collections

sys.setrecursionlimit(1e7)

def dfs(node, parent, distance):
    depth[node] = distance
    for next_node, cost in Tree[node]:
        if next_node != parent:
            dfs(next_node, node, distance + cost)

N = int(input())

Tree = collections.defaultdict(list)

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

depth = {}
dfs(k, -1, 0)

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

Submission status: Runtime Error

Solution code:
import collections

def dfs(node, parent, distance):
    depth[node] = distance
    for next_node, cost in Tree[node]:
        if next_node != parent:
            dfs(next_node, node, distance + cost)

N = int(input())

Tree = collections.defaultdict(list)

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

depth = {}
dfs(k, -1, 0)

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
n=int(input())
g=[[] for _ in range(n)]
for _ 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())
d=[-1]*n
def f(k,c):
    d[k]=c
    for i,v in g[k]:
        if d[i]==-1:
            f(i,c+v)
f(k-1,0)
for _ 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.setrecusionlimit(100000)
n=int(input())
g=[[] for _ in range(n)]
for _ 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())
d=[-1]*n
def f(k,c):
    d[k]=c
    for i,v in g[k]:
        if d[i]==-1:
            f(i,c+v)
f(k-1,0)
for _ 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 _ in range(n)]
for _ 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())
d=[-1]*n
def f(k,c):
    d[k]=c
    for i,v in g[k]:
        if d[i]==-1:
            f(i,c+v)
f(k-1,0)
print(d)
for _ in range(q):
    x,y=map(int,input().split())
    print(d[x-1]+d[y-1])

Submission status: Runtime Error

Solution code:
#! /usr/bin/env python3
D = {}
L = []

def f(n):
    r = []
    s = 0
    while n in D:
        a, b = D[n]
        s += L[a]
        r = [(a, s)] + r
        n = b
    return r

def d(a, b):
    r = c = 0
    for i in range(min(len(a), len(b))):
        if a[i][0] == b[i][0]:
            c += 1
        else:
            break
    if len(a) : r += a[c][1]
    if len(b) : r += b[c][1]
    return r

def main():
    N = int(input())
    for i in range(N-1):
        a, b, c = map(int, input().split())
        D[b] = (i, a)
        L.append(c)
    Q, K = map(int, input().split())
    k = f(K)
    for i in range(Q):
        x, y = map(int, input().split())
        print(d(f(x), k) + d(f(y), k))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

def f(diu, n):
    r = []
    while n != 1:
        r = [diu[n][0]] + r
        n = diu[n][1]
    return r

def d(p, a, b):
    c = 0
    for i, j in zip(a, b):
        if i == j:
            c += 1
        else:
            break
    return sum(p[x][2] for x in a[c:]) + sum(p[x][2] for x in b[c:])

def main():
    N = int(input())
    P = [tuple(map(int, input().split())) for x in range(N-1)]
    diu = {max(v[0], v[1]) : (i, min(v[0], v[1]))  for i, v in enumerate(P)}
    M, K = map(int, input().split())
    XY = [tuple(map(int, input().split())) for x in range(M)]
    k = f(diu, K)
    for x, y in XY:
        print(d(P, f(diu, x), k) + d(P, f(diu, y), k))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#! /usr/bin/env python3
D = {}
L = []

def f(n):
    r = []
    while n != '1':
        r = [D[n][0]] + r
        n = D[n][1]
    return r

def d(a, b):
    c = 0
    for i, j in zip(a, b):
        if i == j:
            c += 1
        else:
            break
    return sum(L[x] for x in a[c:]) + sum(L[x] for x in b[c:])

def main():
    global D, L
    N = int(input())
    P = [input().split() for x in range(N-1)]
    L = [int(x[2]) for x in P]
    D = {P[x][1] : (x, P[x][0])  for x in range(N-1)}
    M, K = input().split()
    XY = [input().split() for x in range(int(M))]
    k = f(K)
    for x, y in XY:
        print(d(f(x), k) + d(f(y), k))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

def f(diu, n):
    r = []
    while n != 1:
        r = [diu[n][0]] + r
        n = diu[n][1]
    return r

def d(p, a, b):
    c = 0
    for i, j in zip(a, b):
        if i == j:
            c += 1
        else:
            break
    return sum(p[x][2] for x in a[c:]) + sum(p[x][2] for x in b[c:])

def main():
    N = int(input())
    P = [tuple(map(int, input().split())) for x in range(N-1)]
    diu = {v[1] : (i, v[0])  for i, v in enumerate(P)}
    M, K = map(int, input().split())
    XY = [tuple(map(int, input().split())) for x in range(M)]
    k = f(diu, K)
    # for x, y in XY:
    #     print(d(P, f(diu, x), k) + d(P, f(diu, y), k))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

def f(diu, n):
    r = []
    while n != 1:
        r = [diu[n][0]] + r
        n = diu[n][1]
    return r

def d(p, a, b):
    c = 0
    for i, j in zip(a, b):
        if i == j:
            c += 1
        else:
            break
    return sum(p[x][2] for x in a[c:]) + sum(p[x][2] for x in b[c:])

def main():
    N = int(input())
    P = [tuple(map(int, input().split())) for x in range(N-1)]
    diu = {v[1] : (i, v[0])  for i, v in enumerate(P)}
    M, K = map(int, input().split())
    XY = [tuple(map(int, input().split())) for x in range(M)]
    k = f(diu, K)
    for x, y in XY:
        print(d(P, f(diu, x), k) + d(P, f(diu, y), k))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

def f(diu, n):
    r = []
    while n != 1:
        r = [diu[n][0]] + r
        n = diu[n][1]
    return r

def d(p, a, b):
    c = 0
    for i, j in zip(a, b):
        if i == j:
            c += 1
        else:
            break
    return sum(p[x][2] for x in a[c:] + b[c:])

def main():
    N = int(input())
    P = [tuple(map(int, input().split())) for x in range(N-1)]
    diu = {v[1] : (i, v[0])  for i, v in enumerate(P)}
    M, K = map(int, input().split())
    XY = [tuple(map(int, input().split())) for x in range(M)]
    k = f(diu, K)
    for x, y in XY:
        print(d(P, f(diu, x), k) + d(P, f(diu, y), k))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

def f(diu, n):
    r = []
    while n != 1:
        r += [diu[n][0]]
        n = diu[n][1]
    return r[::-1]
    
def d(p, a, b):
    c = 0
    for i, j in zip(a, b):
        if i == j:
            c += 1
        else:
            break
    return sum(p[x][2] for x in a[c:] + b[c:])

N = int(input())
P = [tuple(map(int, input().split())) for x in range(N-1)]
diu = {v[1] : (i, v[0])  for i, v in enumerate(P)}
M, K = map(int, input().split())
XY = [tuple(map(int, input().split())) for x in range(M)]
k = f(diu, K)
for x, y in XY:
    print(d(P, f(diu, x), k) + d(P, f(diu, y), k))

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

distance = [-1]*(N+1)
# def add_weight(k, pre):
#     for v in edges[k]:
#         d, w = v
#         if d != pre:
#             distance[d] = w + distance[k]
#             add_weight(d, k)
# add_weight(K, -1)
que = deque()
que.append(edges[K]); distance[K] = 0
while len(que):
    a = que.popleft()
    for b, c in a:
        if distance[b] == -1:
            distance[b] = c
            que.append(edges[b])

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

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:
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, 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 q in queries:
    s, e = q
    print(weighted_nodes[s] + weighted_nodes[e])