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: Accepted

Solution code:
## abc070d: Transit Tree Path
import sys
from collections import deque
input = sys.stdin.readline

n = int(input())

T = [{} for _ in range(n)]
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    T[v1-1][v2-1] = d
    T[v2-1][v1-1] = d

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

visit = [False]*n
depth = [0]*n
que = deque()
que.append(k-1)
while que:
    p = que.popleft()
    visit[p] = True
    for c in T[p].keys():
        if visit[c]: continue
        depth[c] = depth[p] + T[p][c]
        que.append(c)

for _ in range(q):
    v1,v2 = map(int, input().split())
    print(depth[v1-1]+depth[v2-1])

Submission status: Accepted

Solution code:
## abc070d: Transit Tree Path

from collections import deque

n = int(input())

T = [{} for _ in range(n)]
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    T[v1-1][v2-1] = d
    T[v2-1][v1-1] = d

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

visit = [False]*n
depth = [0]*n
que = deque()
que.append(k-1)
while que:
    p = que.popleft()
    visit[p] = True
    for c in T[p].keys():
        if visit[c]: continue
        depth[c] = depth[p] + T[p][c]
        que.append(c)

for _ in range(q):
    v1,v2 = map(int, input().split())
    print(depth[v1-1]+depth[v2-1])

Submission status: Accepted

Solution code:
## abc070d: Transit Tree Path

from collections import deque

n = int(input())

T = [{} for _ in range(n)]
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    T[v1-1][v2-1] = d
    T[v2-1][v1-1] = d

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

visit = [False]*n
depth = [0]*n
que = deque([[-1,k-1,0]])
while que:
    p,c,d = que.popleft()
    if visit[c]: continue
    visit[c] = True
    depth[c] = d
    if p>=0: depth[c] += depth[p]
    for cc in T[c].keys():
        if not visit[cc]: que.append([c,cc,T[c][cc]])

for _ in range(q):
    v1,v2 = map(int, input().split())
    print(depth[v1-1]+depth[v2-1])

Submission status: Accepted

Solution code:
## abc070d: Transit Tree Path

n = int(input())

T = [{} for _ in range(n)]
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    T[v1-1][v2-1] = d
    T[v2-1][v1-1] = d

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

visit = [False]*n
depth = [0]*n
stack = [[-1,k-1,0]]
while stack:
    p,c,d = stack.pop()
    if visit[c]: continue
    visit[c] = True
    depth[c] = d
    if p>=0: depth[c] += depth[p]
    for cc in T[c].keys():
        if not visit[cc]: stack.append([c,cc,T[c][cc]])

for _ in range(q):
    v1,v2 = map(int, input().split())
    print(depth[v1-1]+depth[v2-1])

Submission status: Accepted

Solution code:
# abc070d: Transit Tree Path

n = int(input())

T = [[] for _ in range(n)]
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    v1,v2 = v1-1,v2-1
    T[v1].append([v1,v2,d])
    T[v2].append([v2,v1,d])

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

visit = [False]*(n)
depth = [0]*(n)
stack = [[-1,k-1,0]]
while stack:
    p,c,d = stack.pop()
    if visit[c]: continue
    visit[c] = True
    depth[c] = d
    if p>=0: depth[c] += depth[p]
    for pp,cc,dd in T[c]:
        if not visit[cc]: stack.append([pp,cc,dd])

for _ in range(q):
    v1,v2 = map(int, input().split())
    print(depth[v1-1]+depth[v2-1])

Submission status: Accepted

Solution code:
## abc070d: Transit Tree Path

n = int(input())

T = [[] for _ in range(n+1)]
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    T[v1].append([v1,v2,d])
    T[v2].append([v2,v1,d])

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

visit = [False]*(n+1)
depth = [0]*(n+1)
stack = [[0,k,0]]
while stack:
    p,c,d = stack.pop()
    if visit[c]: continue
    visit[c] = True
    depth[c] = depth[p] + d
    for pp,cc,dd in T[c]:
        if not visit[cc]: stack.append([pp,cc,dd])

for _ in range(q):
    v1,v2 = map(int, input().split())
    print(depth[v1]+depth[v2])

Submission status: Accepted

Solution code:
## abc070d: Transit Tree Path

n = int(input())

