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
from math import log2
def input(): return sys.stdin.readline().strip()


def main():
    """
    Kの指定があるのに気づかずダブリングでLCA求めちゃった・・・！
    https://algo-logic.info/lca/
    勉強になったから良しとする。ポイントとして
    1. parents[k][u]の求め方がまず再帰
    2. LCAでまず深さを揃えるとこも2べき（必ずfor文はint(log2(N))まで回すこと！）
    3. ダブリングは祖先が一致しない時だけ更新
    を押さえとけば自力で再現できそう？
    """
    N = int(input())
    repn = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b, c = map(int, input().split())
        repn[a - 1].append((b - 1, c))
        repn[b - 1].append((a - 1, c))
    depth = [-1] * N
    dist = [0] * N
    parents = [[-1] * N for _ in range(int(log2(N)) + 2)]  # parents[k][u] = (頂点uから2^k先の祖先)

    def dfs(u):
        for v, c in repn[u]:
            if depth[v] != -1: continue
            depth[v] = depth[u] + 1
            dist[v] = dist[u] + c
            parents[0][v] = u
            dfs(v)

    depth[0] = 0
    dfs(0)

    for k in range(int(log2(N)) + 1):
        for u in range(N):
            if parents[k][u] < 0:
                parents[k + 1][u] = -1
            else:
                parents[k + 1][u] = parents[k][parents[k][u]]

    def doubling(u, v):
        if depth[u] < depth[v]: u, v = v, u
        for k in range(int(log2(N)) + 1):
            if ((depth[u] - depth[v]) & (1 << k)):
                u = parents[k][u]
                k += 1
        if u == v: return u
        for k in range(int(log2(N)), -1, -1):
            if parents[k][u] != parents[k][v]:
                u = parents[k][u]
                v = parents[k][v]
        return parents[0][u]

    Q, K = map(int, input().split())
    for _ in range(Q):
        u, v = map(int, input().split())
        lca1 = doubling(u - 1, K - 1)
        lca2 = doubling(K - 1, v - 1)
        d1 = dist[u - 1] + dist[K - 1] - dist[lca1]
        d2 = dist[K - 1] + dist[v - 1] - dist[lca2]
        print(d1 + d2)



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
from math import log2
def input(): return sys.stdin.readline().strip()


def main():
    """
    Kの指定があるのに気づかずダブリングでLCA求めちゃった・・・！
    https://algo-logic.info/lca/
    勉強になったから良しとする。ポイントとして
    1. parents[k][u]の求め方がまず再帰
    2. LCAでまず深さを揃えるとこも2べき（必ずfor文はint(log2(N))まで回すこと！）
    3. ダブリングは祖先が一致しない時だけ更新
    を押さえとけば自力で再現できそう？
    """
    N = int(input())
    repn = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b, c = map(int, input().split())
        repn[a - 1].append((b - 1, c))
        repn[b - 1].append((a - 1, c))
    depth = [-1] * N
    dist = [0] * N
    parents = [[-1] * N for _ in range(int(log2(N)) + 2)]  # parents[k][u] = (頂点uから2^k先の祖先)

    def dfs(u):
        for v, c in repn[u]:
            if depth[v] != -1: continue
            depth[v] = depth[u] + 1
            dist[v] = dist[u] + c
            parents[0][v] = u
            dfs(v)

    depth[0] = 0
    dfs(0)

    for k in range(int(log2(N)) + 1):
        for u in range(N):
            if parents[k][u] < 0:
                parents[k + 1][u] = -1
            else:
                parents[k + 1][u] = parents[k][parents[k][u]]

    def doubling(u, v):
        if depth[u] < depth[v]: u, v = v, u
        for k in range(int(log2(N)) + 1):
            if ((depth[u] - depth[v]) & (1 << k)):
                u = parents[k][u]
                k += 1
        if u == v: return u
        for k in range(int(log2(N)), -1, -1):
            if parents[k][u] != parents[k][v]:
                u = parents[k][u]
                v = parents[k][v]
        return parents[0][u]

    Q, K = map(int, input().split())
    for _ in range(Q):
        u, v = map(int, input().split())
        lca1 = doubling(u - 1, K - 1)
        lca2 = doubling(K - 1, v - 1)
        d1 = dist[u - 1] + dist[K - 1] - dist[lca1]
        d2 = dist[K - 1] + dist[v - 1] - dist[lca2]
        print(lca1, lca2)
        print(d1 + d2)



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
adj = defaultdict(list)
vis =[0 for i in range(1000000)]
dis =[0 for i in range(1000000)]
def dfs(u, p):
	for v, w in adj[u]:
		if v==p:
			continue
		dis[v]=dis[u]+w
		dfs(v, u)

