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

Solution (Python):
import heapq
def dijkstra_heap(s,node_edges):
    '''
    ノードの入力は0-indexedに修正してから用いる
    returnはノードごとの最小コストを格納したリスト
    '''
    
    d = [float("inf")] * n
    used = [False] * n 
    d[s] = 0
    used[s] = True
    edgelist = []
    
    for e in node_edges[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        
        minedge = heapq.heappop(edgelist)
        
        if used[minedge[1]]:
            continue
        v = minedge[1]
        
        d[v] = minedge[0]
        used[v] = True
        for e in node_edges[v]:
            if not used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

n = int(input())
node_edges = [[] for _ in range(n)]
for i in range(n-1):
    start, end, cost = map(int,input().split())
    start -= 1
    end -= 1
    node_edges[start].append([cost, end])
    node_edges[end].append([cost, start])
num_q, stop = map(int,input().split())
stop -= 1

dist_from_stop = dijkstra_heap(stop, node_edges)
ans_ls = [0] * num_q
for i in range(num_q):
    start, end = map(int,input().split())
    start -= 1
    end -= 1
    ans_ls[i] = dist_from_stop[start] + dist_from_stop[end]
for ans in ans_ls:
    print(ans)

Solution (Python):
import heapq
n = int(input())

def dijkstra_heap(s):
    
    d = [float("inf")] * n
    used = [False] * n 
    d[s] = 0
    used[s] = True
    edgelist = []
    
    for e in node_edges[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        
        minedge = heapq.heappop(edgelist)
        
        if used[minedge[1]]:
            continue
        v = minedge[1]
        
        d[v] = minedge[0]
        used[v] = True
        for e in node_edges[v]:
            if not used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

node_edges = [[] for i in range(n)]

for i in range(n-1):
    start, end, cost = map(int,input().split())
    start -= 1
    end -= 1
    node_edges[start].append([cost, end])
    node_edges[end].append([cost, start])

num_q, stop = map(int,input().split())
stop -= 1
d_ls = dijkstra_heap(stop)

ans_ls = [0] * num_q
for i in range(num_q):
    start, end = map(int,input().split())
    start -= 1
    end -= 1
    total_dist = d_ls[start] + d_ls[end]
    ans_ls[i] = total_dist
for ans in ans_ls:
    print(ans)

Solution (Python):
from collections import deque

n = int(input())
to = [[] for _ in range(n)]

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

dist = [0 for _ in range(n)]
visited = [False for _ in range(n)]

def dfs(root):
    d = deque()
    d.append(root)
    while len(d) > 0:
        v = d.pop()
        visited[v] = True
        for u, c in to[v]:
            if visited[u]:
                continue
            d.append(u)
            dist[u] = dist[v]+c

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

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

Solution (Python):


import sys








from collections import deque                





















def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n = ii()
    adj = [[] for _ in range(n)]

    for _ in range(n-1):
        a, b, dist = mi()
        a -= 1
        b -= 1
        adj[a].append((b, dist))
        adj[b].append((a, dist))
    
    q, k = mi()
    k -= 1
    query = [lmi_0() for _ in range(q)]

    dist_from_k = [0] * n    
    visited = [False] * n
    def bfs_queue_traverse(start):
        queue = deque()    
        queue.append([start, 0])
        while queue:
            current, dist = queue.popleft()
            if not visited[current]:
                visited[current] = True
                dist_from_k[current] = dist
                for v, next_dist in adj[current]:
                    if not visited[v]:
                        queue.append((v, dist + next_dist))
    
    bfs_queue_traverse(k)
    for x, y in query:
        print(dist_from_k[x] + dist_from_k[y])



if __name__ == "__main__":
    main()

Solution (Python):
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
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
dist[K-1] = 0

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

dfs(K-1)


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

Solution (Python):
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
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
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)


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

Solution (Python):
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
abc = [LIST() for _ in range(N-1)]
Q, K = MAP()
xy = [LIST() for _ in range(Q)]

connection = [[] for _ in range(N)]
for a, b, c in abc:
	connection[a-1].append((b-1, c))
	connection[b-1].append((a-1, c))



step = [-1]*N

def DFS(N):
	for X, C in connection[N]:
		if step[X] == -1:
			step[X] = step[N] + C
			DFS(X)

step[K-1] = 0
DFS(K-1)



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

Solution (Python):
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
abc = [LIST() for _ in range(N-1)]
Q, K = MAP()
xy = [LIST() for _ in range(Q)]

connection = [[] for _ in range(N)]
for a, b, c in abc:
	connection[a-1].append((b-1, c))
	connection[b-1].append((a-1, c))



step = [-1]*N
step[K-1] = 0
q = deque([K-1])

while q:
	p = q.pop()
	for X, C in connection[p]:
		if step[X] == -1:
			step[X] = step[p] + C
			q.append(X)



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

Solution (Python):
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
abc = [LIST() for _ in range(N-1)]
Q, K = MAP()
xy = [LIST() for _ in range(Q)]

connection = [[] for _ in range(N)]
for a, b, c in abc:
	connection[a-1].append((b-1, c))
	connection[b-1].append((a-1, c))



step = [-1]*N
step[K-1] = 0
q = deque([K-1])

while q:
	p = q.popleft()
	for X, C in connection[p]:
		if step[X] == -1:
			step[X] = step[p] + C
			q.append(X)



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

Solution (Python):
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
ABC = [LIST() for _ in range(N-1)]
Q, K = MAP()
xy = [LIST() for _ in range(Q)]

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

for i in range(N-1):
	connection[ABC[i][0]-1].append((ABC[i][1]-1, ABC[i][2]))
	connection[ABC[i][1]-1].append((ABC[i][0]-1, ABC[i][2]))



step = [-1]*N
step[K-1] = 0

q = deque([K-1])


while q:
	N = q.popleft()
	for x, C in connection[N]:
		
		if step[x] == -1:
			step[x] = step[N] + C
			
			q.append(x)




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

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

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

d = [float('inf')] * (N + 1)
d[K] = 0
q = [K]
while q:
    i = q.pop()
    for j, c in links[i]:
        if d[i] + c < d[j]:
            d[j] = d[i] + c
            q.append(j)

result = []
for _ in range(Q):
    x, y = map(int, input().split())
    result.append(d[x] + d[y])
print('\n'.join(str(v) for v in result))

Solution (Python):
from heapq import heappop, heappush

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

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

d = [float('inf')] * (N + 1)
d[K] = 0

q = [(0, K)]
while q:
    _, u = heappop(q)
    for v, c in links[u]:
        alt = d[u] + c
        if d[v] > alt:
            d[v] = alt
            
            heappush(q, (alt, v))

result = []
for _ in range(Q):
    x, y = map(int, input().split())
    result.append(d[x] + d[y])
print('\n'.join(str(v) for v in result))

Solution (Python):
from collections import deque

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

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

d = [float('inf')] * (N + 1)
d[K] = 0
q = deque([K])
while q:
    i = q.popleft()
    di = d[i]
    for j, c in links[i]:
        if di + c < d[j]:
            d[j] = di + c
            q.append(j)

result = []
for _ in range(Q):
    x, y = map(int, input().split())
    result.append(d[x] + d[y])
print('\n'.join(str(v) for v in result))

Solution (Python):
from collections import deque

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

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

d = [float('inf')] * (N + 1)
d[K] = 0
q = deque([K])
while q:
    i = q.popleft()
    for j, c in links[i]:
        if d[i] + c < d[j]:
            d[j] = d[i] + c
            q.append(j)

result = []
for _ in range(Q):
    x, y = map(int, input().split())
    result.append(d[x] + d[y])
print('\n'.join(str(v) for v in result))

Solution (Python):
from heapq import heappop, heappush

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

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

d = [float('inf')] * (N + 1)
d[K] = 0

q = [(0, K)]
while q:
    _, u = heappop(q)
    for v in costs[u]:
        alt = d[u] + costs[u][v]
        if d[v] > alt:
            d[v] = alt
            
            heappush(q, (alt, v))

result = []
for _ in range(Q):
    x, y = map(int, input().split())
    result.append(d[x] + d[y])
print('\n'.join(str(v) for v in result))

Solution (Python):
from collections import deque

N = int(input())

gr = { i:[] for i in range(N+1)}

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

sta = deque([K])
dis = [10**10 for i in range(N+1)]
dis[K] = 0
sumi = [-1 for i in range(N+1)]

while len(sta) >= 1:
  a = sta.pop()
  sumi[a] += 1
  
  for j in gr[a]:
    if sumi[ j[0] ] != -1:
      continue
    else:
      sta.append(j[0])
      dis[j[0]] = dis[a] + j[1]
    
for i in range(Q):
  x,y = map(int,input().split())
  
  print(int(dis[x] + dis[y] ))

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())

