Problem:


Score : 400 points

Problem Statement

You are given a tree with N vertices.

Here, a tree is a kind of graph, and more specifically, a connected undirected graph with N-1 edges, where N is the number of its vertices.

The i-th edge (1≤i≤N-1) connects Vertices a_i and b_i, and has a length of c_i.

You are also given Q queries and an integer K. In the j-th query (1≤j≤Q):

find the length of the shortest path from Vertex x_j and Vertex y_j via Vertex K.

Constraints

3≤N≤10^5 

1≤a_i,b_i≤N (1≤i≤N-1) 

1≤c_i≤10^9 (1≤i≤N-1) 

The given graph is a tree.

1≤Q≤10^5 

1≤K≤N 

1≤x_j,y_j≤N (1≤j≤Q) 

x_j≠y_j (1≤j≤Q) 

x_j≠K,y_j≠K (1≤j≤Q) 

Input

Input is given from Standard Input in the following format:  

N  
a_1 b_1 c_1  
:  
a_{N-1} b_{N-1} c_{N-1}
Q K
x_1 y_1
:  
x_{Q} y_{Q}

Output

Print the responses to the queries in Q lines.

In the j-th line j(1≤j≤Q), print the response to the j-th query.

Sample Input 1

5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5

Sample Output 1

3
2
4

The shortest paths for the three queries are as follows:

Query 1: Vertex 2 → Vertex 1 → Vertex 2 → Vertex 4 : Length 1+1+1=3 

Query 2: Vertex 2 → Vertex 1 → Vertex 3 : Length 1+1=2 

Query 3: Vertex 4 → Vertex 2 → Vertex 1 → Vertex 3 → Vertex 5 : Length 1+1+1+1=4 

Sample Input 2

7
1 2 1
1 3 3
1 4 5
1 5 7
1 6 9
1 7 11
3 2
1 3
4 5
6 7

Sample Output 2

5
14
22

The path for each query must pass Vertex K=2.

Sample Input 3

10
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
1 1
9 10

Sample Output 3

17000000000



Sample input:
5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5


Sample output:
3
2
4

Submission status: Runtime Error

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


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]", Q: int, K: int, x: "List[int]", y: "List[int]"):
    edges = [[] for _ in range(N+1)]
    for aa, bb, cc in zip(a, b, c):
        edges[aa].append((bb, cc))
        edges[bb].append((aa, cc))
    costs = [None] * (N + 1)
    def dfs(n, c):
        if costs[n] is not None:
            return
        costs[n] = c
        for nn, cc in edges[n]:
            dfs(nn, c+cc)
    dfs(K, 0)
    for xx, yy in zip(x, y):
        print(costs[xx]+costs[yy])
    return

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    c = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    Q = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (Q)  # type: "List[int]"
    y = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, a, b, c, Q, K, x, y)

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
graph = [[0] * (N+1) for i in range(N+1)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    graph[a][b] = c
    graph[b][a] = c
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, \
    bellman_ford, johnson
from scipy.sparse import csr_matrix

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

a = np.array(graph)
path = shortest_path(a, indices=K)
# print(path)

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

Submission status: Runtime Error

Solution code:
N = int(input())
a = [[] for i in range(N)]
for i 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])
dist = [-1]*N
Q, K = map(int, input().split())
dist[K-1] = 0

def  dfs(now):
  for i, dis_e in a[now]:
    if dist[i] == -1:
      dist[i] = dist[now] + dis_e
      dfs(i)

def main():
  dfs(K-1)
  ans = []
  for i in range(Q):
    x, y = map(int, input().split())
    print(dist[x-1]+dist[y-1])
  #print(*ans, sep = "\n")

if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
N = int(input())
a = [[] for i in range(N)]
edge = {}
for i 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])
dist = [-1]*N
Q, K = map(int, input().split())
dist[K-1] = 0

def  dfs(now):
  for i, dis_e in a[now]:
    if dist[i] == -1:
      dist[i] = dist[now] + dis_e
      dfs(i)

def main():
  dfs(K-1)
  ans = []
  for i in range(Q):
    x, y = map(int, input().split())
    ans.append(dist[x-1]+dist[y-1])
  print(*ans, sep = "\n")