def main():
	n = int(input())
	for i in range(n-1):
		a, b, w = map(int , input().split())
		adj[a].append((b, w))
		adj[b].append((a, w))

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

if __name__ == "__main__":
	main()

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())
    tree[a-1].append([b-1, c])
    tree[b-1].append([a-1, c])
Q, K = map(int, input().split())

dist = [-1] * N
def dfs(v, total_cost):
    # v：頂点, total_cost：今までかかったコストの合計
    dist[v] = total_cost
    for v_next, cost in tree[v]:
        if dist[v_next] >= 0:
            continue
            # v_nextが訪問済みならスキップ
        dfs(v_next, total_cost+cost)

dfs(K-1, 0)

for i 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())
tree = [[] for _ in range(N)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    tree[a-1].append((b-1, c))
    tree[b-1].append((a-1, c))
Q, K = map(int, input().split())

dist = [-1] * N
def dfs(v, total_cost=0):
    # v：頂点, total_cost：今までかかったコストの合計
    dist[v] = total_cost
    for v_next, cost in tree[v]:
        if dist[v_next] >= 0:
            continue
            # v_nextが訪問済みならスキップ
        dfs(v_next, total_cost+cost)

dfs(K-1, 0)

for i 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())
tree = [[] for _ in range(N)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    tree[a-1].append((b-1, c))
    tree[b-1].append((a-1, c))
Q, K = map(int, input().split())

dist = [-1] * N
def dfs(v, total_cost):
    # v：頂点, total_cost：今までかかったコストの合計
    dist[v] = total_cost
    for v_next, cost in tree[v]:
        if dist[v_next] >= 0:
            continue
            # v_nextが訪問済みならスキップ
        dfs(v_next, total_cost+cost)

dfs(K-1, 0)

for i 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())
tree = [[] for _ in range(N)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    tree[a-1].append([b-1, c])
    tree[b-1].append([a-1, c])
Q, K = map(int, input().split())

dist = [-1] * N
def dfs(v, total_cost):
    # v：頂点, total_cost：今までかかったコストの合計
    dist[v] = total_cost
    for v_next, cost in tree[v]:
        if dist[v_next] >= 0:
            continue
            # v_nextが訪問済みならスキップ
        dfs(v_next, total_cost+cost)

dfs(K-1, 0)

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

Submission status: Runtime Error

Solution code:
def dfs(now_node,parent_node,dist):
  depth[now_node]=dist
  for next_node,w in graph[now_node]:
    if next_node==parent_node:
      continue
    dfs(next_node,now_node,dist+w)

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

Submission status: Runtime Error

Solution code:
def abc070_d():
    import sys
    read = sys.stdin.buffer.read
    inp = iter(map(int, read().split()))

    import numpy as np
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import dijkstra

    n = next(inp)
    adjmtx = np.zeros((n, n), dtype=np.int32)
    for _ in range(n-1):
        a = next(inp) - 1
        b = next(inp) - 1
        c = next(inp)
        adjmtx[a, b] = c
        adjmtx[b, a] = c

    q = next(inp)
    k = next(inp) - 1

    graph = csr_matrix(adjmtx)
    dist = dijkstra(csgraph=graph, indices=k)
    eps = 1e-6

    for _ in range(q):
        x = next(inp) - 1
        y = next(inp) - 1
        ans = int(dist[x] + dist[y] + eps)
        print(ans)

if __name__ == '__main__':
    abc070_d()

Submission status: Runtime Error

Solution code:
def abc070_d():
    import sys
    read = sys.stdin.buffer.read
    inp = iter(map(int, read().split()))

    import numpy as np
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import dijkstra

    n = next(inp)
    adjmtx = np.zeros((n, n), dtype=np.int64)
    for _ in range(n-1):
        a = next(inp) - 1
        b = next(inp) - 1
        c = next(inp)
        adjmtx[a, b] = c
        adjmtx[b, a] = c

    q = next(inp)
    k = next(inp) - 1

    graph = csr_matrix(adjmtx)
    dist = dijkstra(csgraph=graph, indices=k)
    eps = 1e-6

    for _ in range(q):
        x = next(inp) - 1
        y = next(inp) - 1
        ans = int(dist[x] + dist[y] + eps)
        print(ans)

if __name__ == '__main__':
    abc070_d()

Submission status: Runtime Error

Solution code:
def abc070_d():
    import sys
    read = sys.stdin.buffer.read
    inp = iter(map(int, read().split()))

    import numpy as np
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import dijkstra

    n = next(inp)
    adjmtx = np.zeros((n, n), dtype=np.int64)
    for _ in range(n-1):
        a = next(inp) - 1
        b = next(inp) - 1
        c = next(inp)
        adjmtx[a, b] = c
        adjmtx[b, a] = c

    q = next(inp)
    k = next(inp) - 1

    graph = csr_matrix(adjmtx)
    dist = dijkstra(csgraph=graph, indices=k)

    for _ in range(q):
        x = next(inp) - 1
        y = next(inp) - 1
        ans = int(dist[x] + dist[y])
        print(ans)

if __name__ == '__main__':
    abc070_d()

Submission status: Runtime Error

Solution code:
def dfs(v, p, d):
    dist[v] = d
    for c, cost in edge[v]:
        if c == p:
            continue
        dfs(c, v, d + cost)


n = int(input())

edge = [[] for _ in range(n)]
for _ 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())

