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 collections

stack = collections.deque()

N = int(input())
a = [-1] * (N-1)
b = [-1] * (N-1)
c = [-1] * (N-1)
cost = [0] * (N+1)
nodes = [[] for _ in range(N+1)]
yet = [int(ele) for ele in range(1, N+1)]

for i in range(N-1):
    a[i], b[i], c[i] = [int(ele) for ele in input().split()]  # 無効グラフなので、逆にも
    nodes[a[i]].append([b[i], c[i]])
    nodes[b[i]].append([a[i], c[i]])

Q, K = [int(ele) for ele in input().split()]
x = [-1] * Q
y = [-1] * Q

for i in range(Q):
    x[i], y[i] = [int(ele) for ele in input().split()]


def main():
    root = K
    stack.appendleft(root)
    bfs()

    for x_i, y_i in zip(x, y):
        print(cost[x_i] + cost[y_i])


def bfs():
    if len(stack) == 0:
        return

    parent = stack[-1]
    yet.remove(parent)
    for child in nodes[parent]:
        if child[0] in yet:
            stack.appendleft(child[0])
            cost[child[0]] = cost[parent] + child[1]
    else:
        stack.pop()
        bfs()


if __name__ == "__main__":
    main()

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())
k=k-1
stack=[k]
dis=[-1]*n
dis[k]=0
import deque
stack=deque(stack)
while len(stack)>0:
    now=stack.pop()
    d=dis[now]
    for i in G[now]:
        if dis[i[0]]==-1:
            dis[i[0]]=d+i[1]
            stack.append(i[0])
for i in range(q):
    x,y=map(int,input().split())
    x=x-1
    y=y-1
    print(dis[x]+dis[y])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

N = int(input())
maze = [list(map(int, input().split())) for i in range(N -  1)]
Q, K = map(int, input().split())
query = [list(map(int, input().split())) for i in range(Q)]

visited = [-1] * N
ans = 0

maze_hash = {}
#繋がっている点をハッシュで表現する
for i in maze:
    if (i[0] - 1) in maze_hash:
        maze_hash[i[0] - 1].append([i[1] - 1, i[2]])
    else:
        maze_hash[i[0] - 1] = [[i[1] - 1, i[2]]]
    if (i[1] - 1) in maze_hash:
        maze_hash[i[1] - 1].append([i[0] - 1, i[2]])
    else:
        maze_hash[i[1] - 1] = [[i[0] - 1, i[2]]]

def dfs(now, goal, visiterd, ans):
    if visited[now] == -1:
        visited[now] = ans
    else:
        visited[now] = min(visited[now], ans)
    if now == goal:
        return ans
    #次に行けるところを探す。
    tmp = 10000000000000000000
    for i in maze_hash[now]:
        if visited[i[0]] == -1:
           tmp = min(tmp, dfs(i[0], goal, visited, ans + i[1]))
    return tmp

#まずx から　K への経路を計算しておく。
for i in query:
    visited = [-1] * N
    ans = 0
    to_k = dfs(i[0] - 1, K - 1, visited, 0)
    visited = [-1] * N
    to_goal = dfs(K - 1, i[1] - 1, visited, to_k)
    print(to_goal)

Submission status: Runtime Error

Solution code:
n = int(input())
dat =[]
link = []
for i in range(n+1):
    link.append([])
cost = [-1] * (n + 1)

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

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

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

#print(link)

def search(curcost, current):
    #print("cost{0}, pos {1}: ".format(curcost, current))
    cost[current] = curcost
    for npos, ncost in link[current]:
        if cost[npos] != -1:
            # 戻らない
            continue
        search(curcost + ncost, npos)

search(0, k)

#print(cost)
for i in range(q):
    x,y = dat_q[i]
    print(cost[x] + cost[y])

Submission status: Runtime Error

Solution code:
# 2019/07/12
# DFS ver

import sys

input=sys.stdin.readline

n=int(input())
edge=[[] for _ in range(n)]
for _ in range(n-1):
    u,v,c=map(int,input().split())
    u-=1 ; v-=1
    edge[u].append((c,v))
    edge[v].append((c,u))

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

d=[0]*n
visited=[False]*n