g = [[] for _ in range(N+1)]

for i 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())

cost = [-1] * (N+1)
cost[K] = 0
temp = [K]
while temp:
    p = temp.pop()
    for q in g[p]:
        if cost[q[0]] == -1:
            cost[q[0]] = cost[p] + q[1]
            temp.append(q[0])

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

Solution (Python):
from collections import defaultdict, deque
def solve():
    N = int(input())
    G = defaultdict(list)

    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())
    K -= 1
    visited = [False] * N
    q = deque()
    q.append((K,0))
    visited[K] = True
    depth = [0] * N
    depth[K] = 0
    while len(q) > 0:
        now, d = q.popleft()
        for next,distance in G[now]:
            if not visited[next]:
                q.append((next,d+distance))
                visited[next] = True
                depth[next] = d+distance
        
    ans = []
    for i in range(Q):
        x,y = map(int,input().split())
        x -= 1
        y -= 1
        ans.append(depth[x] + depth[y])
    
    print(*ans,sep='\n')

if __name__ == '__main__':
    solve()

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

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

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

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

def dfs(v, pv=-1, d=0):
  dist[v] = d
  for nv, nd in G[v]:
    if nv == pv:
      continue
    dfs(nv, v, d+nd)

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

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

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

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


def w(k):
    que = deque()
    L[k] = 0
    que.append((k, -1))
    while que:
        n, p = que.popleft()
        for nn, nv in edges[n]:
            if nn == p: continue
            L[nn] = L[n] + nv
            que.append((nn, n))