dist = [0] * n
dfs(k-1, -1, 0)

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

for v in res:
    print(v)

Submission status: Runtime Error

Solution code:
def dfs(st, depth=0):
    dist[st] = depth
    for to, c in tree[st]:
        if dist[to]>=0:
            continue
        dfs(to, depth+c)


N = int(input())
tree = [[] for _ in range(N)]
dist = [-1]*N

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

Q, K = map(int, input().split())
dfs(K-1, 0)
# print(dist)
# print(tree)
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())
d = [-1 for i in range(n)]
e = [[] for i in range(n)]
for i in range(n - 1):
    a, b, c = map(int, input().split())
    e[a - 1].append([b - 1, c])
    e[b - 1].append([a - 1, c])
q, k = map(int, input().split())
def dfs(cur, par, di):
    d[cur] = di
    for i in e[cur]:
        if d[i[0]] == -1:
            if i == par:
                continue
            dfs(i[0], cur, di + i[1])
dfs(k - 1, -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 = 5
# ARR = [
#     [1, 2, 1],
#     [1, 3, 1],
#     [2, 4, 1],
#     [3, 5, 1]
# ]
#
# Q, K = 3, 1
#
# BRR = [
#     [2, 4],
#     [2, 3],
#     [4, 5],
# ]
#
#

N = int(input())

ARR = [list(map(int,input().split())) for i in range(N-1)]

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

BRR = [list(map(int,input().split())) for i in range(Q)]



def prepare(arr, n):
    links = [[] for i in range(n)]
    depth = [0 for i in range(n)]
    for i in range(n - 1):
        startNode = arr[i][0] - 1
        endNode = arr[i][1] - 1
        dist = arr[i][2]

        links[startNode].append((endNode, dist))
        links[endNode].append((startNode, dist))

    return links, depth


def dfs(currentNode, parrentNode=-1, dist=0):
    childNodes = links[currentNode]
    depths[currentNode] = dist
    for (childNode, childDistance) in childNodes:
        if childNode == parrentNode:
            continue

        dfs(childNode, currentNode, dist + childDistance)


links, depths = prepare(ARR, N)

dfs(K - 1)

for i in range(Q):
    p1 = BRR[i][0] - 1
    p2 = BRR[i][1] - 1

    d1 = depths[p1]
    d2 = depths[p2]

    print(d1 + d2)

Submission status: Runtime Error

Solution code:
from collections import deque
n = int(input())
g = [[] for i 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())

# 前処理
dist = [-1] * n

def dfs(st, depth=0):
    dist[st] = depth
    for to, c in g[st]:
        if dist[to] >= 0: continue
        dfs(to, depth+c)

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:
N = int(input())
G = [[] for _ in range(N)]
length = {}
for _ in range(N-1):
    a, b, c = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    length[(a-1, b-1)] = c
    length[(b-1, a-1)] = c

r = 0
dist = [0]*N

prv = [None]*N
depth = [0]*N

def dfs(v):
    for u in G[v]:
        if dist[u] > 0 or u ==r: continue
        dist[u] = dist[v] + length[(v, u)]
        depth[u] = depth[v] + 1
        prv[u] = v
        dfs(u)

dfs(r)

# N: 頂点数
# G[v]: 頂点vの子頂点 (親頂点は含まない)
#
# - construct
# prv[u] = v: 頂点uの一つ上の祖先頂点v
# - lca
# kprv[k][u] = v: 頂点uの2^k個上の祖先頂点v
# depth[u]: 頂点uの深さ (根頂点は0)

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

ans = []
for _ in range(Q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    xr = lca(x, K, kprv, depth)
    yr = lca(y, K, kprv, depth)
    a = dist[x] + dist[K] - dist[xr]*2 + dist[y] + dist[K] - dist[yr]*2
    ans.append(a)

print('\n'.join(map(str, ans)))

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
import sys
input = sys.stdin.readline

import heapq

INF = 10 ** 18

class Edge():
    def __init__(self, start, end, cost):
        self.start = start
        self.end = end
        self.cost = cost
    def __str__(self):
        return 'Edge: {} -> {}, cost {}'.format(self.start, self.end, self.cost)

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    h = []
    heapq.heappush(h, (0, s))

    while h:
        # 使っていない頂点のうち、現時点で最も距離の近いものを選びvとする
        d, v = heapq.heappop(h)
        if dist[v] < d:
            continue
        # vから到達可能な頂点について、距離が短くなれば更新
        for e in G[v]:
            if dist[e.end] > dist[v] + e.cost:
                dist[e.end] = dist[v] + e.cost
                heapq.heappush(h, (dist[e.end], e.end))
    return dist


n = int(input())
es = [[] for i in range(n)]

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

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

d = dijkstra(n, es, k)

for j 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())
edge=[[] for i in range(n)]
for i in range(n-1):
    x,y,z=map(int,input().split())
    edge[x-1].append([y-1,z])
    edge[y-1].append([x-1,z])
q,k=map(int,input().split())
dist=[-1]*n
def dfs(node,d):
    dist[node]=d
    for i in edge[node]:
        if dist[i[0]]==-1:
            dfs(i[0],d+i[1])
dfs(k-1,0)
for i 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())
G=[[] for _ 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())