def dfs(s,p):
    visited[s]=True
    for c,v in edge[s]:
        if visited[v] or p==v:continue
        d[v]=c+d[s]
        visited[v]=True
        dfs(v,s)
    return 


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

Submission status: Runtime Error

Solution code:
# http://wakabame.hatenablog.com/entry/2017/09/03/213522
# おまじない
import sys
input = sys.stdin.readline

# ノード数
N = int(input())

# 各要素は(元ノード, 先ノード, コスト)のタプルになっている
edges = [list(map(int, input().split())) for i in range(N)]

# クエリ数と経由ノード
Q, K = map(int, input().split())

# クエリ一覧
xy = [list(map(int, input().split())) for i in range(Q)]


# まず経由地から各ノードのへの距離をメモする
def BFS(K, edges, N):
    # ノード分のリストを持ったリストの定義
    # ノード番号はインデックス-1に対応．つながっている先のノードとそこへのコストのタプルが入る
    roots = [ [] for i in range(N) ]
    for a, b, c in edges:
        roots[a-1] += [(b-1, c)]
        roots[b-1] += [(a-1, c)]
    # memo
    dist = [-1] * N
    # たどり着いたノードのリスト
    stack = []
    stack.append(K)
    dist[K] = 0
    while stack:
        label = stack.pop(-1)
        for i, c in roots[label]:
            # 初到達ならmemoしてstackに追加
            # これはグラフが木構造であるから言えること．そうでなければコスト最小値しか採用しては行けない？
            if dist[i] == -1:
                dist[i] = dist[label] + c
                stack += [i]
    return dist

distance = BFS(K - 1, edges, N)

for i in range(Q):
    print(distance[xy[i][0] - 1] + distance[xy[i][1] - 1])

Submission status: Runtime Error

Solution code:
# http://wakabame.hatenablog.com/entry/2017/09/03/213522
# おまじない
import sys
input = sys.stdin.readline

# ノード数
N = int(input())

# 各要素は(元ノード, 先ノード, コスト)のタプルになっている
edges = [list(map(int, input().split())) for i in range(N)]

# クエリ数と経由ノード
Q, K = map(int, input().split())

# クエリ一覧
xy = [list(map(int, input().split())) for i in range(Q)]


# まず経由地から各ノードのへの距離をメモする
def BFS(K, edges, N):
    # ノード分のリストを持ったリストの定義
    # ノード番号はインデックス-1に対応．つながっている先のノードとそこへのコストのタプルが入る
    roots = [ [] for i in range(N) ]
    for a, b, c in edges:
        roots[a-1] += [(b-1, c)]
        roots[b-1] += [(a-1, c)]
    # memo
    dist = [-1] * N
    # たどり着いたノードのリスト
    stack = []
    stack.append(K)
    dist[K] = 0
    while stack:
        label = stack.pop(-1)
        for i, c roots[label]:
            # 初到達ならmemoしてstackに追加
            # これはグラフが木構造であるから言えること．そうでなければコスト最小値しか採用しては行けない？
            if dist[i] == -1:
                dist[i] = dist[label] + c
                stack += [i]
    return dist

distance = BFS(K - 1, edges, N)

for i in range(Q):
    print(distance[xy[i][0] - 1] + distance[xy[i][1] - 1])

Submission status: Runtime Error

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

tree = [{} for _ in range(N)]
for a, b, c in ABC:
	a, b = a - 1, b - 1
	tree[a][b] = c
	tree[b][a] = c

costs = {}
def dfs(current, cost):
	global costs
	costs[current] = cost
	for n in tree[current]:
		if n in costs:
			continue
		dfs(n, cost + tree[current][n])

dfs(K - 1, 0)

for x, y in XY:
	x, y = x - 1, y - 1
	print(costs[x] + costs[y])

#print(tree)
#print(costs)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100001)
def input():
    return sys.stdin.readline()[:-1]
from heapq import *

def dfs(s, es):
    dist = [None] * len(es)
    dist[s] = 0
    def ret(v, d):
        for u, c in es[v]:
            if dist[u] == None:
                dist[u] = dist[v] + c
                ret(u, dist[u])
    ret(s, 0)
    return dist

