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())
d=[-1 for _ in range(N+1)]
e=[[] for _ in range(N+1)]
for _ in range(N-1):
	a,b,c=map(int,input().split())
	e[a].append([b, c])
	e[b].append([a, c])
Q,K=map(int,input().split())
def bfs(now, dis):
	if d[now] != -1:
		return
	d[now] = dis
	for nxt, cos in e[now]:
		bfs(nxt, dis+cos)
bfs(K, 0)
for _ in range(Q):
	x,y=map(int,input().split())
	print(d[x]+d[y])

Submission status: Runtime Error

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

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

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

L[K]=0

def dfs(x):
    for i in n[x]:
        if L[i[0]]==-1:
            L[i[0]]=L[x]+i[1]
            dfs(i[0])
dfs(K)
#print(n)
#print(L)

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
li = [[] for i in range(n)]

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

q,k = map(int,input().split())
tdp = [-1]*n
tdp[k-1] = 0

def dfs(x):
  for node in li[x]:
    if tdp[node[0]] == -1:
      tdp[node[0]] = tdp[x] + node[1]
      dfs(node[0])

dfs(k-1)
for i in range(q):
  a,b = map(int,input().split())
  print(tdp[a-1]+tdp[b-1])

Submission status: Runtime Error

Solution code:
n = int(input())
abc = [[int(item) for item in input().split()] for _ in range(n-1)]
q, k = [int(item) for item in input().split()]
xy = [[int(item) for item in input().split()] for _ in range(q)]

distance = [0] * n
e = [[] for _ in range(n)]
w = [[] for _ in range(n)]
for a, b, c in abc:
    e[a-1].append(b-1)
    e[b-1].append(a-1)
    w[a-1].append(c)
    w[b-1].append(c)

def dfs(v, par, dist):
    distance[v] = dist
    if len(e[v]) == 0:
        return True
    for i in range(len(e[v])):
        if e[v][i] == par:
            continue
        dfs(e[v][i], v, dist + w[v][i])

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

Submission status: Runtime Error

Solution code:
from collections import deque