SD=[0]*N
def DFS(v,p,d):
    SD[v]=d
    for i,co in G[v]:
        if i==p:continue
        DFS(i,v,d+co)
    return

DFS(K-1,-1,0)

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

Submission status: Runtime Error

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

import scipy.sparse
N = int(input())
lil = scipy.sparse.lil_matrix((N, N), dtype = int)
for i in range(N-1):
    a, b, c = (int(x) for x in input().split())
    lil[a-1, b-1] = c
lil2 = scipy.sparse.csgraph.dijkstra(lil,directed=False).astype(int)
Q, K = (int(x) for x in input().split())
for i in range(Q):
    x, y = (int(x) for x in input().split())
    print(lil2[K-1][x-1]+lil2[K-1][y-1])

Submission status: Runtime Error

Solution code:
import scipy.sparse
N = int(input())
lil = scipy.sparse.lil_matrix((N, N), dtype = int)
for i in range(N-1):
    a, b, c = (int(x) for x in input().split())
    lil[a-1, b-1] = c
lil2 = scipy.sparse.csgraph.dijkstra(lil, directed = False).astype(int)
Q, K = (int(x) for x in input().split())
for i in range(Q):
    x, y = (int(x) for x in input().split())
    print(lil2[K-1][x-1]+lil2[K-1][y-1])