N = int(input())
es = [[] for i in range(N+1)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    es[a].append((b, c))
    es[b].append((a, c))
Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for i in range(Q)]
dist = dfs(K, es)
for i in range(Q):
    print(dist[xy[i][0]] + dist[xy[i][1]])

Submission status: Runtime Error

Solution code:
N = int(input())
edge = {}
neighbor = [[] for _ in range(N+1)]
for _ in range(N-1):
    a,b,c = map(int,input().split())
    neighbor[a].append(b)
    neighbor[b].append(a)
    edge[(a,b)] = c
    edge[(b,a)] = c
Q,K = map(int,input().split())
XY = [list(map(int,input().split())) for _ in range(Q)]

def bfs(Q,memo,current,Nei):
    for e in Nei[current]:
        if memo[e] == float('inf'):
            Q.append(e)
            memo[e] = memo[current] + edge[(current,e)]
    if len(Q) == 0:
        return memo
    else:
        next = Q.pop(0)
        return bfs(Q,memo,next,Nei)
queue = []
memo = [float('inf')]*(N+1)
memo[K] = 0
Ans = bfs(queue,memo,K,neighbor)

for x,y in XY:
    print(Ans[x] + Ans[y])

Submission status: Runtime Error

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

input = sys.stdin.readline

N = int(input())
T = [[] for _ in range(N+1)]

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

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

dist = [None]*(N+1)

def dfs(now,d) :
    dist[now] = d
    for to,c in T[now] :
        if dist[to] is not None :
            continue
        dfs(to,d+c)

dfs(K,0)

ans = [0]*Q

for _ in range(Q) :
    u,v = map(int,input().split())
    ans[i] = dist[u]+dist[v]

print(*ans,sep="\n")

Submission status: Runtime Error

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

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

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

dist = [None]*(N+1)

def dfs(now,d) :
    dist[now] = d
    for to,c in T[now] :
        if dist[to] is not None :
            continue
        dfs(to,d+c)

dfs(K,0)

ans = []

for i in range(Q) :
    u,v = map(int,input().split())
    ans.append(dist[u]+dist[v])

print(*ans,sep="\n")

Submission status: Runtime Error

Solution code:
N = int(input())
D = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    D[a].append((b, c))
    D[b].append((a, c))
Q, K = map(int, input().split())
DS = [-1] * (N + 2)


def dfs(c, p, d):
    DS[c] = d
    for r in D[c]:
        if r[0] == p:
            continue
        dfs(r[0], c, d + r[1])


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


main()

Submission status: Runtime Error

Solution code:
N = int(input())
D = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    D[a].append((b, c))
    D[b].append((a, c))
Q, K = map(int, input().split())
DS = [-1] * (N + 1)


def dfs(c, p, d):
    DS[c] = d
    for r in D[c]:
        if r[0] == p:
            continue
        dfs(r[0], c, d + r[1])


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


main()

Submission status: Runtime Error

