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
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, q = map(int, input().split())
edges = [[] for _ in range(n)]

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

count = [0]*n
for i in range(q):
    p, x = map(int, input().split())
    count[p-1] += x


def dfs(v, parent):
    for v2 in edges[v]:
        if v2 == parent:
            continue
        count[v2] += count[v]
        dfs(v2, v)


dfs(0, None)
print(*count)

Submission status: Runtime Error

Solution code:
"""
--- アルゴリズム概要 ---
前計算で頂点Kから各ノードへの最短路を記録しておき、
各クエリに対しては、dp[a]+dp[b]を返せばよい。

頂点Kから各ノードへの最短ルートはdfsとかで記録していけばよい。
"""

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

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

path = {K:""}
dp = [0]*(N+1)
def dfs(n,cost):
    path[n]=""
    dp[n]=cost
    for i,c in AB[n].items():
        if i not in path:
            dfs(i,cost+c)
dfs(K,0)
for i in range(Q):
    x,y=map(int,input().split())
    print(dp[x]+dp[y])

Submission status: Runtime Error

Solution code:
"""
---アルゴリズム概要---
閉路のないグラフなので、シンプルにxからKまでまっすぐに進んでから、Kからyにまっすぐ進むことを考えればよい。
クエリの数Qが10**5個あるので、ノードaからノードbにまっすぐ進む場合のコストをメモしていくのがよさそう。

次に、どうやってノードaからノードbへの「まっすぐ進む道」＝「まっすぐ進むための次のノード」を判断するかだが、
これは、ノードaが直接つながっているノードのうち、
ノードbへのコストが最も少ないものがまっすぐ進むための次のノードとなる。
"""

N = int(input())
edges = [{} for _ in range(N)]
#dpでiからjへの最短コストを管理する。
for _ in range(N-1):
    a,b,c = map(int,input().split())
    edges[a-1][b]=c
    edges[b-1][a]=c

Q,K = map(int,input().split())
dp = [float("INF")]*(N)

path = {}
def dfs(i,c):
    dp[i-1]=c
    path[i]=""
    for n,cost in edges[i-1].items():
        if n not in path:
            dfs(n, c + cost)

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

Submission status: Runtime Error

Solution code:
from sys import stdin
from collections import defaultdict
N = int(stdin.readline().rstrip())
adj = defaultdict(set)

for i in range(N-1):
    a,b,c = [int(x) for x in stdin.readline().rstrip().split()]
    adj[a].add((b,c))
    adj[b].add((a,c))
    
Q,K = [int(x) for x in stdin.readline().rstrip().split()]

visited = [False]*(N+1)
dist = [0]*(N+1)

def dfs(i,j):
    if visited[i]:
        return
    dist[i] = j
    visited[i] = True
    
    for node,d in adj[i]:
        dfs(node,d+j)
        
dfs(K,0)

for i in range(Q):
    x,y = [int(x) for x in stdin.readline().rstrip().split()]
    print(dist[x]+dist[y])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

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

nim, mike = list(map(int, input().split()))

queue = [mike-1]
dist = [None]*data
dist[K-1] = 0
while queue:
  queue_new = []
  for q in queue:
    for e in E[q]:
      if dist[e[0]] is not None: continue
      dist[e[0]] = dist[q] + e[1]
      queue_new.append(e[0])
  queue = queue_new

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

Submission status: Runtime Error

Solution code:
#tempt

n=int(input())
a=[]
b=[]
c=[]
tree=[[] for j in range(n)]
for i in range(n-1):
    d,e,f=map(int,input().split())
    tree[d-1].append([e-1,f])
    tree[e-1].append([d-1,f])

x=[]
y=[]

q,k=map(int,input().split())
for i in range(q):
    a,b=map(int,input().split())
    x.append(a)
    y.append(b)

ans=[0]*n

def dfs(start):

Submission status: Runtime Error

Solution code:
N = int(input())
ABC = [list(map(int, input().split())) for i in range(N-1)]
Q, K = map(int, input().split())
D = [0] * (N+1)
L = [[] for i in range(N+1)]
for a, b, c in ABC:
    L[a].append([b, c])
    L[b].append([a, c])
 
 