Submission status: Runtime Error

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



n = int(input())
matrix = np.zeros((n, n),dtype=np.int64)
for i in range(n-1):
    a, b, c = map(int, input().split())
    matrix[a-1][b-1] = c
    matrix[b-1][a-1] = c
min_span_matrix = dijkstra(matrix, directed=False,
                                 return_predecessors=False)
q, k = map(int, input().split())
for i in range(q):
    x, y = map(int, input().split())
    print(int(min_span_matrix[x-1][k-1] + min_span_matrix[k-1][y-1]))

Submission status: Runtime Error

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



n = int(input())
matrix = np.zeros((n, n),dtype=np.int64)
for i in range(n-1):
    a, b, c = map(int, input().split())
    matrix[a-1][b-1] = c
    matrix[b-1][a-1] = c
min_span_matrix = floyd_warshall(matrix, directed=False,
                                 return_predecessors=False)
q, k = map(int, input().split())
for i in range(q):
    x, y = map(int, input().split())
    print(int(min_span_matrix[x-1][k-1] + min_span_matrix[k-1][y-1]))

Submission status: Runtime Error

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



n = int(input())
matrix = np.zeros((n, n))
for i in range(n-1):
    a, b, c = map(int, input().split())
    matrix[a-1][b-1] = c
    matrix[b-1][a-1] = c
min_span_matrix = floyd_warshall(matrix, directed=False,
                                 return_predecessors=False)
q, k = map(int, input().split())
for i in range(q):
    x, y = map(int, input().split())
    print(min_span_matrix[x-1][k-1] + min_span_matrix[k-1][y-1])

Submission status: Runtime Error

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


def main():
    h, w = map(int, input().split())
    grids = [list(input()) for _ in range(h)]
    up = [[1 for __ in range(w)] for _ in range(h)]
    down = [[1 for __ in range(w)] for _ in range(h)]
    left = [[1 for __ in range(w)] for _ in range(h)]
    right = [[1 for __ in range(w)] for _ in range(h)]
    ans = 0

    # 上に移動できるマスの数
    for i in range(h - 1, -1, -1):
        for j in range(w):
            if (grids[i][j] == '.') and (i < h - 1):
                up[i][j] = up[i + 1][j] + 1
            elif grids[i][j] == '#':
                up[i][j] = 0

    # 下に移動できるマスの数
    for i in range(h):
        for j in range(w):
            if (grids[i][j] == '.') and (i > 0):
                down[i][j] = down[i - 1][j] + 1
            elif grids[i][j] == '#':
                down[i][j] = 0

    # 左に移動できるマスの数
    for i in range(h):
        for j in range(w - 1, -1, -1):
            if (grids[i][j] == '.') and (j < w - 1):
                left[i][j] = left[i][j + 1] + 1
            elif grids[i][j] == '#':
                left[i][j] = 0

    # 右に移動できるマスの数
    for i in range(h):
        for j in range(w):
            if (grids[i][j] == '.') and (j > 0):
                right[i][j] = right[i][j - 1] + 1
            elif grids[i][j] == '#':
                right[i][j] = 0

    # あるマス(i, j)に着目したときに，上下左右に移動できるマスの数を計算
    for i in range(h):
        for j in range(w):
            # 重複しているマスを除外
            ans = max(ans, (up[i][j] + down[i][j] - 1) + (left[i][j] + right[i][j] - 1) - 1)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, K = map(int,input().split())