Solution code:
N = int(input())
t = [[]for i in range(N+1)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    t[a].append([b,c])
    t[b].append([a,c])
Q,K = map(int,input().split())
#p is parent
#pcd is parent-child distance
d = [0 for i in range(N+1)]
def f(v,p,pcd):
    global t,d
    d[v] = pcd
    for c in t[v]:
        if c[0]!=p:
            f(c[0],v,pcd+c[1])
f(K,0,0)
for i in range(Q):
    x,y = map(int,input().split())
    print(d[x]+d[y])

Submission status: Runtime Error

Solution code:
import sys
N = int(input())
t = [[]for i in range(N+1)]
lines = sys.stdin.readlines()
for i in range(N-1):
    a,b,c = map(int,lines[i].split())
    t[a].append([b,c])
    t[b].append([a,c])
Q,K = map(int,lines[N-1].split())
#p is parent
#pcd is parent-child distance
d = [0 for i in range(N+1)]
def f(v,p,pcd):
    global t,d
    d[v] = pcd
    for c in t[v]:
        if c[0]!=p:
            f(c[0],v,pcd+c[1])
f(K,0,0)
for i in range(Q):
    x,y = map(int,lines[N+i].split())
    print(d[x]+d[y])

Submission status: Runtime Error

Solution code:
N = int(input())
t = [[]for i in range(N+1)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    t[a].append([b,c])
    t[b].append([a,c])
Q,K = map(int,input().split())
#p is parent
#pcd is parent-child distance
d = [0 for i in range(N+1)]
def f(v,p,pcd):
    global t,d
    d[v] = pcd
    for c in t[v]:
        if c[0]!=p:
            f(c[0],v,pcd+c[1])
f(K,0,0)
for i in range(Q):
    x,y = map(int,input().split())
    print(d[x]+d[y])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N = int(input())
##
v = defaultdict(lambda: [])
d = [defaultdict(lambda: 0) for _ in range(N+1)]
##
for i in range(N-1):
    a,b,c = map(int,input().split())
    v[a].append(b)
    v[b].append(a)
    d[a][b] = c
    d[b][a] = c
Q,K = map(int,input().split())
##
reached = defaultdict(lambda: 0)
def f(p,pcd):
    global v,d,K,reached
    reached[p] = 1
    d[K][p] = pcd
    for c in v[p]:
        if reached[c] == 0:
            f(c, pcd+d[p][c])
f(K,0)
##
for i in range(Q):
    x,y = map(int,input().split())
    print(d[K][x]+d[K][y])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N = int(input())
##
v = defaultdict(lambda: [])
d = defaultdict(lambda: defaultdict(lambda: 0))
##
for i in range(N-1):
    a,b,c = map(int,input().split())
    v[a].append(b)
    v[b].append(a)
    d[a][b] = c
    d[b][a] = c
Q,K = map(int,input().split())
##
reached = defaultdict(lambda: 0)
def f(p,pcd):
    global v,d,K,reached
    reached[p] = 1
    d[K][p] = pcd
    for c in v[p]:
        if reached[c] == 0:
            f(c, pcd+d[p][c])
f(K,0)
##
for i in range(Q):
    x,y = map(int,input().split())
    print(d[K][x]+d[K][y])

Submission status: Runtime Error

Solution code:
from collections import defaultdict

N = int(input())
edges = [list(map(int, input().split())) for _ in range(N - 1)]
Q, K = map(int, input().split())

graph = defaultdict(set)
for v, w, c in edges:
    graph[v].add((w, c))
    graph[w].add((v, c))

INF = 10 ** 9 + 7
dp = [INF] * (N + 1)
visited = [False] * (N + 1)

def dfs(v, p, d):    
    dp[v] = d
    visited[v] = True
    for j, c in graph[v]:
        if j == p or visited[j]:
            continue
        dfs(j, v, d + c)

dfs(K, 0, 0)

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict

N = int(input())
edges = [list(map(int, input().split())) for _ in range(N - 1)]
Q, K = map(int, input().split())

graph = defaultdict(set)
for v, w, c in edges:
    graph[v].add((w, c))
    graph[w].add((v, c))

INF = 10 ** 9 + 7
dp = [INF] * (N + 1)
visited = [False] * (N + 1)

def dfs(v, p, d):    
    dp[v] = d
    visited[v] = True
    for j, c in graph[v]:
        if j == p:
            continue
        dfs(j, v, d + c)

dfs(K, 0, 0)

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

Submission status: Runtime Error

Solution code:
# KからDFS -> xからKまでとyからKまで
n = int(input())
graph = [[] for _ in range(n)]
costs = [0 for _ in range(n)]

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

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


def dfs(cur, cost):
    for g in graph[cur]:
        if g[0] != k-1 and costs[g[0]] == 0:
            costs[g[0]] = g[1] + cost
            dfs(g[0], costs[g[0]])


dfs(k - 1, 0)

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

Submission status: Runtime Error

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

def dfs(idx, visited, conn, d, cur):
    visited[idx] = True
    for nex in conn[idx]:
        if not visited[nex[0]]:
            d[nex[0]] = cur + nex[1]
            d = dfs(nex[0], visited, conn, d, cur + nex[1])
    return d


def solve(N: int, A: "List[int]", B: "List[int]", C: "List[int]", Q: int, K: int, x: "List[int]", y: "List[int]"):

    conn = [[] for _ in range(N)]
    for j in range(N - 1):
        a = A[j] - 1
        b = B[j] - 1
        conn[a].append([b, C[j]])
        conn[b].append([a, C[j]])
    visited = [False] * N
    d = [0] * N
    d = dfs(K - 1, visited, conn, d, 0)
    for q in range(Q):
        s = x[q] - 1
        t = y[q] - 1
        ret = d[s] + d[t]
        print(ret)
    return


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)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def dfs(l,d,k):
  for i in l[k]:
    if d[i[0]]==-1:
      d[i[0]]=d[k]+i[1]
      dfs(l,d,i[0])

n=int(input())
l=[[] for i in range(n)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  l[a-1].append([b-1,c])
  l[b-1].append([a-1,c])
q,k=map(int,input().split())
d=[-1 for i in range(n)]
d[k-1]=0
dfs(l,d,k-1)
L=[list(map(int,input().split())) for i in range(q)]
for i in range(q):
  print(d[L[i][0]-1]+d[L[i][1]-1])

Submission status: Runtime Error

Solution code:
N=int(input())

NODES={}
for i in range(N-1):
    a,b,c=map(int,input().split())
    if not a in NODES:
        NODES[a] = []
    if not b in NODES:
        NODES[b] = []
    NODES[a].append((b, c))
    NODES[b].append((a, c))

Q,K=map(int,input().split())
MP=[-1]*(N+1)
MP[K]=0
def dfs(k):
    for i, c in NODES[k]:
        if MP[i] == -1:
            MP[i] = MP[k] + c
            dfs(i)

dfs(K)
# print(MP)
for l,r in [tuple(map(int,input().split())) for _ in range(Q)]:
    print(MP[l]+MP[r])

Submission status: Runtime Error

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


def main():
    n = int(input())
    graph = np.zeros((n + 1, n + 1))
    for i in range(n-1):
        a, b, c = [int(x) for x in input().split()]
        graph[a, b] = c
    graph = csr_matrix(graph)
    q, k = [int(x) for x in input().split()]
    dist = dijkstra(csgraph=graph, directed=False, indices=k)
    for j in range(q):
        l, r = [int(x) for x in input().split()]
        print(int(dist[l]+dist[r]))


main()

Submission status: Runtime Error

Solution code:
#from numpy import*
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**6)

def main():
    n=int(input())
    graph=[[0]*n for i 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
    graph=csr_matrix(graph)
    d = shortest_path(csgraph=graph)
    q,k=map(int,input().split())
    for i in range(q):
        a,b=map(int,input().split())
        print(int(d[a-1][k-1]+d[k-1][b-1]))
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def dfs(i, V, E):
    vi = V[i]
    for j, value in E[i].items():
        if V[j] > value + vi:
            V[j] = value + vi
            V = dfs(j, V, E)
    return V

INF = 10 ** 14
n = int(input())
V = [INF for _ in range(n + 1)]
E = [{} for _ in range(n + 1)]
for i in range(n - 1):
    ai, bi, ci = map(int, input().split())
    E[ai][bi] = ci
    E[bi][ai] = ci

q, k = map(int, input().split())
z = [list(map(int, input().split())) for _ in range(q)]
V[k] = 0

V = dfs(k, V, E)
for i in range(q):
    x, y = z[i]
    print(V[x] + V[y])

Submission status: Runtime Error

Solution code:
def dfs(v, parent):
    for tail, weight in adj[v]:
        if tail == parent:
            continue
        dist[tail] = dist[v] + weight
        dfs(tail, v)


n = int(input())
adj = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b, c = [int(x) for x in input().split()]
    adj[a].append((b, c))
    adj[b].append((a, c))
q, k = [int(x) for x in input().split()]
dist = [0] * (n + 1)
dfs(k, k)
for j in range(q):
    l, r = [int(x) for x in input().split()]
    print(dist[l] + dist[r])
# print(*data, sep='\n')

Submission status: Runtime Error

Solution code:
def dfs(v, parent):
    for edge in adj[v]:
        if edge[0] == parent:
            continue
        dist[edge[0]] = dist[v] + edge[1]
        dfs(edge[0], v)


n = int(input())
adj = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b, c = [int(x) for x in input().split()]
    adj[a].append((b, c))
    adj[b].append((a, c))
q, k = [int(x) for x in input().split()]
dist = [0] * (n + 1)
dfs(k, k)
for j in range(q):
    l, r = [int(x) for x in input().split()]
    print(dist[l] + dist[r])
# print(*data, sep='\n')

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import shortest_path
n = int(input())
mat=[[0]*n for i in range(n)]
for i in range(n-1):
    a, b, c = map(int, input().split())
    mat[a-1][b-1]=c
    mat[b-1][a-1]=c
q, k  = map(int, input().split())
distance = shortest_path(mat, directed = False, indices = [k-1], method = 'D')
for i in range(q):
    x, y = map(int, input().split())
    print(int(distance[0][x-1]+distance[0][y-1]))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)
INF = float('inf')

N = int(sys.stdin.readline())
ABC = [list(map(int, sys.stdin.readline().split())) for _ in range(N - 1)]
Q, K = list(map(int, sys.stdin.readline().split()))
X, Y = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(Q)]))