def main()
    n=int(input())
    l=[0]*n
    d={}
    for i in range(n-1):
        a,b,c=map(int,input().split())
        a-=1
        b-=1
        if a in d:
            d[a].add((b,c))
        else:
            d[a]={(b,c)}
        if b in d:
            d[b].add((a,c))
        else:
            d[b]={(a,c)}
    q,k=map(int,input().split())
    k-=1
    p=deque([k])
    while len(p):
        w=p.popleft()
        for i in d[w]:
            if (l[i[0]]==0 and i[0]!=k) or (l[i[0]]!=0 and l[i[0]]>l[w]+i[1]):
                l[i[0]]=l[w]+i[1]
                p.append(i[0])

    for i in range(q):
        x,y=map(int,input().split())
        print(l[x-1]+l[y-1])
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main()
    n=int(input())
    l=[0]*n
    d={}
    for i in range(n-1):
        a,b,c=map(int,input().split())
        a-=1
        b-=1
        if a in d:
            d[a].add((b,c))
        else:
            d[a]={(b,c)}
        if b in d:
            d[b].add((a,c))
        else:
            d[b]={(a,c)}
    q,k=map(int,input().split())
    k-=1
    p=deque([k])
    while len(p):
        w=p.popleft()
        for i in d[w]:
            if (l[i[0]]==0 and i[0]!=k) or (l[i[0]]!=0 and l[i[0]]>l[w]+i[1]):
                l[i[0]]=l[w]+i[1]
                p.append(i[0])

    for i in range(q):
        x,y=map(int,input().split())
        print(l[x-1]+l[y-1])
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
n=int(input())
l=[0]*n
d={}
for i in range(n-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    if a in d:
        d[a].add((b,c))
    else:
        d[a]={(b,c)}
    if b in d:
        d[b].add((a,c))
    else:
        d[b]={(a,c)}
q,k=map(int,input().split())
k-=1
p=deque([k])
while len(p):
    w=p.popleft()
    for i in d[w]:
        if (l[i[0]]==0 and i[0]!=k) or (l[i[0]]!=0 and l[i[0]]>l[w]+l[i[1]]):
            print(i)
            l[i[0]]=l[w]+i[1]
            p.append(i[0])

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

Submission status: Runtime Error

Solution code:
from collections import deque

def solve1(rs, p, v, cost, costs):
    costs[v] = cost
    for e in rs[v]:
        if p == e[0]:
            continue
        solve1(rs, v, e[0], cost+e[1], costs)
    return costs

n = int(input())
rs = []
for i in range(n - 1):
    abc = input().split(' ')
    rs.append([int(x) for x in abc])
qk = input().split(' ')
q = int(qk[0])
k = int(qk[1])
qs = []
for i in range(q):
    xy = input().split(' ')
    qs.append([int(x) for x in xy])

edges = {}
for r in rs:
    if r[0] not in edges:
        edges[r[0]] = []
    edges[r[0]].append((r[1], r[2]))
    if r[1] not in edges:
        edges[r[1]] = []
    edges[r[1]].append((r[0], r[2]))

c = solve1(edges, -1, k, 0, {})

for query in qs:
    c1 = c[query[0]]
    c2 = c[query[1]]
    print(c1 + c2)

Submission status: Runtime Error

Solution code:
n=int(input())
s=[[]for i in range(n+1)]
g=[0]*(n+1)
h=[True]*(n+1)
for i in range(n-1):
    a,b,c=map(int,input().split())
    s[a].append([b,c])
    s[b].append([a,c])
def dfs(x):
    h[x]=False
    for i in s[x]:
        if h[i[0]]:
            g[i[0]]=g[x]+i[1]
            dfs(i[0])
q,k=map(int,input().split())
dfs(k)
for i in range(q):
    x,y=map(int,input().split())
    print(g[x]+g[y])

Submission status: Runtime Error

Solution code:
def distances(tree: list, treeSize: int, root: int)->list:
    dists = [0] * treeSize

    def dfs(v: int, prev: int,  dist: int):
        dists[v] = dist
        for u, c in tree[v]:
            if u == prev:
                continue
            dfs(u, v, dist+c)

    dfs(root, -1, 0)

    return dists


def transit_tree_path(
        N: int, edges: list, Q: int, K: int, queries: list)->list:
    tree = [[] for _ in range(N)]
    for u, v, c in edges:
        tree[u-1].append((v-1, c))
        tree[v-1].append((u-1, c))

    d = distances(tree, N, K-1)

    return [d[x-1]+d[y-1] for x, y in queries]


if __name__ == "__main__":
    N = int(input())
    edges = [tuple(map(int, input().split())) for _ in range(N-1)]
    Q = 0
    Q, K = map(int, input().split())
    queries = [tuple(map(int, input().split())) for _ in range(Q)]

    ans = transit_tree_path(N, edges, Q, K, queries)
    for a in ans:
        print(a)

Submission status: Runtime Error

Solution code:
import heapq
class edge:
    def __init__(self,to,cost):
        self.to=to
        self.cost=cost

N=int(input())
G=[list() for i in range(N)]
P=[False for i in range(N)]
A=[-100 for i in range(N)]
for i in range(N-1):
    a,b,c=map(int,input().split())
    G[a-1].append(edge(b-1,c))
    G[b-1].append(edge(a-1,c)) #無向グラフならこれも


def solve(G,K,P):
    P[K]=True
    for i in G[K]:
        if(P[i.to]):
            continue
        A[i.to]=A[K]+i.cost
        solve(G,i.to,P)

Q,K=map(int,input().split())
A[K-1]=0
solve(G,K-1,P)


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

Submission status: Runtime Error

Solution code:
n = int(input())
inf = float("inf")
road = [dict() for _ in range(n+1)]
for _ in range(n-1):
  a,b,c = map(int, input().split())
  road[a][b] = c
  road[b][a] = c
q,k = map(int, input().split())
dfs = [inf]*(n+1)
dfs[k] = 0
def dodfs(x):
  for i in road[x]:
    if dfs[i] == inf:
      dfs[i] = dfs[x] + road[x][i]
      dodfs(i)
  return   
dodfs(k)
for _ in range(q):
  x,y = map(int, input().split())
  print(dfs[x] + dfs[y])

Submission status: Runtime Error

Solution code:
n = int(input())
inf = float("inf")
road = [dict() for _ in range(n)]
for _ in range(n-1):
  a,b,c = map(int, input().split())
  road[a-1][b-1] = c
  road[b-1][a-1] = c
q,k = map(int, input().split())
dfs = [inf]*n
dfs[k-1] = 0

def dodfs(x):
  for i in road[x-1]:
    if dfs[i] == inf:
      dfs[i] = dfs[x-1] + road[x-1][i]
      dodfs(i)
  return
      
dodfs(k)
for _ in range(q):
  x,y = map(int, input().split())
  print(dfs[x-1] + dfs[y-1])

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

Solution code:
import collections as c
 
d=c.defaultdict(list)
n=int(input())
for s in range(n-1):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])
 