a = list(map(int,input().split()))
a = [0] + a
A = [0]*(N+1)
for i in range(1,N+1):
  A[i] = A[i-1] + a[i]

Submission status: Runtime Error

Solution code:
from itertools import accumulate
 
N, K = map(int,input().split())
a = list(map(int,input().split()))
a = [0] + a
A = [0]*(N+1)
for i in range(1,N+1):
  A[i] = A[i-1] + a[i]
  
#A = list(accumulate(a))
ans = 0
for i in range(1,N-K+2):
    ans += A[i+K-1] - A[i-1]
print(ans)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
from collections import defaultdict

n = int(input())
graph = defaultdict(list)

# グラフにコストを格納
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))

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


# コストの初期化
INF = 1 << 60
dist = [INF] * (n + 1)
dist[k] = 0

#　スタート地点
q = [(0, k)]

# ３からの距離
while q:
    cost, curr = heappop(q)
    if cost > dist[curr]:
        continue
    for after, nc in graph[curr]:
        if cost + nc < dist[after]:
            dist[after] = cost + nc
            heappush(q, (cost + nc, after))

print("\n".join(map(str, (dist[x] + dist[y]
                          for x, y in (map(int, input().split()) for _ in range(q))))))

Submission status: Runtime Error

Solution code:
import sys

TO_K = []
TREE = []
DISTANCE = []

def dfs(child, parent):
    for i_node in TREE[parent]:
        if i_node[0] == child:
            TO_K[child] = TO_K[parent] + i_node[1]

    for i_gch in TREE[child]:
        if i_gch[0] == parent:
            TO_K[child] = TO_K[parent] + i_gch[1]
        else:
            dfs(i_gch[0], child)

    return


def main():
    n = int(input())
    abc = [[int(_) for _ in input().split()] for i in range(n-1)]
    q, k = map(int, input().split())
    xy = [[int(_) for _ in input().split()] for i in range(q)]

    global TO_K
    # index '0' is not used.
    TO_K = [0]*(n+1)

    global TREE
    # index '0' is not used.
    TREE = [[] for _ in range(n+1)]
    for a, b, c in abc:
        TREE[a].append([b, c])
        TREE[b].append([a, c])

    dfs(k, 0)

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


if __name__ == "__main__":
    main()
    sys.exit(0)

Submission status: Runtime Error

Solution code:
import sys

TO_K = []
TREE = []
DISTANCE = []

def dfs(child, parent):
    small, big = min(child, parent), max(child, parent)
    for i_distance in DISTANCE[small]:
        if i_distance[0] == big:
            TO_K[child] = TO_K[parent] + i_distance[1]

    for i_gch in TREE[child]:
        if i_gch == parent:
            continue
        dfs(i_gch, child)

    return


def main():
    n = int(input())
    abc = [[int(_) for _ in input().split()] for i in range(n-1)]
    q, k = map(int, input().split())
    xy = [[int(_) for _ in input().split()] for i in range(q)]

    global TO_K
    # index '0' is not used.
    TO_K = [0]*(n+1)

    global TREE
    global DISTANCE
    # index '0' is not used.
    TREE = [[] for _ in range(n+1)]
    DISTANCE = [[] for _ in range(n+1)]
    for a, b, c in abc:
        TREE[a].append(b)
        TREE[b].append(a)
        small, big = min(a,b), max(a, b)
        DISTANCE[small].append([big, c])

    dfs(k, 0)

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


if __name__ == "__main__":
    main()
    sys.exit(0)

Submission status: Runtime Error

