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

Solution (Python):


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

Solution (Python):


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):
    
    
    roots = [ [] for i in range(N) ]
    for a, b, c in edges:
        roots[a-1] += [(b-1, c)]
        roots[b-1] += [(a-1, c)]
    
    dist = [-1] * N
    
    stack = []
    stack.append(K)
    dist[K] = 0
    while stack:
        label = stack.pop(-1)
        for i, c in roots[label]:
            
            
            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])

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

Solution (Python):

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

Solution (Python):

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

Solution (Python):

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


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


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

Solution (Python):

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


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


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

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
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]])

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

INF = 10 ** 20
def dijkstra(s, edges):
    dist = [INF for _ in range(len(edges))]
    dist[s], h = 0, []
    heappush(h, (0, s))
    while (len(h)):
        dv, v = heappop(h)
        if dv > dist[v]:
            continue
        for u, cost in edges[v]:
            if dv + cost < dist[u]:
                dist[u] = dv + cost
                heappush(h, (dist[u], u))
    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 = dijkstra(K, es)
for i in range(Q):
    print(dist[xy[i][0]] + dist[xy[i][1]])

Solution (Python):
from collections import defaultdict
from heapq import heappush, heappop

def dijkstra(V, E, s):
    '''
    Input:
        V = list(range(N))
        E = defaultdict(dict)
        s (in V) : start vertex
    Output:
        dist: the list of the minimum cost from s to arbitrary vertex v in the given graph
    '''
    INF = float('inf')
    N = len(V)
    dist = [INF]*N
    heap = []
    heappush(heap, (0, s))
    while heap:
        d, v = heappop(heap)
        
        if d > dist[v]:
            continue
        dist[v] = d
        for u, c in E[v].items():
            temp = d + c
            if temp < dist[u]:
                heappush(heap, (temp, u))
    return dist

N = int(input())
V = list(range(N))
E = defaultdict(dict)
for _ in range(N-1):
    a, b, c = map(int, input().split())
    E[a-1][b-1] = c
    E[b-1][a-1] = c
Q, K = map(int, input().split())
dist = dijkstra(V, E, K-1)
for _ in range(Q):
    x, y = map(int, input().split())
    ans = dist[x-1] + dist[y-1]
    print(ans)

Solution (Python):
from collections import deque

def solve(n, a, b, c, q, k, x, y):
    E = {}
    G = {}
    for u, v, d in zip(a, b, c):
        if not u in E:
            E[u] = []
        if not v in E:
            E[v] = []
        E[u].append(v)
        E[v].append(u)
        G[u, v] = d
        G[v, u] = d
    dist = {}
    dist[k] = 0
    que = deque([k])
    while que:
        v = que.pop()
        for u in E[v]:
            if not u in dist:
                dist[u] = dist[v] + G[u,v]
                que.append(u)
    for i in range(q):
        print(dist[x[i]] + dist[y[i]])

n = int(input())
a = [0] * (n-1)
b = [0] * (n-1)
c = [0] * (n-1)
for i in range(n-1):
    a[i], b[i], c[i] = map(int, input().split())
q, k = map(int, input().split())
x = [0] * q
y = [0] * q
for i in range(q):
    x[i], y[i] = map(int, input().split())
solve(n, a, b, c, q, k, x, y)

Solution (Python):
import sys
import numpy as np

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

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())
K_to = [[] for _ in range(N + 1)]
visited = [0] * (N + 1)

def dfs(v, p, d):
    K_to[v] = d
    if not visited[p]:
        for to, c  in G[v]:
            if to == p:
                continue
            dfs(to, v, c + d)
    else:
        visited[p] = True
    return

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

Solution (Python):
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 i in range(Q) :
    u,v = map(int,input().split())
    ans[i] = dist[u]+dist[v]

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

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

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)

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

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

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)

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

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

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 = []

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

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

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

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

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

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

Solution (Python):
N = int(input())
abc = [list(map(int, input().split())) for _ in range(N - 1)]
Q, K = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(Q)]

class Tree:
  def __init__(s, N):
    s.D = [-1] * (N + 1)
    s.R = {}
  def setR(s, a, b, c):
    if a in s.R:
      s.R[a].append([b, c])
    else:
      s.R[a] = [[b, c]]
    if b in s.R:
      s.R[b].append([a, c])
    else:
      s.R[b] = [[a, c]]
  def setD(s, x):
    S = [[x, s.R[x]]]
    s.D[x] = 0
    while S:
      y, t = S.pop()
      k = s.D[y]
      for a, d in t:
        if s.D[a] == -1:
          s.D[a] = k + d
          S.append([a, s.R[a]])
  def getD(s, x):
    return s.D[x]