def dfs(n, np):
    for nc in L[n]:
        if nc[0] == np:
            continue
        else:
            D[nc[0]] = D[n] + nc[1]
            dfs(nc[0], n)
 
 
dfs(K, 0)
for i in range(Q):
    x, y = map(int, input().split())
    print(D[x] + D[y])

Submission status: Runtime Error

Solution code:
N = int(input())
graph = [[] for _ in range(N+1)] #木構造を入れておく
long = [0] * (N+1) #Kから任意のノードまでの距離

for i in range(N-1):
  x, y, z = map(int, input().split())
  graph[x].append([y, z])
  graph[y].append([x, z])
  
Q, K = map(int, input().split())
def dfs(n, num):
    for t in graph[n]:
        if t[0] == num:
            continue
        else:
            long[t[0]] = long[n] + t[1]
            dfs(t[0], n)
 
 
dfs(K, 0)

for i in range(Q):
  x_i, y_i = map(int, input().split())
  ans = long[x_i] + long[y_i]
  print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
graph = [[] for _ in range(N+1)] #木構造を入れておく
long = [0] * (N+1) #Kから任意のノードまでの距離

for i in range(N-1):
  x, y, z = map(int, input().split())
  graph[x].append([y, z])
  graph[y].append([x, z])
  
Q, K = map(int, input().split())
x = list()
y = list()

for i in range(Q):
  x_i, y_i = map(int, input().split())
  x.append(x_i)
  y.append(y_i)

       
def dfs(n, np):
    for nc in graph[n]:
        if nc[0] == np:
            continue
        else:
            long[nc[0]] = long[n] + nc[1]
            dfs(nc[0], n)
 
 
dfs(K, 0)

for i in range(Q):
  ans = long[x[i]] + long[y[i]]
  print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
list_ABC = [list(map(int, input().split())) for i in range(n - 1)]
q, k = map(int, input().split())
list_XY = [ list(map(int,input().split(" "))) for i in range(q)]
D = [0] * (n + 1)
L = [[] for i in range(n + 1)]
for a, b, c in list_ABC:
    L[a].append([b, c])
    L[b].append([a, c])

def dfs(n, np):
    for ne in L[n]:
        if ne[0] == np:
            continue
        else:
            D[ne[0]] = D[n] + ne[1]
            dfs(ne[0], n)

dfs(k, 0)

for x, y in list_XY:
    print(D[x]+D[y])

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

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

ma = [[0]*n for _ in range(n)]
for a, b, c in list_ABC:
    ma[a-1][b-1] = c
    ma[b-1][a-1] = c

a = csr_matrix(ma)
b = shortest_path(a, directed=False).astype(int)

for x, y in list_XY:
    print(b[x-1,k-1]+b[k-1,y-1])

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

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

ma = np.zeros((n,n), dtype=np.int16)
for a, b, c in list_ABC:
    ma[a-1, b-1] = c
    ma[b-1, a-1] = c

a = csr_matrix(ma)
b = dijkstra(a, directed=False).astype(int)

for x, y in list_XY:
    print(b[x-1, k-1]+b[k-1, y-1])

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

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

ma = np.zeros((n,n))
for a, b, c in list_ABC:
    ma[a-1, b-1] = c
    ma[b-1, a-1] = c

a = csr_matrix(ma)
b = dijkstra(a, directed=False).astype(int)

for x, y in list_XY:
    print(b[x-1, k-1]+b[k-1, y-1])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
n = int(input())

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

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

# k からの距離を求める
dist = [-1 for _ in range(n+1)]
is_checked = [False for _ in range(n+1)]
def dfs(num, cur_dist):
    for next_num, d in edges[num]:
        if not is_checked[next_num]:
            is_checked[next_num] = True
            dist[next_num] = cur_dist+d
            dfs(next_num, cur_dist+d)
dist[k] = 0
is_checked[k] = True
dfs(k, 0)
# print(dist)
ans = []
for _ in range(q):
    x, y = map(int, input().split())
    ans.append(str(dist[x] + dist[y]))
print("\n".join(ans))

Submission status: Runtime Error