T = [None]*(n+1)
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    if(T[v1] is None): T[v1] = [[v1,v2,d]]
    else: T[v1].append([v1,v2,d])
    if(T[v2] is None): T[v2] = [[v2,v1,d]]
    else: T[v2].append([v2,v1,d])

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

visit = [False]*(n+1)
depth = [0]*(n+1)
stack = [[0,k,0]]
while stack:
    p,c,d = stack.pop()
    if visit[c]: continue
    visit[c] = True
    depth[c] = depth[p] + d
    for pp,cc,dd in T[c]:
        if not visit[cc]: stack.append([pp,cc,dd])

for _ in range(q):
    v1,v2 = map(int, input().split())
    print(depth[v1]+depth[v2])

Submission status: Accepted

Solution code:
## abc070d: Transit Tree Path
 
n = int(input())
 
T = [None]*(n+1)
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    if(T[v1] is None): T[v1] = [[v1,v2,d]]
    else: T[v1].append([v1,v2,d])
    if(T[v2] is None): T[v2] = [[v2,v1,d]]
    else: T[v2].append([v2,v1,d])

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

depth = [0]*(n+1)
visit = [False]*(n+1)
depth[k] = 0
visit[k] = True
stack = T[k]
while stack:
    p,c,d = stack.pop()
    if visit[c]: continue
    visit[c] = True
    depth[c] = depth[p] + d
    for pp,cc,dd in T[c]:
        if not visit[cc]: stack.append([pp,cc,dd])
 
for _ in range(q):
    v1,v2 = map(int, input().split())
    print(depth[v1]+depth[v2])

Submission status: Accepted

Solution code:
## abc070d: Transit Tree Path

n = int(input())

T = [None]*(n+1)
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    if(T[v1] is None): T[v1] = [[v1,v2,d]]
    else: T[v1].append([v1,v2,d])
    if(T[v2] is None): T[v2] = [[v2,v1,d]]
    else: T[v2].append([v2,v1,d])

depth = [0]*(n+1)

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

is_visit = [False]*(n+1)
p,c,d = 0,k,0
depth[c] = d
is_visit[c] = True
stack = T[c]
while stack:
    p,c,d = stack.pop()
    if is_visit[c]: continue
    is_visit[c] = True
    depth[c] = depth[p] + d
    for pp,cc,dd in T[c]:
        if not is_visit[cc]: stack.append([pp,cc,dd])

for _ in range(q):
    v1,v2 = map(int, input().split())
    print(depth[v1]+depth[v2])

Submission status: Accepted

Solution code:
n=int(input())
abc=[list(map(int,input().split())) for _ in [0]*(n-1)]
q,k=map(int,input().split())
xy=[list(map(int,input().split())) for _ in [0]*q]

g=[[] for _ in [0]*n]
[g[b-1].append([a-1,c]) for a,b,c in abc]
[g[a-1].append([b-1,c]) for a,b,c in abc]

inf=10**15
dist=[None for _ in [0]*n]
dist[k-1]=0
q=[k-1]
while q:
    i=q.pop()
    gg=g[i]
    for j,k in gg:
        if dist[j]==None:
            dist[j]=dist[i]+k
            q.append(j)
for x,y in xy:
    print(dist[x-1]+dist[y-1])

Submission status: Accepted

Solution code:
import itertools
import math

def dfs(N,E,start):
    d = [-1] * (N + 1)
    d[start] = 0
    q = [start]
    while q:
        now = q.pop()
        vertexes = E[now]
        for to in vertexes:
            if d[to] == -1:
                d[to] = d[now] + E[now][to]
                q.append(to)
    return d
N = int(input())
E = [{} for _ in range(N + 1)]
for _ in range(N-1):
    a,b,c = map(int, input().split(" "))
    E[a][b] = c
    E[b][a] = c

Q, K = map(int, input().split(" "))
d = dfs(N,E,K)
AB = [list(map(int, input().split(" "))) for _ in range(Q)]
for a,b in AB:
    print(d[a] + d[b])

Submission status: Accepted

Solution code:
N = int(input())
ABC = [list(map(int,input().split())) for _ in [0]*(N-1)]
Q,K = map(int,input().split())
XY = [list(map(int,input().split())) for _ in [0]*Q]