T = Tree(N)
for a, b, c in abc:
  T.setR(a, b, c)
T.setD(K)

for x, y in xy:
  print(T.getD(x) + T.getD(y))

Solution (Python):
from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist

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

Q,K = map(int,input().split())
dist = dijkstra(g,N,K-1)
for _ in range(Q):
    x,y = map(int,input().split())
    print(dist[x-1]+dist[y-1])

Solution (Python):
N = int(input())


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


Q,K = map(int,input().split())
xy = list(list(map(int,input().split()))for i in range(Q))

len_ = [float('inf')]*N  
len_[K-1] = 0 


queue = [K-1]
hoge = []
while queue != []:
    for i in queue:
        for b,c in S[i]:
            if len_[b] > len_[i]+c:
                hoge.append(b)
                len_[b] = len_[i]+c
    queue = hoge
    hoge = []


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

Solution (Python):
N = int(input())
S = [[]for i in range(N)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    S[a-1].append([b-1,c])
    S[b-1].append([a-1,c])
Q,K = map(int,input().split())
xy = list(list(map(int,input().split()))for i in range(Q))
len_ = [float('inf')]*N
len_[K-1] = 0
queue = [K-1]
hoge = []
while queue != []:
    for i in queue:
        for b,c in S[i]:
            if len_[b] > len_[i]+c:
                hoge.append(b)
                len_[b] = len_[i]+c
    queue = hoge
    hoge = []
for x,y in xy:
    print(len_[x-1]+len_[y-1])

Solution (Python):
N=int(input())
from collections import defaultdict
branch=defaultdict(dict)
for i in range(N-1):
    a,b,c=map(int,input().split())
    branch[a-1][b-1]=c
    branch[b-1][a-1]=c
Q,K=map(int,input().split())
dist=[float('inf')]*N
dist[K-1]=0
check={K-1}
while len(check)>0:
    now=check.pop()
    for nex,d in branch[now].items():
        if dist[nex]>dist[now]+d:
            dist[nex]=dist[now]+d
            check|={nex}
for i in range(Q):
    x,y=map(int,input().split())
    print(dist[x-1]+dist[y-1])

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush

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

dp = [-1] * (N + 1)
pq = []


dp[K] = 0
heappush(pq, (0, K))

while pq:
    cost, u = heappop(pq)
    
    for w, c in graph[u]:
        if dp[w] > -1:
            continue

        dp[w] = dp[u] + c
        heappush(pq, (dp[w], w))

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

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

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

Solution (Python):

from collections import defaultdict

import sys
input = sys.stdin.readline

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

    link = defaultdict(set)
    weight = defaultdict(int)
    for i in range(num - 1):
        a, b, c = map(int, input().split())
        link[a].add(b)
        link[b].add(a)
        weight[(min(a, b), max(a, b))] = c

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

    dist_data = [-1 for i in range(num + 1)]
    dist_data[k] = 0
    now_check = set()
    next_check = set()
    now_check.add(k)

    while len(now_check) > 0:
        for ele in now_check:
            now_dist = dist_data[ele]
            for now_ele in link[ele]:
                if dist_data[now_ele] != -1:
                    continue
                next_check.add(now_ele)
                dist_data[now_ele] = now_dist + weight[(min(now_ele, ele), max(now_ele, ele))]
        now_check = next_check
        next_check = set()

    for i in range(q_num):
        a, b = map(int, input().split())
        print(dist_data[a] + dist_data[b])



if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict

import sys
input = sys.stdin.readline

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

    link = defaultdict(set)
    weight = defaultdict(int)
    for i in range(num - 1):
        a, b, c = map(int, input().split())
        link[a].add(b)
        link[b].add(a)
        weight[(min(a, b), max(a, b))] = c

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

    dist_data = [-1 for i in range(num + 1)]
    dist_data[k] = 0
    now_check = set()
    next_check = set()
    now_check.add(k)

    while len(now_check) > 0:
        for ele in now_check:
            now_dist = dist_data[ele]
            for now_ele in link[ele]:
                if dist_data[now_ele] != -1:
                    continue
                next_check.add(now_ele)
                dist_data[now_ele] = now_dist + weight[(min(now_ele, ele), max(now_ele, ele))]
        now_check = next_check
        next_check = set()

    for i in range(q_num):
        a, b = map(int, input().split())
        print(dist_data[a] + dist_data[b])



if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict


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

    link = defaultdict(set)
    weight = defaultdict(int)
    for i in range(num - 1):
        a, b, c = map(int, input().split())
        link[a].add(b)
        link[b].add(a)
        weight[(min(a, b), max(a, b))] = c

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

    dist_data = [-1 for i in range(num + 1)]
    dist_data[k] = 0
    now_check = set()
    next_check = set()
    now_check.add(k)

    while len(now_check) > 0:
        for ele in now_check:
            now_dist = dist_data[ele]
            for now_ele in link[ele]:
                if dist_data[now_ele] != -1:
                    continue
                next_check.add(now_ele)
                dist_data[now_ele] = now_dist + weight[(min(now_ele, ele), max(now_ele, ele))]
        now_check = next_check
        next_check = set()

    for i in range(q_num):
        a, b = map(int, input().split())
        print(dist_data[a] + dist_data[b])



if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
from heapq import heappush, heappop
class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()
        
class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]
N = int(input())
gp = Graph()
for _ in range(N-1):
    s,d,w = [int(x) for x in input().split()]
    gp.add_edge(s-1,d-1,w)
    gp.add_edge(d-1,s-1,w)