Solution code:
import sys
from heapq import heappush, heappop, heappushpop, heapify, heapreplace
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt
INF = 1 << 60
sys.setrecursionlimit(10 ** 6)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
            v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
            
        for j in range(n):
            d[j] = min(d[j],d[v]+cost[v][j])
    return d


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

#ここから書き始める
n = int(input())
cost = [[INF for i in range(n)] for i in range(n)] 
for i in range(n - 1):
    a, b, c = map(int, input().split())
    cost[a - 1][b - 1] = c
    cost[b - 1][a - 1] = c
q, k = map(int, input().split())   
ans = [0] * q
to_k = [0] * n
to_y = [0] * n
for i in range(n):
    to_k[i] = dijkstra(i, n, n - 1, cost)[k - 1]
    to_y[i] = dijkstra(k - 1, n, n - 1, cost)[i]
for i in range(q):
    x, y = map(int, input().split())
    ans[i] = to_k[x - 1] + to_y[y - 1]
for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
from heapq import heapify, heappush, heappop

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

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

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

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

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

d[K] = 0
dfs(K, 0)

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

Submission status: Runtime Error

Solution code:
N = int(input())
abc=[]
for _ in range(N-1):
    abc.append(tuple(map(int, input().split())))
Q, K = map(int, input().split())
xy=[]
for _ in range(Q):
    xy.append(tuple(map(int, input().split())))
#print(abc)
#print(xy)

G = [[] for _ in range(N+1)]
for el in abc:
    a,b,c = el
    G[a].append((b,c))
    G[b].append((a,c))
#print(G)

seen=[False]*(N+1)
distance=[0]*(N+1)
def dfs(n):
    seen[n]=True
    for el in G[n]:
        if seen[el[0]] == False:
            distance[el[0]] = distance[n] + el[1]
            dfs(el[0])
dfs(K)
#print(distance)

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

Submission status: Runtime Error

Solution code:
n= int(input())
branchdict = {}
for i in range(n-1):
    a,b,c= map(int,input().split())
    branchdict[a-1] = branchdict.get(a-1,[]) + [(b-1,c)]
    branchdict[b-1] = branchdict.get(b-1,[]) + [(a-1,c)]
q,k= map(int,input().split())
cost = [0] * n
def dfs(curnode,pre,addcost):
    cost[curnode]=addcost
    if curnode in branchdict.keys():
        for abr in branchdict[curnode]:
            if abr[0]!=pre:
                dfs(abr[0],curnode,addcost+abr[1])
dfs(k-1,-1,0)
for i in range(q):
    x,y= map(int,input().split())
    print(cost[x-1]+cost[y-1])

Submission status: Runtime Error

Solution code:
n= int(input())
branchdict = {}
for i in range(n-1):
    a,b,c= map(int,input().split())
    branchdict[a-1] = branchdict.get(a-1,[]) + [(b-1,c)]
    branchdict[b-1] = branchdict.get(b-1,[]) + [(a-1,c)]
q,k= map(int,input().split())
cost = [0] * n
def dfs(curnode,pre,addcost):
    cost[curnode]=addcost
    passedf[curnode]=True
    if curnode in branchdict.keys():
        for abr in branchdict[curnode]:
            if abr[0]!=pre:
                dfs(abr[0],curnode,addcost+abr[1])
dfs(k-1,-1,0)
for i in range(q):
    x,y= map(int,input().split())
    print(cost[x-1]+cost[y-1])

Submission status: Runtime Error

Solution code:
n= int(input())
branchdict = {}
for i in range(n-1):
    a,b,c= map(int,input().split())
    branchdict[a-1] = branchdict.get(a-1,[]) + [(b-1,c)]
    branchdict[b-1] = branchdict.get(b-1,[]) + [(a-1,c)]
q,k= map(int,input().split())
passedf = [False] * n
cost = [0] * n
def dfs(curnode,addcost):
    cost[curnode]=addcost
    passedf[curnode]=True
    if curnode in branchdict.keys():
        for abr in branchdict[curnode]:
            if not passedf[abr[0]]:dfs(abr[0],addcost+abr[1])
dfs(k-1,0)
for i in range(q):
    x,y= map(int,input().split())
    print(cost[x-1]+cost[y-1])