def main():
    q, k = [int(_) for _ in input().split()]
    w(k)
    for i in range(q):
        a, b = [int(_) for _ in input().split()]
        print(L[a] + L[b])

if __name__ == '__main__':
    main()

Solution (Python):
from queue import deque

n = int(input())
edges = [set() for _ in range(n + 1)]
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    edges[a].add((c, b))
    edges[b].add((c, a))

q, k = map(int, input().split())
stack = deque([(0, k)])
costs = [0] * (n + 1)
visited = set()
while stack:
    c, p = stack.popleft()
    costs[p] = c
    visited.add(p)
    stack.extend((c + c2, p2) for c2, p2 in edges[p] if p2 not in visited)

ans = []
for _ in range(q):
    x, y = map(int, input().split())
    ans.append(costs[x] + costs[y])
print('\n'.join(map(str, ans)))

Solution (Python):
import heapq
import sys


def dijkstra(n, paths, root):
	total_cost = [10 ** 9] * (n + 1)
	total_cost[root] = 0

	not_checked = set(range(1, n + 1))
	checked = set()
	cur_node = root
	h = []

	while not_checked:
		checked.add(cur_node)
		not_checked -= {cur_node}

		for next_node, cost in paths[cur_node]:
			if next_node in not_checked:
				heapq.heappush(h, (total_cost[cur_node] + cost, next_node))

		if not_checked:
			cost, next_node = heapq.heappop(h)

			while next_node in checked:
				cost, next_node = heapq.heappop(h)

			cur_node = next_node
			total_cost[cur_node] = cost

	return total_cost
		

def main():
	readline = sys.stdin.readline

	n = int(readline().rstrip())

	path = []
	for _ in range(n + 1):
		path.append([])

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

	

	q, k = map(int, readline().rstrip().split())

	cost_from_k = dijkstra(n, path, k)

	for _ in range(q):
		x, y = map(int, readline().rstrip().split())
		print(cost_from_k[x] + cost_from_k[y])


if __name__ == '__main__':
	main()

Solution (Python):
from heapq import heappush, heappop