E = [{} for _ in [0]*N]
for a,b,c in ABC:
    E[a-1][b-1] = c
    E[b-1][a-1] = c

def dist_dfs_tree(N,E,start):
    d = [-1]*N
    d[start] = 0
    q = [start]
    while q:
        i = q.pop()
        ci = d[i]
        for j,cj in E[i].items():
            if d[j] !=-1:continue
            d[j] = ci+cj
            q.append(j)
    return d

d = dist_dfs_tree(N,E,K-1)
for x,y in XY:
    print(d[x-1]+d[y-1])

Submission status: Accepted

Solution code:
import heapq
WHITE = 0
GRAY = 1
BLACK = 2
INFTY = 10**16
def dijkstra(s, VC):
    color = [WHITE for i in range(N+1)]
    d = [INFTY for i in range(N+1)]
    d[s] = 0
    pq = []
    heapq.heappush(pq, (0, s))

    while len(pq) != 0:
        u = heapq.heappop(pq)[1]
        color[u] = BLACK

        for v, c in VC[u]:
            if color[v] != BLACK:
                if d[u] + c < d[v]:
                    d[v] = d[u] + c
                    color[v] = GRAY
                    heapq.heappush(pq, (d[v], v))

    return d

N = int(input())
V = [[] for i in range(N+1)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    V[a].append([b, c])
    V[b].append([a, c])
Q, K = map(int, input().split())
d = dijkstra(K, V)
for i in range(Q):
    x, y = map(int, input().split())
    print(d[x] + d[y])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
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
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: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
G=[[] for i in range(n)]
for i in range(n-1):
    a,b,c=[int(v)-1 for v in input().split()]
    c+=1
    G[a].append((b,c))
    G[b].append((a,c))
q,k=[int(v) for v in input().split()]
k=k-1
stack=[k]
dis=[-1]*n
dis[k]=0
while stack!=[]:
    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=[int(v)-1 for v in input().split()]
    print(dis[x]+dis[y])

Submission status: Accepted

Solution code:
n=int(input())
G=[[] for i in range(n)]
for i in range(n-1):
    a,b,c=[int(v)-1 for v in input().split()]
    c+=1
    G[a].append((b,c))
    G[b].append((a,c))
q,k=[int(v) for v in input().split()]
k=k-1
stack=[k]
dis=[-1]*n
dis[k]=0
while stack!=[]:
    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=[int(v)-1 for v in input().split()]
    print(dis[x]+dis[y])

Submission status: Accepted

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

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


q, k = [ int(v) for v in input().split() ]
k -= 1

shortest_list = [-1 for i in range(n)]
shortest_list[k] = 0

searching_list = [k]

while searching_list != []:

    new_search_list = []
    for i in searching_list:
        for j in connect_list[i]:
            x, y = j
            if shortest_list[x] == -1:
                shortest_list[x] = y + shortest_list[i]
                new_search_list.append(x)
    searching_list = new_search_list


for i in range(q):
    a, b = [ int(v)-1 for v in input().split() ]
    print(shortest_list[a] + shortest_list[b])

Submission status: Accepted

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
while stack!=[]:
    new=[]
    for j in stack:
        d=dis[j]
        for i in G[j]:
            if dis[i[0]]==-1:
                dis[i[0]]=d+i[1]
                new.append(i[0])
    stack=new
for i in range(q):
    x,y=map(int,input().split())
    x=x-1
    y=y-1
    print(dis[x]+dis[y])

Submission status: Accepted

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
while stack!=[]:
    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: Accepted

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
from collections 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: Accepted

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

Submission status: Accepted

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
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: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
abc = [LIST() for _ in range(N-1)]
graph = defaultdict(list)
for a, b, c in abc:
	graph[a-1].append((b-1, c))
	graph[b-1].append((a-1,c))

Q, K = MAP()
xy = [LIST() for _ in range(Q)]

dist = [-1]*N  # K から各頂点への最短距離
dist[K-1] = 0

def dfs(node):
	for to, cost in graph[node]:
		if dist[to] != -1:
			continue
		dist[to] = dist[node]+cost
		dfs(to)
dfs(K-1)
# print(dist)

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

Submission status: Accepted

Solution code:
import sys
from collections import deque


fin = sys.stdin.readline
N = int(fin())
adj = [[] for _ in range(N)]
w = {}
for _ in range(N - 1):
    a, b, c = [int(elem) for elem in fin().split()]
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)
    w[a, b] = c
    w[b, a] = c