def DFS(point,d,cost,TFlist): #入力と同じindex系
    for s in d[point]:
        try:
            p=s[0]
            c=s[1]+cost[point]
            if TFlist[p-1]:
                continue
            cost[p]+=c
            TFlist[p-1]=1
            DFS(p,d,cost,TFlist)
        except RecursionError:
            continue
 
cost=[None]+[0 for i in range(n)]
q,k=map(int,input().split())
TFlist=[0 for i in range(n)]
TFlist[k-1]=1
DFS(k,d,cost,TFlist)
 
for t in range(q):
    a,b=map(int,input().split())
    print(cost[a]+cost[b])

Submission status: Runtime Error

Solution code:
import collections as c
 
d=c.defaultdict(list)
n=int(input())
for s in range(n-1):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])
 
def DFS(point,d,cost,TFlist): #入力と同じindex系
    for s in d[point]:
        try:
            p=s[0]
            c=s[1]+cost[point]
            if TFlist[p-1]:
                continue
            cost[p]+=c
            TFlist[p-1]=1
            DFS(p,d,cost,TFlist)
        except KeyError:
            continue
 
cost=[None]+[0 for i in range(n)]
q,k=map(int,input().split())
TFlist=[0 for i in range(n)]
TFlist[k-1]=1
DFS(k,d,cost,TFlist)
 
for t in range(q):
    a,b=map(int,input().split())
    print(cost[a]+cost[b])

Submission status: Runtime Error

Solution code:
import collections as c
 
d=c.defaultdict(list)
n=int(input())
for s in range(n-1):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])
 
def DFS(point,d,cost,TFlist): #入力と同じindex系
    for s in d[point]:
        try:
            p=s[0]
            c=s[1]+cost[point]
            if TFlist[p-1]:
                continue
            cost[p]+=c
            TFlist[p-1]=1
            DFS(p,d,cost,TFlist)
        except IndexError:
            continue
 
cost=[None]+[0 for i in range(n)]
q,k=map(int,input().split())
TFlist=[0 for i in range(n)]
TFlist[k-1]=1
DFS(k,d,cost,TFlist)
 
for t in range(q):
    a,b=map(int,input().split())
    print(cost[a]+cost[b])

Submission status: Runtime Error

Solution code:
import collections as c
 
d=c.defaultdict(list)
n=int(input())
for s in range(n-1):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])
 
def DFS(point,d,cost,TFlist): #入力と同じindex系
    for s in d[point]:
        p=s[0]
        c=s[1]+cost[point]
        if TFlist[p-1]:
            continue
        cost[p]+=c
        TFlist[p-1]=1
        DFS(p,d,cost,TFlist)
 
cost=[None]+[0 for i in range(n)]
q,k=map(int,input().split())
TFlist=[0 for i in range(n)]
TFlist[k-1]=1
DFS(k,d,cost,TFlist)
 