INF = 10**15

def dijkstra(s, edges):
    n = len(edges)
    que = []
    d = [INF] * n
    prev = [-1] * n
    d[s] = 0
    heappush(que, (0, s))

    while len(que) > 0:
        (c, v) = heappop(que)
        if d[v] < c:
            continue
        for (cc, w) in edges[v]:
            if d[w] > d[v] + cc:
                d[w] = d[v] + cc
                prev[w] = v
                heappush(que, (d[w], w))

    return d, prev

n = int(input())
edge = [[] for i in range(n)]
for i in range(n-1):
    ai, bi, ci = map(int, input().split())
    ai, bi = ai-1, bi-1
    edge[ai].append((ci, bi))
    edge[bi].append((ci, ai))

q, k = map(int, input().split())
x, y = [], []
for i in range(q):
    xi, yi = map(int, input().split())
    xi, yi = xi-1, yi-1
    x.append(xi)
    y.append(yi)

dist, prev = dijkstra(k-1, edge)

for i in range(q):
    print(dist[x[i]]+dist[y[i]])

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
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])
ans=[-1]*n
q,k=map(int,input().split())
ans[k-1]=0
d=deque([k-1])
while d:
  now=d.pop()
  for x in l[now]:
    a,b=x
    if ans[a]<0:
      ans[a]=ans[now]+b
      d.appendleft(a)
for i in range(q):
  a,b=map(int,input().split())
  print(ans[a-1]+ans[b-1])

Solution (Python):
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])
ans=[-1]*n
q,k=map(int,input().split())
ans[k-1]=0
from collections import deque
d=deque([k-1])
while d:
  now=d.pop()
  for x in l[now]:
    a,b=x
    if ans[a]<0:
      ans[a]=ans[now]+b
      d.appendleft(a)
for i in range(q):
  a,b=map(int,input().split())
  print(ans[a-1]+ans[b-1])

Solution (Python):
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])
ans=[-1]*n
q,k=map(int,input().split())
ans[k-1]=0
from collections import deque
d=deque([k-1])
while d:
  now=d.pop()
  for x in l[now]:
    a,b=x
    if ans[a]<0:
      ans[a]=ans[now]+b
      d.append(a)
for i in range(q):
  a,b=map(int,input().split())
  print(ans[a-1]+ans[b-1])

Solution (Python):



from heapq import heappop, heappush

INF = float("inf")

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    hq = [(0, s)]
    while hq:
        d, v = heappop(hq)
        if dist[v] < d:
            continue
        for child, child_d in G[v]:
            if dist[child] > dist[v] + child_d:
                dist[child] = dist[v] + child_d
                heappush(hq, (dist[child], child))
    return dist

n = int(input())
edge = [list(map(int, input().split())) for _ in range(n - 1)]
graph = [[] for _ in range(n)]

for a, b, c in edge:
    graph[a - 1].append((b - 1, c))
    graph[b - 1].append((a - 1, c))

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

d = dijkstra(n, graph, k - 1)

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

Solution (Python):

from collections import defaultdict, deque
N = int(input())
w = defaultdict(int)
edge = [[] for _ in range(N + 1)]

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

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

root = K
done = [True for _ in range(N + 1)]
done[root] = False
d = [0 for _ in range(N + 1)]
q = deque([root])

while q:
    parent = q.pop()
    for child in edge[parent]:
        if done[child]:
            key = str(parent) + "_" + str(child)
            done[child] = False
            d[child] = d[parent] + w[key]
            q.append(child)

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

Solution (Python):

from collections import defaultdict, deque
N = int(input())
w = defaultdict(int)
edge = [[] for _ in range(N + 1)]

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

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

root = K
done = [True for _ in range(N + 1)]
done[root] = False
d = [0 for _ in range(N + 1)]
q = deque([root])

while q:
    parent = q.pop()
    for child in edge[parent]:
        if done[child]:
            key = str(parent) + "_" + str(child)
            done[child] = False
            d[child] = d[parent] + w[key]
            q.append(child)

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

Solution (Python):
import sys
sys.setrecursionlimit(200000)


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