Submission status: Runtime Error

Solution code:
n= int(input())
branchdict = {}
for i in range(n-1):
    a,b,c= map(int,input().split())
    branchdict[a-1] = branchdict.get(a-1,[]) + [(b-1,c)]
    branchdict[b-1] = branchdict.get(b-1,[]) + [(a-1,c)]
q,k= map(int,input().split())
passed = set()
cost = [0] * n
def dfs(curnode,addcost):
    cost[curnode]=addcost
    passed.add(curnode)
    for abr in branchdict[curnode]:
        if not abr[0] in passed:dfs(abr[0],addcost+abr[1])
dfs(k-1,0)
for i in range(q):
    x,y= map(int,input().split())
    print(cost[x-1]+cost[y-1])

Submission status: Runtime Error

Solution code:
n = int(input())

es=[[] for _ in range(n)] # es[i] = (頂点iの(隣接する頂点,コスト)の組)
d = [0]*n # 頂点sからの最短距離
used=[True]*n
# 入力
for i in range(n-1):
    a,b,c = map(int,input().split())
    a,b = a-1, b-1
    es[a].append((b,c))
    es[b].append((a,c))


def dfs(s,dist):
    used[s]=False
    for v,x in es[s]:
        if used[v]:
            d[v]=dist+x
            dfs(v,dist+x)
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())

es=[[] for _ in range(n)] # es[i] = (頂点iの(隣接する頂点,コスト)の組)
d = [0]*n # 頂点sからの最短距離
used=[True]*n
# 入力
for i in range(n-1):
    a,b,c = map(int,input().split())
    a,b = a-1, b-1
    es[a].append((b,c))
    es[b].append((a,c))


def dfs(s,dist):
    used[s]=False
    for v,x in es[s]:
        if used[v]:
            d[v]=dist+x
            dfs(v,dist+x)
q,k=map(int,input().split())
dfs(k-1,0)
print(d)
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())
T, D = {i: [] for i in range(N)}, [-1] * N
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    T[a - 1].append((b - 1, c))
    T[b - 1].append((a - 1, c))


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


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

Submission status: Runtime Error

Solution code:
import sys
rline = sys.stdin.readline

N = int(rline())
graph = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b, c = map(int, rline().split())
    a -= 1
    b -= 1
    graph[a].append([b, c])
    graph[b].append([a, c])
to_k = [0] * N


def dfs(node, parent, dist):
    to_k[node] = dist
    
    for child, d in graph[node]:
        if child != parent:
            dfs(child, node, dist + d)


def solve():
    Q, K = map(int, rline().split())
    K -= 1
    dfs(K, -1, 0)
    for _ in range(Q):
        x, y = map(lambda z: int(z) - 1, rline().split())
        print(to_k[x] + to_k[y])


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

N = int(input())

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

for _ 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())
xy = []
for _ in range(Q):
    xy.append(tuple(map(int, input().split())))

d = [-1 for _ in range(N+1)]


def dfs(s: int):
    for v, c in g[s]:
        if d[v] == -1:
            d[v] = d[s] + c
            dfs(v)


d[K] = 0
dfs(K)

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

N = int(input())

edges = {n: [] for n in range(N+1)}

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

    edges[a].append((b, c))
    edges[b].append((a, c))

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


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


def dfs(n: int):
    for m, c in edges[n]:
        if d[m] == -1:
            d[m] = d[n] + c
            dfs(m)


dfs(K)

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(20000)

N = int(input())

edges = {n: [] for n in range(N+1)}

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

    edges[a].append((b, c))
    edges[b].append((a, c))

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


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


def dfs(n: int):
    for m, c in edges[n]:
        if d[m] == -1:
            d[m] = d[n] + c
            dfs(m)


dfs(K)

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

N = int(input())

edges = {n: [] for n in range(N+1)}

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

    edges[a].append((b, c))
    edges[b].append((a, c))

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


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


def dfs(n: int):
    for m, c in edges[n]:
        if d[m] == -1:
            d[m] = d[n] + c
            dfs(m)


dfs(K)

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

Submission status: Runtime Error

Solution code:
sys.setrecursionlimit(10000)

N = int(input())