for t in range(q):
    a,b=map(int,input().split())
    print(cost[a]+cost[b])

Submission status: Runtime Error

Solution code:
import collections as c
 
d=c.defaultdict(list)
n=int(input())
for s in range(n-1):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])

def DFS(point,d,cost,TFlist): #入力と同じindex系
    for s in d[point]:
        p=s[0]
        c=s[1]+cost[point]
        if TFlist[p-1]:
            continue
        cost[p]+=c
        TFlist[p-1]=1
        DFS(p,d,cost,TFlist)
    return cost[point]

cost=[None]+[0 for i in range(n)]
q,k=map(int,input().split())
TFlist=[0 for i in range(n)]
TFlist[k-1]=1
DFS(k,d,cost,TFlist)

for t in range(q):
    a,b=map(int,input().split())
    print(cost[a]+cost[b])

Submission status: Runtime Error

Solution code:
import collections as c

d=c.defaultdict(list)
n=int(input())
for s in range(n-1):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])
#print(d)

    
def DFS(point,d,cost,TFlist): #入力と同じindex系
    if all(TFlist):
        return cost
    for s in d[point]:
        p=s[0]
        c=s[1]+cost[point]
        if TFlist[p-1]:
            continue
        cost[p]+=c
        TFlist[p-1]=1
      #  print(cost,TFlist)
        DFS(p,d,cost,TFlist)
    return cost[point]

cost=[None]+[0 for i in range(n)]
q,k=map(int,input().split())
TFlist=[0 for i in range(n)]
TFlist[k-1]=1
DFS(k,d,cost,TFlist)

for t in range(q):
    a,b=map(int,input().split())
    print(cost[a]+cost[b])

Submission status: Runtime Error

Solution code:
def dfs(n,p,d):
    visited[n] = True
    dist[n] = d
    for (i,c) in A[n]:
        if i != p and not visited[i]:
            dfs(i,n,d+c)

N = int(input())
A = [[] for _ in range(N)]
for _ 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())
B = []
for _ in range(Q):
    x,y = map(int,input().split())
    B.append((x,y))

dist = [-1]*N
visited = [False]*N
dfs(K-1,N,0)

for (x,y) in B:
    print(dist[x-1]+dist[y-1])

Submission status: Runtime Error

Solution code:
from collections import defaultdict

d=defaultdict(list)

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

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

# Kを中心とした距離を求める
dists=[None]*(N+1)
isused=[False]*(N+1)
dists[K]=0
isused[K]=True

def dfs(n):
    for i,j in d[n]:
        if isused[i]:continue
        isused[i]=True
        dists[i]=dists[n]+j
        dfs(i)

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

Submission status: Runtime Error

Solution code:
# D
N = int(input())
edge = [[] for _ in range(N)]
for _ in range(N):
    ai,bi,ci = map(int, input().split())
    edge[ai-1].append((bi-1, ci))
    edge[bi-1].append((ai-1, ci))
Q,K = map(int, input().split())
K = K-1
x,y = [],[]
for _ in range(Q):
    xi,yi = map(int, input().split())
    x.append(xi-1)
    y.append(yi-1)


dist = [float('inf')]*N # from K
visited = [False]*N
q = [K]
dist[K] = 0
visited[K] = True
while q:
    cur = q.pop()
    visited[cur] = True
    for nex,cost in edge[cur]:
        if not visited[nex]:
            q.append(nex)
            dist[nex] = dist[cur]+cost
#print(dist)
for xi,yi in zip(x,y):
    print(dist[xi] + dist[yi])

Submission status: Runtime Error

Solution code:
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()

n=I()
nl=[[] for i in range(n)]
used=[False for i in range(n)]
for i in range(n-1):
    a,b,c=IL()
    nl[a-1].append([b-1,c])
    nl[b-1].append([a-1,c])
d=[None for i in range(n)]
def dfs(now,pre,dis):
    used[now]=True
    d[now]=dis
    for i in nl[now]:
        if i[0]!=pre and not used[i[0]]:
            dfs(i[0],now,dis+i[1])
    
    return