Q, K = [int(elem) for elem in fin().split()]
K -= 1
queries = tuple(tuple(int(elem) - 1 for elem in fin().split()) for _ in range(Q))
dist_from_root = {K: 0}
nodes = deque()
nodes.append(K)
while nodes:
    node = nodes.popleft()
    dist = dist_from_root[node]
    for neighbor in adj[node]:
        if neighbor not in dist_from_root:
            dist_from_root[neighbor] = dist + w[node, neighbor]
            nodes.append(neighbor)

for x, y in queries:
    print(dist_from_root[x] + dist_from_root[y])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)

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: Accepted

Solution code:
import numpy as np
from collections import defaultdict
from heapq import heappush, heappop


def djkstra_adj_list(adj_list, src):
    dist = defaultdict(lambda: np.inf)
    dist[src] = 0

    prev = defaultdict(lambda: None)

    queue = []
    heappush(queue, (dist[src], src))

    while len(queue) > 0:
        dist_u, u = heappop(queue)
        vs = adj_list[u]
        for v, weight in vs:
            alt = dist_u + weight
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
                heappush(queue, (alt, v))

    return dist, prev


def djkstra_adj_mat(adj_mat, src):
    dist = defaultdict(lambda: np.inf)
    dist[src] = 0

    prev = defaultdict(lambda: None)

    queue = []
    heappush(queue, (dist[src], src))

    while len(queue) > 0:
        dist_u, u = heappop(queue)
        vs = np.argwhere(adj_mat[u] > 0).flatten()
        for v in vs:
            weight = adj_mat[u, v]
            alt = dist_u + weight
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
                heappush(queue, (alt, v))

    return dist, prev


def main():
    N = int(input())

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

    for _ 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

    dist, prev = djkstra_adj_list(adj_list, K)

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

    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def solve(n_query, q_query, k):
    d = defaultdict(list)
    for a, b, c in n_query:
        d[a].append((c, b))
        d[b].append((c, a))

    from_k = dijkstra(n+1, d, k)
    ans = []
    for x, y in q_query:
        x_to_k = from_k[x]
        k_to_y = from_k[y]

        ans.append(x_to_k + k_to_y)
    #    print("{0}->{1}: {2} |{3}->{4}: {5}".format(x, k, x_to_k, k, y, k_to_y))

    return ans


def dijkstra(vertex, g, sp):
    d = [float('inf')] * vertex
    d[sp] = 0
    heap = [(d[sp], sp)]

    while heap:
        du, u = heappop(heap)
        for length, v in g[u]:

            if d[v] > du + length:
                d[v] = du + length
                heappush(heap, (d[v], v))
    return d


if __name__ == '__main__':
    n = int(input())
    par, rank = [-1]*(n+1), [0]*(n+1)
    diff_weight = [0]*(n+1)
    is_via_root = [1]*(n+1)
    n_query = []
    q_query = []

    for _ in range(n-1):
        a, b, c = map(int, input().split())
        n_query.append((a, b, c))
    q, k = map(int, input().split())
    for _ in range(q):
        x, y = map(int, input().split())
        q_query.append((x, y))

    ans = solve(n_query, q_query, k)
    for a in ans:
        print(a)

Submission status: Accepted

Solution code:
import heapq

N = int(input())
graph = [[] for i in range(N+1)]
visited = [False] * (N+1)
cost = [10**20 for i in range(N+1)]

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

for cr in graph[K]:
    heapq.heappush(q, cr)
visited[K] = True
cost[K] = 0

while q:
    c, r = heapq.heappop(q)
    
    if not visited[r]:
        visited[r] = True
        cost[r] = c
        
        for c_n, r_n in graph[r]:
            if not visited[r_n]:
                heapq.heappush(q, (c+c_n, r_n))
                
for i in range(Q):
    x, y = map(int, input().split())
    print(cost[x] + cost[y])

Submission status: Accepted

Solution code:
# 2019/07/12
# DFS ver
# リストにしてみた

import sys

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

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

import sys

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

Solution code:
# 2019/07/11

import sys
from heapq import heappop,heappush

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))