def dfs(v, a, graph, ret=None):
    ret = ret or {}
    ret[v] = a
    for u, w in graph[v]:
        if u in ret:
            continue
        dfs(u, a + w, graph, ret)
    return ret


#: :type: list of (list of (int, int))
graph = [[] for _ in range(N + 1)]
for a, b, c in ABC:
    graph[a].append((b, c))
    graph[b].append((a, c))

dists = dfs(K, 0, graph)
for x, y in zip(X, Y):
    print(int(dists[x] + dists[y]))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N = int(sys.stdin.readline())
ABC = [list(map(int, sys.stdin.readline().split())) for _ in range(N - 1)]
Q, K = list(map(int, sys.stdin.readline().split()))
X, Y = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(Q)]))


def dfs(v, a, graph, ret=None):
    ret = ret or {}
    ret[v] = a
    for u, w in graph[v]:
        if u in ret:
            continue
        dfs(u, a + w, graph, ret)
    return ret


#: :type: list of (list of (int, int))
graph = [[] for _ in range(N + 1)]
for a, b, c in ABC:
    graph[a].append((b, c))
    graph[b].append((a, c))

dists = dfs(K, 0, graph)
for x, y in zip(X, Y):
    print(int(dists[x] + dists[y]))

Submission status: Runtime Error