q,k=IL()
dfs(k-1,-1,0)
for i in range(q):
    x,y=IL()
    print(d[x-1]+d[y-1])

Submission status: Runtime Error

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

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


def dfs(u, par, d):
    dist[u] = d
    for w, cost in G[u]:
        if w == par:
            continue
        dfs(w, u, d + cost)


dfs(K - 1, -1, 0)

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:
import sys
sys.setrecursionlimit(10 ** 10)


class Solve():
    def __init__(self):
        self.N = int(input())
        self.route = [dict() for _ in range(self.N)]
        for _ in range(self.N - 1):
            a, b, c = map(int, input().split())
            self.route[a - 1][b - 1] = c
            self.route[b - 1][a - 1] = c
        self.Q, self.K = map(int, input().split())
        self.K -= 1
        self.query = []
        for _ in range(self.Q):
            x, y = map(int, input().split())
            self.query.append([x - 1, y - 1])
        self.depth = [0 for _ in range(self.N)]

    def DFS(self, v, p, d):
        self.depth[v] = d
        for dest, cost in self.route[v].items():
            if dest == p:
                continue
            self.DFS(dest, v, d + cost)

    def execute(self):
        self.DFS(self.K, -1, 0)
        for x, y in self.query:
            print(self.depth[x] + self.depth[y])


if __name__ == '__main__':
    Solve().execute()

Submission status: Runtime Error

Solution code:
class Solve():
    def __init__(self):
        self.N = int(input())
        self.route = [dict() for _ in range(self.N)]
        for _ in range(self.N - 1):
            a, b, c = map(int, input().split())
            self.route[a - 1][b - 1] = c
            self.route[b - 1][a - 1] = c
        self.Q, self.K = map(int, input().split())
        self.K -= 1
        self.query = []
        for _ in range(self.Q):
            x, y = map(int, input().split())
            self.query.append([x - 1, y - 1])
        self.depth = [float('inf') for _ in range(self.N)]

    def DFS(self, v, p, d):
        self.depth[v] = d
        for dest, cost in self.route[v].items():
            if dest == p:
                continue
            self.DFS(dest, v, d + cost)

    def execute(self):
        self.DFS(self.K, -1, 0)
        for x, y in self.query:
            print(self.depth[x] + self.depth[y])


if __name__ == '__main__':
    ans = Solve()
    ans.execute()

Submission status: Runtime Error

Solution code:
n=int(input())
TREE=[[] for _ in range(n)]
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
cost=[0]*n
visited=[False]*n

def DFS(s,d):
    cost[s]=d
    visited[s]=True
    for i in TREE[s]:
        if not visited[i[0]]:
            DFS(i[0],d+i[1])
    return

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

Submission status: Runtime Error

Solution code:
n=int(input())
TREE=[[] for _ in range(n)]
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
depth=[0]*n
visited=[False for _ in range(n)]

def DFS(s,d):
    depth[s]=d
    visited[s]=True
    for i in TREE[s]:
        if not visited[i[0]]:
            DFS(i[0],d+i[1])
    return

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

Submission status: Runtime Error

Solution code:
n=int(input())
TREE=[[] for _ in range(n)]
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
depth=[0]*n
visited=[False for i in range(n)]

def DFS(s,d):
    depth[s]=d
    visited[s]=True
    for i in TREE[s]:
        if not visited[i[0]]:
            DFS(i[0],d+i[1])
    return

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

Submission status: Runtime Error

Solution code:

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

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

depth = [0 for _ in range(N)]

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

dfs(K)

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 個の頂点、N-1 個の辺なので K を根にした木構造に変換する

N = int(input())
T = {}
D = [None] * N
F = [True] * N

for n in range(N):
    T[n] = []

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

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

K -= 1

D[K] = 0
F[K] = False

L = [K]

while len(L) > 0:
    L_tmp = []
    for k in L:
        for t in T[k]:
            b, c = t
            if F[b] == True:
                D[b] = D[k] + c
                F[b] = False
                L_tmp.append(b)
    L = L_tmp

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