edges = {n: [] for n in range(N+1)}

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

    edges[a].append((b, c))
    edges[b].append((a, c))

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


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


def dfs(n: int):
    for m, c in edges[n]:
        if d[m] == -1:
            d[m] = d[n] + c
            dfs(m)


dfs(K)

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

Submission status: Runtime Error

Solution code:
N = int(input())

edges = {n: [] for n in range(N+1)}

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

    edges[a].append((b, c))
    edges[b].append((a, c))

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


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


def dfs(n: int):
    for m, c in edges[n]:
        if d[m] == -1:
            d[m] = d[n] + c
            dfs(m)

dfs(K)

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

Submission status: Runtime Error

Solution code:
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

Submission status: Runtime Error

Solution code:
from collections import defaultdict
def main():
    N = int(input())
    depth = [0 for _ in range(N)]
    tree = defaultdict(list)

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

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

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
def main():
    N = int(input())
    depth = [0 for _ in range(N)]
    def dfs(v,p,d):
        depth[v] = d
        if tree[v]:
            for u in tree[v]:
                if u[0] == p:continue
                dfs(u[0],v,d+u[1])
    tree = defaultdict(list)
    for _ in range(N-1):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        tree[a] += [[b,c]]
        tree[b] += [[a,c]]
    Q,K = map(int,input().split())
    K -= 1
    dfs(K,-1,0)
    for _ in range(Q):
        x,y = map(int,input().split())
        x -= 1
        y -= 1
        ans = depth[x]+depth[y]
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
def main():
    N = int(input())
    depth = [0 for _ in range(N)]
    def dfs(v,p,d):
        depth[v] = d
        for u in tree[v]:
            if u[0] == p:continue
            dfs(u[0],v,d+u[1])
    tree = defaultdict(list)
    for _ in range(N-1):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        tree[a] += [[b,c]]
        tree[b] += [[a,c]]
    Q,K = map(int,input().split())
    K -= 1
    dfs(K,-1,0)
    for _ in range(Q):
        x,y = map(int,input().split())
        x -= 1
        y -= 1
        ans = depth[x]+depth[y]
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
depth = [0 for _ in range(10**5+10)]
tree = defaultdict(list)
def dfs(v,p,d):
    depth[v] = d
    for u in tree[v]:
        if u[0] == p:continue
        dfs(u[0],v,d+u[1])
def main():
    N = int(input())
    for _ in range(N-1):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        tree[a] += [[b,c]]
        tree[b] += [[a,c]]
    Q,K = map(int,input().split())
    K -= 1
    dfs(K,-1,0)
    Ans = []
    for _ in range(Q):
        x,y = map(int,input().split())
        x -= 1
        y -= 1
        ans = depth[x]+depth[y]
        Ans.append(ans)
    for ans in Ans:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
def main():
    N = int(input())
    depth = [0 for _ in range(N)]
    def dfs(v,p,d):
        depth[v] = d
        for u in tree[v]:
            if u[0] == p:continue
            dfs(u[0],v,d+u[1])
    tree = defaultdict(list)
    for _ in range(N-1):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        tree[a] += [[b,c]]
        tree[b] += [[a,c]]
    Q,K = map(int,input().split())
    K -= 1
    dfs(K,-1,0)
    Ans = []
    for _ in range(Q):
        x,y = map(int,input().split())
        x -= 1
        y -= 1
        ans = depth[x]+depth[y]
        Ans.append(ans)
    for ans in Ans:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

def d(tree, array, v):
  next_v = tree.get(v)
  
  for nv, nd in next_v:
    if array[nv] == -1:
      array[nv] = array[v] + nd
      d(tree, array, nv)
  

n = int(input())
tree = {}

for i in range(n-1):
  a,b,c = map(int, input().split())
  a -= 1
  b -= 1
  
  array = tree.get(a, [])
  array.append((b,c))
  tree[a] = array
  
  array = tree.get(b, [])
  array.append((a,c))
  tree[b] = array
  
q,k = map(int, input().split())
k -= 1

array = [-1] * n
array[k] = 0

d(tree, array, k)

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

Submission status: Runtime Error