if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
N = int(input())
a = [[] for i in range(N)]
edge = {}
for i in range(N-1):
  A, B, C = map(int, input().split())
  a[A-1].append(B-1)
  a[B-1].append(A-1)
  edge[str(A-1)+"and"+str(B-1)] = C
  edge[str(B-1)+"and"+ str(A-1)] = C
dist = [-1]*N
Q, K = map(int, input().split())
dist[K-1] = 0

def  dfs(now):
  for i in a[now]:
    if dist[i] == -1:
      dist[i] = dist[now] + edge[str(now) + "and" +str(i)]
      dfs(i)

def main():
  dfs(K-1)
  ans = []
  for i in range(Q):
    x, y = map(int, input().split())
    ans.append(dist[x-1]+dist[y-1])
  print(*ans, sep = "\n")

if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
def dfs(node, dis, adj_list):

    for next, d in adj_list[node]:
        if dis[next] == float("inf"):
            dis[next] = dis[node] + d
            dfs(next, dis, adj_list)

    return


n = int(input())

adj_list = [[] for _ in range(n)]

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

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

k -= 1
dis = [float("inf")] * n
dis[k] = 0
dfs(k, dis, adj_list)

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

Submission status: Runtime Error

Solution code:
n = int(input())
edges = [[] for _ in range(n)]
costs = [-1]*n
def dfs(current):

    for nex, cost in edges[current]:
        if costs[nex] != -1:
            continue
        costs[nex] = costs[current] + cost
        dfs(nex)

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

q, k = map(int, input().split())
k -= 1
costs[k] = 0
dfs(k)

res = []
for _ in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    res.append(costs[x]+costs[y])

for ans in res:
    print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
edges = [[] for _ in range(n)]
costs = [-1]*n
def dfs(current, d):
    costs[current] = d
    for nex in edges[current]:
        if costs[nex[0]] != -1:
            continue
        dfs(nex[0], d+nex[1])

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

q, k = map(int, input().split())
k -= 1
dfs(k, 0)

res = []
for _ in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    res.append(costs[x]+costs[y])

for ans in res:
    print(ans)

Submission status: Runtime Error

Solution code:
import heapq

INF = 10**15
n = int(input())
edges = [[] for _ in range(n)]
costs = [INF]*n
def dfs(current, prev, d):
    costs[current] = d
    for nex in edges[current]:
        if nex[0] == prev:
            continue
        dfs(nex[0], current, d+nex[1])

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

q, k = map(int, input().split())
k -= 1
dfs(k, -1, 0)

res = []
for _ in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    res.append(costs[x]+costs[y])

for ans in res:
    print(ans)

Submission status: Runtime Error

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

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

def dfs(v):
    for u, du in to[v]:
        if dist_k[u] != -1:
            continue
        dist_k[u] = dist_k[v] + du
        dfs(u)
dfs(k)
dist_xky = [0] * q
for i in range(q):
    x, y = map(int, input().split())
    dist_xky[i] = dist_k[x] + dist_k[y]
print(*dist_xky, sep='\n')

Submission status: Runtime Error

Solution code:
from collections import deque

N = int(input())

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

# make tree
G2 = [-1] * (N + 1)


def f(v, c, p):
    if G2[v] != -1: return
    G2[v] = c

    for nv, nc in G[v]:
        if nv == p: continue
        f(nv, nc + c, v)


f(K, 0, 0)

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

Submission status: Runtime Error

Solution code:
n = int(input())
visited = [0]*n
def dfs(edge, dist, k):
    visited[k]=1
    for i in edge[k]:
        if visited[i[0]]==0:
            dist[i[0]]=i[1]+dist[k]
            dfs(edge, dist, i[0])


    return dist
def main():
    edge = [[] for _ in range(n)]
    for i in range(n-1):
        a,b,c=map(int, input().split())
        edge[a-1].append([b-1,c])
        edge[b-1].append([a-1,c])

    q,k=map(int, input().split())
    #頂点kから各頂点への距離を最初に求めておくdist[i]:頂点kから頂点iまでの距離　 dist[k]=0
    dist = [0]*n
    visited[k-1]=1
    dist = dfs(edge, dist, k-1)

    res = [0]*q
    for i in range(q):
        x,y=map(int, input().split())
        res[i]=dist[x-1]+dist[y-1]


    for i in range(q):
        print(res[i])
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:

from collections import deque
N=int(input())
T=[[] for _ in range(N)]
for i 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))

Q,K=map(int, input().split())
que=[(K-1,0)
done=[-1]*N
while que:
    t=que.pop(0)
    now,nowd=t
    done[now]=nowd
    for nex in T[now]:
        nexnode,nexd=nex
        if done[nexnode]!=-1:
            continue
        else:
            que.append((nexnode, nowd+nexd))

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

Submission status: Runtime Error

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

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

def dfs(x):
    for u, cost in edges[x]:
        if d[u] == INF:
            d[u] = d[x] + cost
            dfs(u)

dfs(K-1)

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

Submission status: Runtime Error

Solution code:
n = int(input())

def D(now,pre,SUM):
    dist[now] = SUM
    for BC in G[now]:
        if BC[0] == pre:
            continue
        D(BC[0],now,SUM+BC[1])



G = [[] for _ in range(n)]
for i in range(n-1):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append([b,c])
    G[b].append([a,c])
q,k = map(int,input().split())
# xから頂点kまでの最短経路を求めておいて、kからyまでの最短経路を求めておく
k -= 1
# ここで作っとく?
dist = [0] * n
D(k,-1,0)
for i in range(q):
    x,y = map(lambda x:int(x)-1, input().split())
    print(dist[x] + dist[y])

Submission status: Runtime Error

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

def dfs(start):
    for x,cost in graph[start]:
        if d[x]==-1:
            d[x]=d[start]+cost
            dfs(x)

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

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
def ep(*s):
    print(*s,file=sys.stderr)

def search(x,y):
    c = 0
    ox = nodes[x]
    oy = nodes[y]
    while ox.level != oy.level:
        if ox.level > oy.level:
            c += cost[(ox.parent,ox.n)]
            ox = nodes[ox.parent]
        if ox.level < oy.level:
            c += cost[(oy.parent,oy.n)]
            oy = nodes[oy.parent]
    while ox.n != oy.n:
        c += cost[(ox.parent,ox.n)]
        ox = nodes[ox.parent]
        c += cost[(oy.parent,oy.n)]
        oy = nodes[oy.parent]
    return c

class node:
    def __init__(self,n):
        self.n = n
        self.parent = -1
        self.children = set()
        self.level = -1
    def __repr__(self):
        #return f"node={self.n},parent={self.parent},level={self.level},ch={self.children}"
        return "n={0},p={1},l={2},ch{3}".format(self.n,self.parent,self.level,self.children)
    
    
n = int(input())
cost = {}
path = defaultdict(lambda: set())
for i in range(n-1):
    (ai,bi,ci) = list(map(int,input().split()))
    (ai,bi) = sorted([ai,bi])
    cost[(ai,bi)] = ci
    cost[(bi,ai)] = ci
    path[ai].add(bi)

# 各ノードの階層を調べる
nodes = {}
lv = 0
lst = [(1,-1)]
lst2 = []
term = 0

while len(lst) > 0:
    for (i,p) in lst:
        o = node(i)
        o.parent = p
        o.children = path[i]
        o.level = lv
        nodes[i] = o
        lst2 += list(map(lambda x:(x,i),list(path[i])))
    lst = lst2
    lst2 = []
    lv += 1

(q,k) = list(map(int,input().split()))
dp = defaultdict(int)

for i in range(q):
    (x,y) = list(map(int,input().split()))
    print(search(x,k) + search(k,y))

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
def ep(*s):
    print(*s,file=sys.stderr)

def search(x,y):
    c = 0
    ox = nodes[x]
    oy = nodes[y]
    while ox.level != oy.level:
        if ox.level > oy.level:
            c += cost[(ox.parent,ox.n)]
            ox = nodes[ox.parent]
        if ox.level < oy.level:
            c += cost[(oy.parent,oy.n)]
            oy = nodes[oy.parent]
    while ox.n != oy.n:
        c += cost[(ox.parent,ox.n)]
        ox = nodes[ox.parent]
        c += cost[(oy.parent,oy.n)]
        oy = nodes[oy.parent]
    return c

class node:
    def __init__(self,n):
        self.n = n
        self.parent = -1
        self.children = set()
        self.level = -1
    def __repr__(self):
        return f"node={self.n},parent={self.parent},level={self.level},ch={self.children}"
    
    
n = int(input())
cost = {}
path = defaultdict(lambda: set())
for i in range(n-1):
    (ai,bi,ci) = list(map(int,input().split()))
    (ai,bi) = sorted([ai,bi])
    cost[(ai,bi)] = ci
    cost[(bi,ai)] = ci
    path[ai].add(bi)

# 各ノードの階層を調べる
nodes = {}
lv = 0
lst = [(1,-1)]
lst2 = []
term = 0

while len(lst) > 0:
    for (i,p) in lst:
        o = node(i)
        o.parent = p
        o.children = path[i]
        o.level = lv
        nodes[i] = o
        lst2 += list(map(lambda x:(x,i),list(path[i])))
    lst = lst2
    lst2 = []
    lv += 1

(q,k) = list(map(int,input().split()))
dp = defaultdict(int)

for i in range(q):
    (x,y) = list(map(int,input().split()))
    print(search(x,k) + search(k,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())
indices = []
indptr = []
data = []
for _ in range(N-1):
    a,b,c = map(int,input().split())
    indices.append(a)
    indptr.append(b)
    data.append(c)
Q,K = map(int,input().split())
xy = [list(map(int,input().split())) for _ in range(Q)]
csr = csr_matrix((data,(indices,indptr)),shape=(N+1,N+1))

p = dijkstra(csr,directed=False)
for x,y in xy:
    print(int(p[x,K]+p[K,y]))

Submission status: Runtime Error

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


def input():
    return sys.stdin.readline()[:-1]


def dfs(now, point):
    if K in tree[now-1]:
        point += tree_c[now-1][K]
        return point
    else:
        for next_node in tree[now-1]:
            if zumi[next_node-1] == -1:
                tmp_p = point+tree_c[now-1][next_node]
                return dfs(next_node, tmp_p)


N = int(input())
tree = [{} for i in range(N)]
tree_c = [{} for i in range(N)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    tree[a-1][b] = True
    tree[b-1][a] = True
    tree_c[a-1][b] = c
    tree_c[b-1][a] = c
Q, K = map(int, input().split())

for _ in range(Q):
    x, y = map(int, input().split())
    zumi = [-1]*N
    zumi[x-1] = 0
    ans = dfs(x, 0)

    zumi = [-1]*N
    zumi[y-1] = 0
    ans += dfs(y, 0)
    print(ans)

Submission status: Runtime Error

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

costDic = [0]*(N+1)
def f(cost,now,p):
    costDic[now] = cost
    for nx,c in edges[now].items():
        if nx != p:
            f(cost+c,nx,now)

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

Submission status: Runtime Error

Solution code:
n=int(input())

c={}
tree=[[] for _ in range(n)]

for _ in range(n-1):
    i,j,k=map(int,input().split())
    i-=1
    j-=1
    tree[i].append(j)
    tree[j].append(i)
    c[(i,j)]=k
    c[(j,i)]=k

result=[]
q,k=map(int,input().split())

#初期値が0の辞書
from collections import defaultdict
memo = defaultdict(lambda: -1) 

def DEF(z,cnt):
    global memo,tree,c
    memo[z]=cnt
    for item in tree[z]:
        if memo[item]==-1:
            DEF(item,cnt+c[(item,z)])

DEF(k-1,0)
result=[]
for item in range(q):
    a,b=map(int,input().split())
    result.append(memo[a-1]+memo[b-1])

for item in result:
    print(item)

Submission status: Runtime Error

Solution code:
N = int(input())

vertex = [{} for _ in range(N)]

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

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

d = [0 for i in range(N)]

def dfs(v1,v2):
    d[v2] = d[v1] + vertex[v1][v2]
    for v in vertex[v2]:
        if v == v1:
            continue
        dfs(v2,v)

for v in vertex[K-1].keys():
    dfs(K-1,v)

for q 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.setrecursionlimit(10**6);l=lambda:map(int, input().split());n=int(input());s=[0for _ in[0]*n];j=[[]for _ in[0]*n]
for _ in range(n-1):a,b,c=l();j[a-1].append([b-1,c]);j[b-1].append([a-1,c])
def f(v,p,d):
 s[v]=d
 for i,c in j[v]:
  if i==p:
   continue
  f(i,v,d+c)
q,k=l()
dfs(k-1,-1,0)
for _ in [0]*q:x,y=l();print(s[x-1]+s[y-1])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6);l=lambda:map(int, input().split());n=int(input()):s=[0for _ in[0]*n];j=[[]for _ in[0]*n]
for _ in range(n-1):a,b,c=l();j[a-1].append([b-1,c]);j[b-1].append([a-1,c])
def f(v,p,d):
 s[v]=d
 for i,c in j[v]:
  if i==p:
   continue
  f(i,v,d+c)
q,k=l()
dfs(k-1,-1,0)
for _ in [0]*q:x,y=l();print(s[x-1]+s[y-1])

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)

N = int(input())
Nodes = [{} for i in range(N)]


def search(index, dist):
    neighbors = Nodes[index]
    for key in neighbors:
        if distances[key] is not None:
            continue

        distances[key] = dist + neighbors[key]
        search(key, distances[key])


# 木を作る
for _ in range(N-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    Nodes[a][b] = c
    Nodes[b][a] = c

# 頂点Kから各点への距離を求める
Q, K = map(int, input().split())
distances = [None for i in range(N)]
distances[K-1] = 0
search(index=K-1, dist=0)

#print(distances)

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

Submission status: Runtime Error

Solution code:
N = int(input())
Nodes = [{} for i in range(N)]


def search(index, dist):
    neighbors = Nodes[index]
    for key in neighbors:
        if distances[key] is not None:
            continue

        distances[key] = dist + neighbors[key]
        search(key, distances[key])


# 木を作る
for _ in range(N-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    Nodes[a][b] = c
    Nodes[b][a] = c

# 頂点Kから各点への距離を求める
Q, K = map(int, input().split())
distances = [None for i in range(N)]
distances[K-1] = 0
search(index=K-1, dist=0)

#print(distances)

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

Submission status: Runtime Error

Solution code:
from collections import deque

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[0]*(N-1)
L=[ [] for _ in range(N)]
for i in range(N-1):
  a[i],b[i],c[i]= map(int,input().split())
  L[a[i]-1].append((b[i]-1,c[i]))
  L[b[i]-1].append((a[i]-1,c[i]))
Q,K= map(int,input().split())
         
#Lの中のitemの0は接続先、1は距離

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

def BFS(x):
  v=deque([x])
  d[x]=0
  
  while len(v)>0:
    s=v.popleft() #sはint
    for item in L[s]:
      if d[item[0]]==-1:
        d[item[0]]=d[s]+item[1]
        v.append(item[0])
BFS(K-1)

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

Submission status: Runtime Error

Solution code:
from collections import deque

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[0]*(N-1)
L=[ [] for _ in range(N)]
for i in range(N-1):
  a[i],b[i],c[i]= map(int,input().split())
  L[a[i]-1].append((b[i]-1,c[i]))
  L[b[i]-1].append((a[i]-1,c[i]))
Q,K= map(int,input().split())
         
#Lの中のitemの0は接続先、1は距離

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

def BFS(x):
  v=deque([x])
  d[x]=0
  
  while len(v)>0:
    s=v.popleft() #sはint
    for item in L[s]:
      if d[item[0]]==-1:
        d[item[0]]=d[s]+item[1]
        v.append(item[0])
BFS(K-1)

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

Submission status: Runtime Error

Solution code:
import heapq
class Graph:
    def __init__(self,v,edgelist,w_v = None,directed = False):
        super().__init__()
        self.v = v
        self.w_e = [{} for _ in [0]*self.v]
        self.neighbor = [[] for _ in [0]*self.v]
        self.w_v = w_v
        self.directed = directed

        for i,j,w in edgelist:
            self.w_e[i][j] = w
            self.neighbor[i].append(j)

    def dijkstra(self,v_n):
        d = [float('inf')]*self.v
        d[v_n] = 0
        prev = [-1]*self.v

        queue = []
        for i,d_i in enumerate(d): heapq.heappush(queue,(d_i,i))
        
        while len(queue)>0:
            d_u,u = queue.pop()
            if d[u]<d_u :continue
            for v in self.neighbor[u]:
                alt = d[u]+self.w_e[u][v]
                if d[v]>alt:
                    d[v] = alt
                    prev[v] = u
                    heapq.heappush(queue,(alt,v))

        return d,prev

    def warshallFloyd(self):
        d = [[10**18]*self.v for _ in [0]*self.v]
        for i in range(self.v):
            d[i][i] = 0
            
        for i in range(self.v):
            for j in self.neighbor[i]:
                d[i][j] = self.w_e[i][j]
            
        for i in range(self.v):
            for j in self.neighbor[i]:
                d[i][j] = self.w_e[i][j]
        
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    check = d[i][k] + d[k][j]
                    if d[i][j] > check:
                        d[i][j] = check
        return d

    def prim(self):
        gb = GraphBuilder(self.v,self.directed)

        queue = []
        for i,w in self.w_e[0].items(): heapq.heappush(queue,(w,0,i))
        rest = [True]*self.v
        rest[0] = False

        v = 1
        while len(queue)>0:
            w,i,j = heapq.heappop(queue)
            if rest[j]:
                gb.addEdge(i,j,w)
                rest[j] = False
                for k,w in self.w_e[j].items():
                    if rest[k]:heapq.heappush(queue,(w,j,k))

        return gb


class Tree():
    def __init__(self,v,e):
        pass

class GraphBuilder():
    def __init__(self,v,directed = False):
        self.v = v
        self.directed = directed
        self.edge = []

    def addEdge(self,i,j,w=1):
        if not self.directed:
            self.edge.append((j,i,w))
        self.edge.append((i,j,w))

    def addEdges(self,edgelist,weight = True):
        if weight:
            if self.directed:
                for i,j,w in edgelist:
                    self.edge.append((i,j,w))
            else:
                for i,j,w in edgelist:
                    self.edge.append((i,j,w))
                    self.edge.append((j,i,w))
        else:
            if self.directed:
                for i,j,w in edgelist:
                    self.edge.append((i,j,1))
            else:
                for i,j,w in edgelist:
                    self.edge.append((i,j,1))
                    self.edge.append((j,i,1))
            

    def addAdjMat(self, mat):
        for i,mat_i in enumerate(mat):
            for j,w in enumerate(mat_i):
                self.edge.append((i,j,w))

    def buildTree(self):
        pass

    def buildGraph(self):
        return Graph(self.v,self.edge,directed=self.directed)
   
def main():
    n = int(input())
    edge = []
    for _ in range(n):
        a,b,w = tuple([int(t)for t in input().split()])
        edge.append((a-1,b-1,w))
    gb = GraphBuilder(n)
    gb.addEdges(edge)
    g = gb.buildGraph()
    
    q,k = tuple([int(t)for t in input().split()])
    dijk = g.dijkstra(k-1)[0]
    ans = []
    for _ in range(q):
        x,y = tuple([int(t)-1 for t in input().split()])
        ans.append(dijk[x]+dijk[y])
    for a_i in ans:
        print(a_i)
        
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import shortest_path
import sys
import numpy as np
def input():
    return sys.stdin.readline().strip()
 
N = int(input())
 
graph = [[0 for i in range(N)] for j 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())
dist = shortest_path(np.array(graph),indices=K-1)

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

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
INF = 11414191981036436433-4

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

r = [INF]*n
que = deque([k])
r[k] = 0
while que:
    v = que.popleft()
    rr = r[v]
    for w,x in G[v]:
        if r[w] == INF:
            r[w] = rr + x
            que.append(w)
            
for i in range(q):
    d,e = map(int,input().split())
    print(r[d-1] + r[e-1])

Submission status: Runtime Error

Solution code:
from collections import deque
import sys

N = int(input())
prv = [None]*N
G = [[] for i in range(N)]
for v in range(N-1):
    a,b,c = map(int,input().split())
    aa = min(a,b)-1
    bb = max(a,b)-1
    G[aa].append((bb,c))
    prv[bb] = aa

depth = [0]*N
r = [0]*N
que = deque([0])
while que:
    v = que.popleft()
    d = depth[v]
    rr = r[v]
    for w,x in G[v]:
        depth[w] = d + 1
        r[w] = rr + x
        que.append(w)
        
LV = (N-1).bit_length()
def construct(prv):
    kprv = [prv]
    S = prv
    for k in range(LV):
        T = [0]*N
        for i in range(N):
            if S[i] is None:
                continue
            T[i] = S[S[i]]
        kprv.append(T)
        S = T
    return kprv

def lca(u, v, kprv, depth):
    dd = depth[v] - depth[u]
    if dd < 0:
        u, v = v, u
        dd = -dd

    # assert depth[u] <= depth[v]
    for k in range(LV+1):
        if dd & 1:
            v = kprv[k][v]
        dd >>= 1

    # assert depth[u] == depth[v]
    if u == v:
        return u

    for k in range(LV-1, -1, -1):
        pu = kprv[k][u]; pv = kprv[k][v]
        if pu != pv:
            u = pu; v = pv

    # assert kprv[0][u] == kprv[0][v]
    return kprv[0][u]


kprv = construct(prv)

Q,k = map(int, input().split())
k -= 1
for q in range(Q):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    a1 = lca(u, k, kprv, depth)
    a2 = lca(v, k, kprv, depth)
    aa1 = r[u] + r[k] - 2*r[a1]
    aa2 = r[k] + r[v] - 2*r[a2]
    print(aa1+aa2)

Submission status: Runtime Error

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

n = int(input())
L = np.zeros((n,n),int)
for _ in range(n-1):
    a,b,c = map(int,input().split())
    L[a-1,b-1] = c

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

dist = dijkstra(L,directed = False, indices= k-1).astype(int)

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

Submission status: Runtime Error

Solution code:
n = int(input())
adjacency = [[] for i in range(n+1)] #adjacency[i]は頂点iと隣接する頂点のリスト
distance = {} # distance[(i,j)](i,jは隣接した頂点)は頂点i,jを結ぶ辺の長さ
for i in range(n-1):
    line = list(map(int, input().split()))
    adjacency[line[0]].append(line[1])
    adjacency[line[1]].append(line[0])
    distance[(line[0], line[1])] = line[2]
    distance[(line[1], line[0])] = line[2]
q, k = map(int, input().split())
x = []
y = []
for i in range(q):
    line = list(map(int, input().split()))
    x.append(line[0])
    y.append(line[1])

k_distance = [-1 for i in range(n+1)] # k_distance[i]は頂点i,kの距離
k_distance[k] = 0
reached = {k}
def dfs(v, d): # 現在いる頂点vと頂点v,k間の距離dを入力すると頂点vと隣接する未到達の頂点のk_distanceを計算してappendする
    for neighbor in adjacency[v]:
        if not neighbor in reached:
            reached.add(neighbor)
            k_distance[neighbor] = d + distance[(v, neighbor)]
            dfs(neighbor, k_distance[neighbor])
    return
dfs(k, 0)
for i in range(q):
    print(k_distance[x[i]] + k_distance[y[i]])

Submission status: Runtime Error

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

頂点Kから各ノードへの最短ルートはdfsとかで記録していけばよい。
"""
def main():
    import sys
    sys.setrecursionlimit(2000000)
    input = sys.stdin.readline
    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:
                nextcost = (cost+c)%mod
                dfs(i,nextcost)
    dfs(K,0)
    for i in range(Q):
        x,y=map(int,input().split())
        print(dp[x]+dp[y])
main()

Submission status: Runtime Error

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

頂点Kから各ノードへの最短ルートはdfsとかで記録していけばよい。
"""
def main():
    import sys
    sys.setrecursionlimit(20000000)
    input = sys.stdin.readline
    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:
                nextcost = (cost+c)%mod
                dfs(i,nextcost)
    dfs(K,0)
    for i in range(Q):
        x,y=map(int,input().split())
        print(dp[x]+dp[y])
main()