Submission status: Runtime Error

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


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


def dfs(v, c):
    d[v] = c
    for nv, cost in G[v]:
        if d[nv] == -1:
            dfs(nv, cost+c)

dfs(K, 0)

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

Submission status: Runtime Error

Solution code:
n = int(input())
# [[[ノード1, 距離3],[ノード3, 距離5]],[],...]
tree = [[] for _ in range(n+10)]
visited = [-1 for _ in range(n+10)]
# abc = [[0, 0, 0] for _ in range(n)]
for i in range(n-1):
    a, b, c = [int(j) for j in input().split()]
    tree[a - 1].append([b - 1, c])
    tree[b - 1].append([a - 1, c])
def depth(now, cost):
    visited[now] = cost
    for i in range(len(tree[now])):
        if visited[tree[now][i][0]] == -1:
            depth(tree[now][i][0], cost+tree[now][i][1])
    return
q, k = [int(i) for i in input().split()]
depth(k - 1, 0)
# print(visited)
for _ in range(q):
    x, y = [int(i) - 1 for i in input().split()]
    print(visited[x] + visited[y])

Submission status: Runtime Error

Solution code:
n = int(input())
# [[[ノード1, 距離3],[ノード3, 距離5]],[],...]
tree = [[] for _ in range(n)]
visited = [-1 for _ in range(n)]
# abc = [[0, 0, 0] for _ in range(n)]
for i in range(n-1):
    a, b, c = [int(j) for j in input().split()]
    tree[a - 1].append([b-1, c])
    tree[b - 1].append([a - 1, c])
def depth(now, cost):
    visited[now] = cost
    for i in range(len(tree[now])):
        if visited[tree[now][i][0]] == -1:
            depth(tree[now][i][0], cost+tree[now][i][1])
    return
q, k = [int(i) for i in input().split()]
depth(k-1, 0)
# print(visited)
for _ in range(q):
    x, y = [int(i) - 1 for i in input().split()]
    print(visited[x] + visited[y])

Submission status: Runtime Error

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

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

'''
 N:num of nodes
 Q: num of query
 K: node must passed in query

'''
dist = [-1]*(N+1)
for e in edges:
    if dist[e[0]] == -1:
        dist[e[0]] = [[e[1], e[2]]]
    else:
        dist[e[0]].append([e[1], e[2]])

    if dist[e[1]] == -1:
        dist[e[1]] = [[e[0], e[2]]]
    else:
        dist[e[1]].append([e[0], e[2]])

dist_from_k = [-1]*(N+1)


def dfs(v, p, cost):
    if dist_from_k[v] != -1:
        return

    dist_from_k[v] = cost
    for e in dist[v]:
        if e[0] == p:
            continue
        dfs(e[0], v, cost+e[1])


dfs(K, -1, 0)

for q in querys:
    print(dist_from_k[q[0]] + dist_from_k[q[1]])

Submission status: Runtime Error

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

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

'''
 N:num of nodes
 Q: num of query
 K: node must passed in query

'''
dist = [-1]*(N+1)
for e in edges:
    if dist[e[0]] == -1:
        dist[e[0]] = [[e[1], e[2]]]
    else:
        dist[e[0]].append([e[1], e[2]])

    if dist[e[1]] == -1:
        dist[e[1]] = [[e[0], e[2]]]
    else:
        dist[e[1]].append([e[0], e[2]])

dist_from_k = [-1]*(N+1)


def dfs(v, cost):
    if dist_from_k[v] != -1:
        return

    dist_from_k[v] = cost
    for e in dist[v]:
        dfs(e[0], cost+e[1])


dfs(K, 0)

for q in querys:
    print(dist_from_k[q[0]] + dist_from_k[q[1]])

Submission status: Runtime Error

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

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


def dfs(n):
    for v, c in G[n]:
        if dist[v] < 0:
            dist[v] = dist[n] + c
            dfs(v)