Solution code:
N=int(input())
import sys
# sys.setrecursionlimit(10**6)
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())
D=[-1]*N
D[K-1]=0
def dfs(start, nowd):
    to=T[start]
    for t in to:
        next_node,c=t
        if D[next_node]!=-1:
            continue
        nextd=nowd+c
        D[next_node]=nextd
        dfs(next_node, nextd)
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())
tree = [[] for _ in range(N)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    tree[a-1].append((b-1,c))
    tree[b-1].append((a-1,c))

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

dis = [-1]*N
dis[K-1] = 0
def dfs(v,d):
    for i in tree[v]:
        d = dis[v]
        next,c = i
        if dis[next] == -1:
            d += c
            dis[next] = d
            dfs(next,d)
dfs(K-1,0)

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

Submission status: Runtime Error

Solution code:
def main():
    from collections import defaultdict
    import sys
    sys.setrecursionlimit(100000)
    n, *rem = map(int, open(0).read().split())
    t = 3 * (n - 1)
    abc = rem[:t]
    q, k = rem[t], rem[t + 1]
    xy = rem[t + 2:]

    m = [[] for _ in range(n + 1)]
    dist = defaultdict(dict)
    for a, b, c in zip(*[iter(abc)] * 3):
        m[a].append(b)
        m[b].append(a)

        dist[a].update({b: c})
        dist[b].update({a: c})

    vis = [False] * (n + 1)
    cost = [0] * (n + 1)
    vis[k] = True

    def dfs(frm, to):
        if vis[to]:
            return
        vis[to] = True
        cost[to] = cost[frm] + dist[frm][to]
        frm = to
        for to in m[frm]:
            dfs(frm, to)

    frm = k
    for to in m[frm]:
        dfs(frm, to)

    tmp = []
    for x, y in zip(*[iter(xy)] * 2):
        tmp.append(cost[x] + cost[y])

    ans = "\n".join(map(str, tmp))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    from collections import defaultdict
    import sys
    sys.setrecursionlimit(20000)
    n, *rem = map(int, open(0).read().split())
    t = 3 * (n - 1)
    abc = rem[:t]
    q, k = rem[t], rem[t + 1]
    xy = rem[t + 2:]

    m = [[] for _ in range(n + 1)]
    dist = defaultdict(dict)
    for a, b, c in zip(*[iter(abc)] * 3):
        m[a].append(b)
        m[b].append(a)

        dist[a].update({b: c})
        dist[b].update({a: c})

    vis = [False] * (n + 1)
    cost = [0] * (n + 1)
    vis[k] = True

    def dfs(frm, to):
        if vis[to]:
            return
        vis[to] = True
        cost[to] = cost[frm] + dist[frm][to]
        frm = to
        for to in m[frm]:
            dfs(frm, to)

    frm = k
    for to in m[frm]:
        dfs(frm, to)

    tmp = []
    for x, y in zip(*[iter(xy)] * 2):
        tmp.append(cost[x] + cost[y])

    ans = "\n".join(map(str, tmp))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    from collections import defaultdict, deque
    n, *rem = map(int, open(0).read().split())
    t = 3 * (n - 1)
    abc = rem[:t]
    q, k = rem[t], rem[t + 1]
    xy = rem[t + 2:]

    m = [[] for _ in range(n + 1)]
    dist = defaultdict(dict)
    for a, b, c in zip(*[iter(abc)] * 3):
        m[a].append(b)
        m[b].append(a)

        dist[a].update({b: c})
        dist[b].update({a: c})

    vis = [False] * (n + 1)
    cost = [0] * (n + 1)
    vis[k] = True

    def dfs(frm, to):
        if vis[to]:
            return
        vis[to] = True
        cost[to] = cost[frm] + dist[frm][to]
        frm = to
        for to in m[frm]:
            dfs(frm, to)

    frm = k
    for to in m[frm]:
        dfs(frm, to)

    tmp = []
    for x, y in zip(*[iter(xy)] * 2):
        tmp.append(cost[x] + cost[y])

    ans = "\n".join(map(str, tmp))
    print(ans)


if __name__ == '__main__':
    main()

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, b, c = a - 1, b - 1, c
    tree[a].append((b, c))
    tree[b].append((a, c))

limit = 100010
depth = [0] * limit

def dfs(v, p, d): # (現在の頂点v, vの親, 現在の距離)
    depth[v] = d
    for e in tree[v]:
        if e[0] == p: continue
        dfs(e[0], v, d + e[1])

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