def dfs(v, parent=-1, distance=0):
    
    sum_distance[v] = distance
    for i, j in tree[v]:
        if i == parent:
            continue
        dfs(i, v, distance+j)


N = int(input())

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

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


sum_distance = [0]*N
dfs(K-1)


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

Solution (Python):
import sys
from collections import Counter
from collections import deque
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
tree=[[] for i in range(n+1)]
for i in range(n-1):
    a,b,c=mp()
    tree[a].append((b,c))
    tree[b].append((a,c))
q,k=mp()
dist=[-1]*(n+1)
dist[k]=0
deq=deque()
deq.append(k)

while len(deq):
    p=deq.popleft()
    for x,y in tree[p]:
        if dist[x]==-1:
            dist[x]=dist[p]+y
            deq.append(x)
for i in range(q):
    xi,yi=mp()
    print(dist[xi]+dist[yi])

Solution (Python):
from heapq import heappush, heappop

def dijkstra_heap(s):
    """頂点sから各頂点への最短距離"""
    d = [float("inf") for _ in range(N)]
    used = [True for _ in range(N)]  
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heappush(edgelist, e)
    while len(edgelist):
        min_edge = heappop(edgelist)
        
        if not used[min_edge[1]]:
            continue
        v = min_edge[1]
        d[v] = min_edge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heappush(edgelist, [e[0]+d[v], e[1]])
    return d

N = int(input())

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

for _ in range(N-1):
    x, y, z = map(int, input().split())
    edge[x-1].append([z, y-1])
    edge[y-1].append([z, x-1])

Q, K = map(int, input().split())
z = dijkstra_heap(K-1)

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

Solution (Python):
from collections import deque


class UnionFindWeighted:
    """ポテンシャル付きUnionFind"""
    def __init__(self, n):
        self.parent = [-1] * n
        self.weight = [0] * n
        self.cnt = n
        self.INF = 10 ** 18

    def root(self, x):
        """頂点xの根を求める"""
        if self.parent[x] < 0:
            return x
        rt = self.root(self.parent[x])
        self.weight[x] += self.weight[self.parent[x]]
        self.parent[x] = rt
        return rt

    def merge(self, x, y, weight):
        """頂点xを含む集合と頂点y含む集合を結合する
        weight: 頂点yに対する頂点xのポテンシャル(頂点xの方がweight高い)
        """
        root_x = self.root(x)
        root_y = self.root(y)
        if root_x == root_y:
            return
        if self.parent[root_x] < self.parent[root_y]:
            self.parent[root_x] += self.parent[root_y]
            self.parent[root_y] = root_x
            self.weight[root_y] = -weight + self.weight[x] - self.weight[y]
        else:
            self.parent[root_y] += self.parent[root_x]
            self.parent[root_x] = root_y
            self.weight[root_x] = weight - self.weight[x] + self.weight[y]
        self.cnt -= 1

    def is_same(self, x, y):
        """頂点x, yが同じ集合に属するかどうかを返す"""
        return self.root(x) == self.root(y)

    def diff(self, x, y):
        """頂点yに対する頂点xのポテンシャルを求める
        ただし、頂点x,y間にポテンシャルが定義されていない場合は INF を返す
        """
        if not self.is_same(x, y):
            return self.INF
        return self.weight[x] - self.weight[y]

    def get_size(self, x):
        """頂点xを含む集合の要素数を返す"""
        return -self.parent[self.root(x)]

    def get_cnt(self):
        """集合の個数を返す"""
        return self.cnt


n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]
qq, k = map(int, input().split())
query = [list(map(int, input().split())) for i in range(qq)]
k -= 1

tree = [[] for i in range(n)]
for a, b, cost in info:
    a -= 1
    b -= 1
    tree[a].append((b, cost))
    tree[b].append((a, cost))

uf = UnionFindWeighted(n)
root = k
par = {root: -1}
q = deque([root])
while q:
    v = q.pop()
    for nxt_v, cost in tree[v]:
        if nxt_v in par:
            continue
        else:
            par[nxt_v] = v
            uf.merge(nxt_v, par[nxt_v], cost)
            q.append(nxt_v)

for a, b in query:
    a -= 1
    b -= 1
    print(uf.diff(a, k) + uf.diff(b, k))