dfs(K)
for q 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:
n = int(input())
graph = [dict() for _ in range(n)]

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

q, k = map(int, input().split())
xy = []
for i in range(q):
    x, y = map(int, input().split())
    xy.append([x - 1, y - 1])
depth = [0 for _ in range(n)]
prev = [False for _ in range(n)]
depth[k - 1] = 0

import sys

sys.setrecursionlimit(10 ** 5)


def dfs(now, prev, cost, graph, depth):
    depth[now] = cost
    for k, v in graph[now].items():
        if k == prev:
            continue
        dfs(k, now, cost + v,  graph, depth)
    return depth


depth = dfs(k - 1, -1, 0, graph, depth)
for x, y in xy:
    print(depth[x] + depth[y])

Submission status: Runtime Error

Solution code:
n = int(input())
graph = [dict() for _ in range(n)]

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

q, k = map(int, input().split())
xy = []
for i in range(q):
    x, y = map(int, input().split())
    xy.append([x - 1, y - 1])
depth = [0 for _ in range(n)]
prev = [False for _ in range(n)]
depth[k - 1] = 0




def dfs(now, prev, cost, graph, depth):
    depth[now] = cost
    for k, v in graph[now].items():
        if k == prev:
            continue
        dfs(k, now, cost + v,  graph, depth)
    return depth


depth = dfs(k - 1, -1, 0, graph, depth)
for x, y in xy:
    print(depth[x] + depth[y])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from pprint import pprint as pp
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from collections import defaultdict
N = int(input())
abc = [list(map(int, input().split())) for _ in range(N-1)]
Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(Q)]

# graph = [[float('inf') for _ in range(N)] for _ in range(N)]
# graph = defaultdict(lambda: defaultdict(lambda:float('inf')))
graph = np.zeros((N,N), dtype=np.int32)

for a,b,c in abc:
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

# pp(graph)
dist = floyd_warshall(graph, directed=False)

for x,y in xy:
    print(int(dist[x-1][K-1] + dist[K-1][y-1]))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(3000)

n=int(input())
m=[[] for i in range(n)]
for i in range(n-1):
    a,b,c=map(int, input().split())
    m[a-1].append([b-1,c])
    m[b-1].append([a-1,c])
q,k=map(int, input().split())
    
def reach(m,d,k):
    for i in m[k]:
        if d[i[0]]==-1:
            d[i[0]]=d[k]+i[1]
            reach(m,d,i[0])
d=[-1]*n
d[k-1]=0
reach(m,d,k-1)

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())
m=[[] for i in range(n)]
for i in range(n-1):
    a,b,c=map(int, input().split())
    m[a-1].append([b-1,c])
    m[b-1].append([a-1,c])
q,k=map(int, input().split())
    
def reach(m,d,k):
    for i in m[k]:
        if d[i[0]]==-1:
            d[i[0]]=d[k]+i[1]
            reach(m,d,i[0])
d=[-1]*n
d[k-1]=0
reach(m,d,k-1)

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
input = sys.stdin.readline

def make_Graph(N, edges):#頂点の名前はi - 1で受け付ける
    graph = [ [] for i in range(N)]
    for edge in edges:
        a, b, c = edge
        graph[a].append((b,c))
        graph[b].append((a,c))
    return graph

def BFS(N, graph, start):
    Q = []
    V = []
    prev = [None] * N
    dd = [float("inf")] * N
    Q.append(start)
    dd[start] = 0
    while len(V) < N:
        a = Q.pop(0)
        V.append(a)
        for b, c in graph[a]:
            if b != prev[a]:
                Q.append(b)
                prev[b] = a
                dd[b] = dd[a] + c
    return dd

def DFS(N, graph, a, p, d):
    dd[a] = d
    for b, c in graph[a]:
        if b == p or dd[b] != 0:
            continue
        else:
            DFS(N, graph, b, a, d + c)

N = int(input())

sys.setrecursionlimit(10000)

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

Q, K =(int(i) for i in input().split())
dd = [0] * N

DFS(N, graph, K-1, -1, 0)

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