Solution code:
N=int(input())
edge=[list(map(int,input().split())) for i in range(N-1)]
inf=10**15
c=[[] for i in range(N)]
for i,j,w in edge:
    c[i-1].append((j-1,w))
    c[j-1].append((i-1,w))
Q,K=map(int, input().split())
d=[inf]*N
d[K-1]=0
v=[0]*N
def dfs(p,v,d):
    for n,w in c[p]:
        if v[n]==0:
            d[n]=min(d[n],d[p]+w)
            v[n]=1
            dfs(n,v,d)
dfs(K-1,v,d)
xy=[list(map(int,input().split())) for i in range(Q)]
for x,y in xy:
    print(d[x-1]+d[y-1])

Submission status: Runtime Error

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

dist = [-1 for i in range(n)]
q,k = map(int,input().split())
k -= 1
dist[k] = 0

def dfs(now,pre,d):
    dist[now] = d
    for p,q in data[now]:
        if p == pre:
            continue
        dfs(p,now,d+q)

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:
def dfs(v, d):
	global D
	D[v] = d
	for u,dd in G[v]:
		if D[u] is not None:
			continue
		dfs(u, d+dd)

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 = [None]*(N+1)
dfs(K, 0)
for _ in range(Q):
	x, y = map(int, input().split())
	print(D[x] + D[y])

Submission status: Runtime Error

Solution code:
def dfs(v, p, d):
	global D
	global S
	D[v-1] = d
	for g in G[v-1]:
		if S[g[0]-1]==0:
			continue
		S[g[0]-1] = 0
		dfs(g[0], v, d+g[1])

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

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

Submission status: Runtime Error

Solution code:
def dfs(v, p, d):
	global D
	global G
	D[v-1] = d
	while G[v-1]!=[]:
		g = G[v-1].pop()
		if g[0]==p:
			continue
		dfs(g[0], v, d+g[1])

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

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