Solution code:
def d(tree, array, v):
  next_v = tree.get(v)
  
  for nv, nd in next_v:
    if array[nv] == -1:
      array[nv] = array[v] + nd
      d(tree, array, nv)
  

n = int(input())
tree = {}

for i in range(n-1):
  a,b,c = map(int, input().split())
  a -= 1
  b -= 1
  
  array = tree.get(a, [])
  array.append((b,c))
  tree[a] = array
  
  array = tree.get(b, [])
  array.append((a,c))
  tree[b] = array
  
q,k = map(int, input().split())
k -= 1

array = [-1] * n
array[k] = 0

d(tree, array, k)

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

Submission status: Runtime Error

Solution code:
N = int(input())
tree = {i:{} for i in range(1,1+N)}
for i in range(N-1):
    a,b,c = map(int, input().split())
    tree[a][b] = c
    tree[b][a] = c
#print(tree)
Q, K = map(int, input().split())

#Kから各点までの距離を求めていく
k_dst = {K:0}

def p_dist(node, dist):
    if len(tree[node]) == 0:
        k_dst[node] = dist
        #print("k_dst %d : %d"%(node,dist))
    while len(tree[node]) != 0:
        i = list(tree[node].keys())[0]
        c = tree[node][i]
        p = tree[node].pop(i)
        p = tree[i].pop(node)
        k_dst[i] = dist + c
        p_dist(i, dist + c)
        #print("k_dst %d : %d"%(i,k_dst[i]))

p_dist(K,0)

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

Submission status: Runtime Error

Solution code:
N = int(input())
tree = {i:{} for i in range(1,1+N)}
for i in range(N-1):
    a,b,c = map(int, input().split())
    tree[a][b] = c
    tree[b][a] = c
#print(tree)
Q, K = map(int, input().split())

#Kから各点までの距離を求めていく
k_dst = {K:0}

def p_dist(node, dist):
    if len(tree[node]) == 0:
        k_dst[node] = dist
        #print("k_dst %d : %d"%(node,dist))
    while len(tree[node]) != 0:
        i = list(tree[node].keys())[0]
        c = tree[node][i]
        del tree[node][i]
        del tree[i][node]
        k_dst[i] = dist + c
        p_dist(i, dist + c)
        #print("k_dst %d : %d"%(i,k_dst[i]))

p_dist(K,0)

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

Submission status: Runtime Error

Solution code:
N = int(input())
tree = {i:{} for i in range(1,1+N)}
for i in range(N-1):
    a,b,c = map(int, input().split())
    tree[a][b] = c
    tree[b][a] = c
#print(tree)
Q, K = map(int, input().split())

#Kから各点までの距離を求めていく
k_dst = {}

def p_dist(node, dist):
    if len(tree[node]) == 0:
        k_dst[node] = dist
        #print("k_dst %d : %d"%(node,dist))
    while len(tree[node]) != 0:
        i = list(tree[node].keys())[0]
        c = tree[node][i]
        del tree[node][i]
        del tree[i][node]
        k_dst[i] = dist + c
        p_dist(i, dist + c)
        #print("k_dst %d : %d"%(i,k_dst[i]))

p_dist(K,0)

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

Submission status: Runtime Error

Solution code:
N = int(input())
tree = {i:{} for i in range(1,1+N)}
for i in range(N-1):
    a,b,c = map(int, input().split())
    tree[a][b] = c
    tree[b][a] = c
#print(tree)
Q, K = map(int, input().split())
Q_list = []
for i in range(Q):
    x,y = map(int, input().split())
    Q_list.append([x,y])

#Kから各点までの距離を求めていく
k_dst = {}

def p_dist(node, dist):
    if len(tree[node]) == 0:
        k_dst[node] = dist
        #print("k_dst %d : %d"%(node,dist))
    while len(tree[node]) != 0:
        i = list(tree[node].keys())[0]
        c = tree[node][i]
        del tree[node][i]
        del tree[i][node]
        k_dst[i] = dist + c
        p_dist(i, dist + c)
        #print("k_dst %d : %d"%(i,k_dst[i]))

p_dist(K,0)

for i in range(Q):
    x = Q_list[i][0]
    y = Q_list[i][1]
    print(k_dst[x]+k_dst[y])