Q,K = [int(x) for x in input().split()]
xy = [[int(x) for x in input().split()]for _ in range(Q)]
di = Dijkstra(gp,K-1)
for x,y in xy:
    print(di.shortest_distance(x-1)+di.shortest_distance(y-1))

Solution (Python):
N=int(input())
from collections import defaultdict
branch=defaultdict(dict)
for i in range(N-1):
    a,b,c=map(int,input().split())
    branch[a-1][b-1]=c
    branch[b-1][a-1]=c
Q,K=map(int,input().split())
dist=[float('inf') for i in range(N)]
K-=1
dist[K]=0
check={K}
while len(check)>0:
    now=check.pop()
    for nex,cost in branch[now].items():
        if dist[nex]>dist[now]+cost:
            dist[nex]=dist[now]+cost
            check|={nex}
for i in range(Q):
    x,y=map(int,input().split())
    print(dist[x-1]+dist[y-1])

Solution (Python):
import heapq

def dijkstra(graph, node, start):
    dist = [float("inf") for _ in range(node)]

    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        cost, cur_node = heapq.heappop(q)

        if dist[cur_node] < cost:
            continue

        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heapq.heappush(q, (dist[nex_node], nex_node))

    return dist


n = int(input())
adj = [[] for _ in range(n)]
for i in range(n - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    adj[a].append((c, b))
    adj[b].append((c, a))
q, k = map(int, input().split())
shortest = dijkstra(adj, n, k - 1)
for i in range(q):
    x, y = map(int, input().split())
    print(shortest[x - 1] + shortest[y - 1])

Solution (Python):
import heapq

def dijkstra(graph, node, start):
    dist = [float("inf") for _ in range(node)]

    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        cost, cur_node = heapq.heappop(q)

        if dist[cur_node] < cost:
            continue

        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heapq.heappush(q, (dist[nex_node], nex_node))

    return dist


n = int(input())
adj = [[] for _ in range(n)]
for i in range(n - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    adj[a].append((c, b))
    adj[b].append((c, a))
q, k = map(int, input().split())
shortest = dijkstra(adj, n, k - 1)
for i in range(q):
    x, y = map(int, input().split())
    print(shortest[x - 1] + shortest[y - 1])

Solution (Python):



def main():
    from collections import defaultdict
    from collections import deque
    import sys

    n = int(input())
    graph = [defaultdict(int) for _ in range(n)]
    visited = [False for _ in range(n)]
    dist = [float('inf') for _ in range(n)]
    lines = sys.stdin.readlines()

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

    q, k = map(int, lines[n - 1].split())
    k -= 1
    dist[k] = 0
    d = deque()
    d.append(k)

    while d:
        di = d.popleft()
        visited[di] = True

        for bi, ci in graph[di].items():
            if visited[bi]:
                continue

            dist[bi] = dist[di] + ci
            d.append(bi)

    ans = [0 for _ in range(q)]

    for j in range(q):
        xi, yi = map(int, lines[n + j].split())
        xi -= 1
        yi -= 1
        ans[j] = dist[xi] + dist[yi]

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


if __name__ == '__main__':
    main()