Submission status: Runtime Error

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

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

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

dist = [None]*(N+1)

def set_dist(x,d):
  dist[x] = d
  for y,dd in edge[x]:
    if dist[y] is not None:
      continue
    set_dist(y,d+dd)

set_dist(K,0)

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

Submission status: Runtime Error

Solution code:
from scipy.sparse import lil_matrix
import sys
input = sys.stdin.readline

print(scipy.__version__())
N = int(input())
edge = lil_matrix((N+1,N+1))
 
for _ in range(N-1):
  a,b,c = map(int,input().split())
  edge[a,b] = c
 
Q,K = map(int,input().split())
 
from scipy.sparse.csgraph import dijkstra
dist = dijkstra(edge,directed = False, indices = K).astype(int)
 
for _ in range(Q):
  x,y = map(int,input().split())
  print(dist[x] + dist[y])

Submission status: Runtime Error

Solution code:
N = int(input())

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


Q, K = [int(i) for i in input().split()]
dist = [0] * (N + 1)
def dfs(cur, parent, d):
    dist[cur] = d
    for to, cost in E[cur]:
        if to == parent:
            continue
        dfs(to, cur, d + cost)
dfs(K, -1, 0)

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

Submission status: Runtime Error

Solution code:
N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))

edges = ABC[:]


def warshall_floyd(d, n):
    # d: グラフ二次元リスト
    # n: 頂点数 (0始まり)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

# グラフ無効グラフ化
graph = [[float("inf") for i in range(N)] for i in range(N)] 
for x,y,z in edges:
    graph[x-1][y-1] = z
    graph[y-1][x-1] = z
for i in range(N):
    graph[i][i] = 0 #自身のところに行くコストは０

#最短経路
shortest =  warshall_floyd(graph, N)
    
# 順列全探索
import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import itertools
line = R_LIST
for l in itertools.permutations(line):
    #print(l)
    tmp_len = 0
    for a,b in zip(l[:-1], l[1:]):
        tmp_len += shortest[a-1][b-1]

    #print(tmp_len)
    ans = min(ans, tmp_len)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**5)
n=int(input())
G=[[]for i in range(n+1)]
for i in range(n-1):
    a, b, c = map(int,input().split())
    G[a] += (b,c),
    G[b] += (a,c),
q, k = map(int,input().split())
d = [0]*(n+1) #kから各点への距離
def f(v,p,u): #v:今見ているとこ p:一つ前に見たとこ u:kからの距離
    d[v] = u
    for t, c in G[v]:
        if p != t:
            f(t,v,u+c)
f(k,0,0)
for i in range(q):
    x, y = map(int,input().split())
    print(d[x]+d[y])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
n=int(input())
G=[[]for i in range(n+1)]
for i in range(n-1):
    a, b, c = map(int,input().split())
    G[a] += (b,c)
    G[b] += (a,c)
q, k = map(int,input().split())
d = [0]*(n+1) #kから各点への距離
def f(v,p,u): #v:今見ているとこ p:一つ前に見たとこ u:kからの距離
    d[v] = u
    for t, c in G[v]:
        if p != t:
            f(t,v,u+c)
f(k,0,0)
for i in range(q):
    x, y = map(int,input().split())
    print(d[x]+d[y])

Submission status: Runtime Error

Solution code:
n = int(input())
edge = [[[] for i in range(2)] for j in range(n)]
dp = [-1] * n
for i in range(n - 1):
    a, b, c = map(int, input().split())
    edge[a - 1][0].append(b - 1)
    edge[a - 1][1].append(c)
    edge[b - 1][0].append(a - 1)
    edge[b - 1][1].append(c)


def distance(x, prev, d):
    dp[x] = d
    for i, j in zip(edge[x][0], edge[x][1]):
        if i == prev:
            continue
        if dp[i] != -1:
            continue
        distance(i, x, d + j)
    return

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

ans = []
distance(k, -1, 0)
for i in range(q):
    x, y = map(int, input().split())
    ans.append(dp[x - 1] + dp[y - 1])

for i in range(q):
    print(ans[i])