def dijkstra(s):
    d=[float('inf')]*n
    visited=[False]*n
    d[s]=0
    visited[s]=True
    que=[]
    for e in edge[s]:
        heappush(que,e)
    while que:
        c,v=heappop(que)
        if visited[v]:continue
        d[v]=c
        visited[v]=True
        for cost,vtx in edge[v]:
            if visited[vtx]:continue
            hq=(cost+d[v],vtx)
            heappush(que,hq)

    return d

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

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

Submission status: Accepted

Solution code:
# 2019/07/11

from heapq import heappop,heappush

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))


def dijkstra(s):
    d=[float('inf')]*n
    visited=[False]*n
    d[s]=0
    visited[s]=True
    que=[]
    for e in edge[s]:
        heappush(que,e)
    while que:
        c,v=heappop(que)
        if visited[v]:continue
        d[v]=c
        visited[v]=True
        for cost,vtx in edge[v]:
            if visited[vtx]:continue
            hq=(cost+d[v],vtx)
            heappush(que,hq)

    return d

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

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

Submission status: Accepted

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 - 1)]

# クエリ数と経由ノード
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: Accepted

Solution code:
from collections import deque
N = int(input())
V = {i: [] for i in range(1, N+1)}
for _ in range(N-1):
    a, b, c = map(int, input().split())
    V[a].append((b, c))
    V[b].append((a, c))
nq, k = map(int, input().split())
Q = []
for _ in range(nq):
    x, y = map(int, input().split())
    Q.append((x, y))

dist = {i: 0 for i in range(1, N+1)}
dq = deque()
dq.append(k)
dist[k] = 0
vstd = {i: False for i in range(1, N+1)}
while len(dq) > 0:
    u = dq.popleft()
    vstd[u] = True
    for vw in V[u]:
        v, w = vw
        if vstd[v]:
            continue
        dq.append(v)
        dist[v] = dist[u] + w

for q in Q:
    x, y = q
    print(dist[x] + dist[y])

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N = I()
abc = LIR(N-1)
Q, K = LI()
xy = LIR(Q)


K = K

utov = [[] for i in range(N+1)]
for a, b, c in abc:
    utov[a].append((b,c))
    utov[b].append((a,c))

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

q = deque()
q.append(K)
bfs_map[K] = 0

while q:
    u = q.popleft()
    for v, cost in utov[u]:
        if (bfs_map[v] == -1) or (bfs_map[v] > bfs_map[u]+cost):
            bfs_map[v] = bfs_map[u] + cost
            q.append(v)


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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
"""
def gcd(a,b):
    if a == 0:
        return b
    return gcd(b%a,a)
n = I()
a = IR(n)
l = a[0]
for i in range(1,n):
    g = gcd(l,a[i])
    l *= a[i]//g
print(l)
"""

#B
import queue
n = I()
v = [[] for i in range(n)]
for i in range(n-1):
    a,b,c = LI()
    a -= 1
    b -= 1
    v[a].append([b,c])
    v[b].append([a,c])
Q,k = LI()
d = [-1 for i in range(n)]
d[k-1] = 0
q = queue.Queue()
q.put(k-1)
while not q.empty():
    x = q.get()
    for y,c in v[x]:
        if d[y] == -1:
            d[y] = d[x]+c
            q.put(y)
for i in range(Q):
    x,y = LI()
    x -= 1
    y -= 1
    print(d[x]+d[y])
#C

#D

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
"""
def gcd(a,b):
    if a == 0:
        return b
    return gcd(b%a,a)
n = I()
a = IR(n)
l = a[0]
for i in range(1,n):
    g = gcd(l,a[i])
    l *= a[i]//g
print(l)
"""

#B
n = I()
v = [[] for i in range(n)]
for i in range(n-1):
    a,b,c = LI()
    a -= 1
    b -= 1
    v[a].append([b,c])
    v[b].append([a,c])
Q,k = LI()
d = [-1 for i in range(n)]
d[k-1] = 0
q = deque()
q.append(k-1)
while q:
    x = q.popleft()
    for y,c in v[x]:
        if d[y] == -1:
            d[y] = d[x]+c
            q.append(y)
for i in range(Q):
    x,y = LI()
    x -= 1
    y -= 1
    print(d[x]+d[y])
#C

#D

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T