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
import sys
input = sys.stdin.readline

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


n = int(input())

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

for i in range(n-1):
    x,y,z = map(int,input().split())
    edge[x-1].append([z,y-1])
    edge[y-1].append([z,x-1]) 
q,k = map(int,input().split())
p = dijkstra_heap(k-1)
for i in range(q):
    a,b = map(int,input().split())
    print(p[a-1]+p[b-1])

Solution (Python):
from collections import deque
n = int(input())
Adjacent_list = [[] for x in range(n)]
check = [-1 for i in range(n)]
for i in range(n-1):
    a,b,c = map(int,input().split())
    Adjacent_list[a-1].append([b,c])
    Adjacent_list[b-1].append([a,c])
q,k = map(int,input().split())
deq = deque()
deq.appendleft([k,0])
check[k-1] = 0
while deq:
    num = deq.pop()
    for i in range(len(Adjacent_list[num[0]-1])):
        ls = Adjacent_list[num[0]-1][i]
        if check[ls[0]-1] != -1:
            continue
        check[ls[0]-1] = num[1] + ls[1]
        deq.appendleft([ls[0],num[1]+ls[1]])
for i in range(q):
    x,y = map(int,input().split())
    print(check[x-1]+check[y-1])

Solution (Python):
from collections import defaultdict, deque
N = int(input())
tree = defaultdict(list)
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    tree[a].append((b, c))
    tree[b].append((a, c))
Q, K = map(int, input().split())
XY = []
for _ in range(Q):
    XY.append(list(map(int, input().split())))


dists = [None] * (N + 1)
dists[K] = 0
q = deque([K])
while len(q) > 0:
    v = q.popleft()
    d = dists[v]
    for to, c in tree[v]:
        if dists[to] is None:
            dists[to] = d + c
            q.append(to)

for x, y in XY:
    ans = dists[x] + dists[y]
    print(ans)

Solution (Python):

N = int(input())
edge = [[] for _ in range(N)]
for _ in range(N-1):
    ai,bi,ci = map(int, input().split())
    edge[ai-1].append((bi-1, ci))
    edge[bi-1].append((ai-1, ci))
Q,K = map(int, input().split())
K = K-1
x,y = [],[]
for _ in range(Q):
    xi,yi = map(int, input().split())
    x.append(xi-1)
    y.append(yi-1)


dist = [float('inf') for _ in range(N)]
import heapq
def dijkstra(start:int):
    """priority_queue ver. O(|E|log|V|)
    """
    global dist 
    global edge 
    dist[start] = 0
    q = [(0,start)] 
    while q:
        d_cur,cur = heapq.heappop(q)
        if dist[cur] < d_cur:
            continue
        for nex,cost in edge[cur]:
            if dist[nex] > dist[cur]+cost:
                dist[nex] = dist[cur]+cost
                heapq.heappush(q, (dist[nex], nex))


dijkstra(K)
for xi,yi in zip(x,y):
    print(dist[xi] + dist[yi])

Solution (Python):

N = int(input())
edge = [[] for _ in range(N)]
for _ in range(N-1):
    ai,bi,ci = map(int, input().split())
    edge[ai-1].append((bi-1, ci))
    edge[bi-1].append((ai-1, ci))
Q,K = map(int, input().split())
K = K-1
x,y = [],[]
for _ in range(Q):
    xi,yi = map(int, input().split())
    x.append(xi-1)
    y.append(yi-1)


dist = [float('inf')]*N 
visited = [False]*N
q = [K]
dist[K] = 0
visited[K] = True
while q:
    cur = q.pop()
    visited[cur] = True
    for nex,cost in edge[cur]:
        if not visited[nex]:
            q.append(nex)
            dist[nex] = dist[cur]+cost

for xi,yi in zip(x,y):
    print(dist[xi] + dist[yi])

Solution (Python):
from collections import defaultdict
import sys

sys.setrecursionlimit(1000000)
d=defaultdict(list)

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

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


dists=[None]*(N+1)
isused=[False]*(N+1)
dists[K]=0
isused[K]=True

def dfs(n):
    for i,j in d[n]:
        if isused[i]:continue
        isused[i]=True
        dists[i]=dists[n]+j
        dfs(i)

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

Solution (Python):
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()
import sys
sys.setrecursionlimit(10 ** 6)
n=I()
nl=[[] for i in range(n)]
used=[False for i in range(n)]
for i in range(n-1):
    a,b,c=IL()
    nl[a-1].append([b-1,c])
    nl[b-1].append([a-1,c])
d=[None for i in range(n)]
def dfs(now,pre,dis):
    used[now]=True
    d[now]=dis
    for i in nl[now]:
        if i[0]!=pre and not used[i[0]]:
            dfs(i[0],now,dis+i[1])
    
    return
q,k=IL()
dfs(k-1,-1,0)
for i in range(q):
    x,y=IL()
    print(d[x-1]+d[y-1])

Solution (Python):
import heapq

G = [{}]

def setNode(n):
  global G
  G = [{} for i in range(n)]
def solve(s, n):
  global G
  fixed = [None]*n
  q = []
  heapq.heappush(q, (0,s))
  while q:
    w,x = heapq.heappop(q)
    if fixed[x] is not None: continue
    fixed[x] = w
    for y in G[x]:
        if fixed[y] is None:
            heapq.heappush(q, (w + G[x][y], y))
  return fixed


n = int(input())
setNode(n)
for i in range(n-1):
  s,t,w = map(int,input().split())
  G[s-1][t-1] = w
  G[t-1][s-1] = w
Q, K = map(int, input().split())
dist = solve(K-1,n)
for i in range(Q):
    x, y = map(int,input().split())
    print(dist[x-1]+dist[y-1])

Solution (Python):
N=int(input())
from collections import defaultdict
d=defaultdict(list)
f=defaultdict(int)
for _ in range(N-1):
    a,b,c=map(int,input().split())
    d[a].append([b,c,a])
    d[b].append([a,c,b])
Q,K=map(int,input().split())

dist=defaultdict(int)
dist[K]=0
f[K]=1
que=d[K]
prev=defaultdict(int)
prev[K]=0
while len(que)>0:
    tmp=[]
    tmpd=defaultdict(int)
    for t,c,e in que:
        if f[t]==0:
            dist[t]=c+dist[e]
            tmpd[t]=c+dist[e]
            f[t]=1
            tmp+=d[t]
    prev=tmpd
    que=tmp

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

Solution (Python):
N=int(input())
from collections import defaultdict
d=defaultdict(list)
f=defaultdict(int)
for _ in range(N-1):
    a,b,c=map(int,input().split())
    d[a].append([b,c,a])
    d[b].append([a,c,b])
Q,K=map(int,input().split())

dist=defaultdict(int)
dist[K]=0
f[K]=1
que=d[K]
prev=defaultdict(int)
prev[K]=0
while len(que)>0:
    tmp=[]
    tmpd=defaultdict(int)
    for t,c,e in que:
        if f[t]==0:
            dist[t]=c+dist[e]
            tmpd[t]=c+dist[e]
            f[t]=1
            tmp+=d[t]
    prev=tmpd
    que=tmp

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)
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())
dist = [-1] * N


def dfs(u, par, d):
    dist[u] = d
    for w, cost in G[u]:
        if w == par:
            continue
        dfs(w, u, d + cost)


dfs(K - 1, -1, 0)

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

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


class Solve():
    def __init__(self):
        self.N = int(input())
        self.route = [dict() for _ in range(self.N)]
        for _ in range(self.N - 1):
            a, b, c = map(int, input().split())
            self.route[a - 1][b - 1] = c
            self.route[b - 1][a - 1] = c
        self.Q, self.K = map(int, input().split())
        self.K -= 1
        self.query = []
        for _ in range(self.Q):
            x, y = map(int, input().split())
            self.query.append([x - 1, y - 1])
        self.depth = [0 for _ in range(self.N)]

    def DFS(self, v, p, d):
        self.depth[v] = d
        for dest, cost in self.route[v].items():
            if dest == p:
                continue
            self.DFS(dest, v, d + cost)

    def execute(self):
        self.DFS(self.K, -1, 0)
        for x, y in self.query:
            print(self.depth[x] + self.depth[y])


if __name__ == '__main__':
    Solve().execute()

Solution (Python):
import heapq
import itertools
n=int(input())
edges=[[] for _ in range(n)]
for _ in range(n-1):
    a,b,c=map(int, input().split())
    a,b=a-1,b-1
    edges[a].append((b,c))
    edges[b].append((a,c))

def dijkstra(x,route):
    d=[float('inf')]*n
    d[x]=0
    visited={x}
    hq=[(0,x)]
    while hq:
        u=heapq.heappop(hq)[1]
        visited.add(u)
        for node,cost in route[u]:
            if (node not in visited) and d[node]>d[u]+cost:
                d[node]=d[u]+cost
                heapq.heappush(hq,(d[node],node))
    return d
q,k=map(int,input().split())
k-=1
dist=dijkstra(k,edges)
for _ in range(q):
    start,goal=map(int,input().split())
    print(dist[start-1]+dist[goal-1])

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

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

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

depth=[0]*n
visited=[False for i in range(n)]
def dfs(start,kyori):
  depth[start] = kyori
  visited[start]=True
  
  for to in tree[start]:
    if not visited[to[0]]:
      dfs(to[0],kyori+to[1])
  return

dfs(k,0)

for i in range(q):
  start,goal =  map(int, input().split())
  print(depth[start-1]+depth[goal-1])

Solution (Python):


import sys
import heapq
from collections import defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def dijkstra(start: int, size: int, G: dict) -> list:
    costs = [INF] * size
    costs[start] = 0
    hp = []
    heapq.heappush(hp, (0, start))
    while hp:
        hc, hv = heapq.heappop(hp)
        for to, move_cost in G[hv]:
            if hc + move_cost >= costs[to]:
                continue
            costs[to] = hc + move_cost
            heapq.heappush(hp, (costs[to], to))

    return costs


n = II()

G = defaultdict(list)
for _ in range(n - 1):
    a, b, c = LI()
    a -= 1
    b -= 1
    G[a].append((b, c))
    G[b].append((a, c))

q, k = LI()
k -= 1
C = dijkstra(k, n, G)

for _ in range(q):
    x, y = LI_()
    print(C[x] + C[y])

Solution (Python):


import sys
import heapq
from collections import defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def dijkstra(start: int, size: int, graph: dict) -> list:
    costs = [INF] * size
    costs[start] = 0
    visited = set()
    hp = []
    heapq.heappush(hp, (0, start))
    while hp:
        hc, hv = heapq.heappop(hp)
        if hv in visited:
            continue
        for to, move_cost in graph[hv]:
            if hc + move_cost >= costs[to]:
                continue
            costs[to] = hc + move_cost
            heapq.heappush(hp, (costs[to], to))
        visited.add(hv)

    return costs


n = II()

G = defaultdict(list)
for _ in range(n - 1):
    a, b, c = LI()
    a -= 1
    b -= 1
    G[a].append((b, c))
    G[b].append((a, c))

q, k = LI()
k -= 1
C = dijkstra(k, n, G)

for _ in range(q):
    x, y = LI_()
    print(C[x] + C[y])

Solution (Python):

from collections import deque

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

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

depth = [0 for _ in range(N)]

def bfs(v, p = -1, d = 0):
    q = deque()
    q.append([v, p, d])
    while len(q)>0:
        cur = q.popleft()
        depth[cur[0]] = cur[2]
        for i, j in tree[cur[0]]:
            if i == cur[1]:
                continue
            q.append([i, cur[0], cur[2] + j])

bfs(K)

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

Solution (Python):
N = int(input())
tree = [[] for _ in range(N)]

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

depth = [0 for _ in range(N)]

def dfs(v, p = -1, d = 0):
    St = []
    St.append([v, p, d])
    
    while St:
        cur = St.pop()
        depth[cur[0]] = cur[2]
        for i, j in tree[cur[0]]:
            if i == cur[1]:
                continue
            St.append([i, cur[0], cur[2] + j])

dfs(K)

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

Solution (Python):
from heapq import heappush, heappop

INF = 10 ** 20
n = int(input())
edges = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    edges[a].append((b, c))
    edges[b].append((a, c))

q, k = map(int, input().split())
k -= 1
dist = [INF] * n
dist[k] = 0
que = []
heappush(que, (0, k))
while que:
    score, node = heappop(que)
    for to, cost in edges[node]:
        newScore = score + cost
        if dist[to] > newScore:
            dist[to] = newScore
            heappush(que, (newScore, to))

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

Solution (Python):


N = int(input())
T = {}
D = [None] * (N+1)
F = [True] * (N+1)

for n in range(N+1):
    T[n] = []

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

D[K] = 0
F[K] = False

L = [K]

while len(L) > 0:
    L_tmp = []
    for k in L:
        for t in T[k]:
            b, c = t
            if F[b] == True:
                D[b] = D[k] + c
                F[b] = False
                L_tmp.append(b)
    L = L_tmp

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
N = int(input())
G = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    G[a].append((b, c))
    G[b].append((a, c))
Q, K = map(int, input().split())


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


def dfs(v, c):
    d[v] = c
    for nv, cost in G[v]:
        if d[nv] == -1:
            dfs(nv, cost+c)

dfs(K, 0)

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

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

tree = [[] for _ in range(n+10)]
visited = [-1 for _ in range(n+10)]

for i in range(n-1):
    a, b, c = [int(j) for j in input().split()]
    tree[a - 1].append([b - 1, c])
    tree[b - 1].append([a - 1, c])
q, k = [int(i) for i in input().split()]

stack = [[k-1, 0]]
while True:
    size = len(stack)
    if size == 0:
        break
    now, cost = stack.pop()
    visited[now] = cost
    for i in range(len(tree[now])):
        if visited[tree[now][i][0]] == -1:
            stack.append([tree[now][i][0],
                          cost+tree[now][i][1]])

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
N = (int)(input())
edges = []
for _ in range(N-1):
    edges.append((list)(map(int, input().split())))

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

'''
 N:num of nodes
 Q: num of query
 K: node must passed in query

'''
dist = [[] for _ in range(N+1)]
for e in edges:
    dist[e[0]].append([e[1], e[2]])
    dist[e[1]].append([e[0], e[2]])

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


def dfs(v, cost):
    if dist_from_k[v] != -1:
        return

    dist_from_k[v] = cost
    for e in dist[v]:
        dfs(e[0], cost+e[1])


dfs(K, 0)

for q in querys:
    print(dist_from_k[q[0]] + dist_from_k[q[1]])

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
N = (int)(input())
edges = []
for _ in range(N-1):
    edges.append((list)(map(int, input().split())))

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

'''
 N:num of nodes
 Q: num of query
 K: node must passed in query

'''
dist = [-1]*(N+1)
for e in edges:
    if dist[e[0]] == -1:
        dist[e[0]] = [[e[1], e[2]]]
    else:
        dist[e[0]].append([e[1], e[2]])

    if dist[e[1]] == -1:
        dist[e[1]] = [[e[0], e[2]]]
    else:
        dist[e[1]].append([e[0], e[2]])

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


def dfs(v, cost):
    if dist_from_k[v] != -1:
        return

    dist_from_k[v] = cost
    for e in dist[v]:
        dfs(e[0], cost+e[1])


dfs(K, 0)

for q in querys:
    print(dist_from_k[q[0]] + dist_from_k[q[1]])

Solution (Python):
import heapq, collections

n = int(input())
distance = collections.defaultdict(dict)
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    distance[a - 1][b - 1] = c
    distance[b - 1][a - 1] = c
q, k = map(int, input().split())
k -= 1
queries = []
for _ in range(q):
    x, y = map(int, input().split())
    queries.append((x - 1, y - 1))

d = [float('inf')] * (n + 1)
d[k] = 0
queue = [(0, k)]
while queue:
    cost, current = heapq.heappop(queue)
    for nxt in distance[current]:
        if cost + distance[current][nxt] < d[nxt]:
            d[nxt] = cost + distance[current][nxt]
            heapq.heappush(queue, (d[nxt], nxt))

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

Solution (Python):
import heapq, collections

n = int(input())
distance = collections.defaultdict(dict)
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    distance[a - 1][b - 1] = c
    distance[b - 1][a - 1] = c
q, k = map(int, input().split())
k -= 1
queries = []
for _ in range(q):
    x, y = map(int, input().split())
    queries.append((x - 1, y - 1))

d = [float('inf')] * (n + 1)
d[k] = 0
queue = [(0, k)]
while queue:
    cost, current = heapq.heappop(queue)
    for nxt in distance[current]:
        if cost + distance[current][nxt] < d[nxt]:
            d[nxt] = cost + distance[current][nxt]
            heapq.heappush(queue, (d[nxt], nxt))

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

Solution (Python):


import sys
def input(): return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)

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

memo = [0] * (N+1)
def dfs(cur, prev, dist):
    memo[cur] = dist
    for nxt, cost in nodes[cur]:
        if nxt == prev:
            continue
        dfs(nxt, cur, dist+cost)

Q, K = map(int, input().split())
dfs(K, -1, 0)

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

Solution (Python):


import sys
def input(): return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)

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

memo = [0] * (N+1)
def dfs(cur, prev, dist):
    memo[cur] = dist
    for nxt, cost in nodes[cur]:
        if nxt == prev:
            continue
        dfs(nxt, cur, dist+cost)

Q, K = map(int, input().split())
dfs(K, -1, 0)

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

Solution (Python):


import sys
def input(): return sys.stdin.readline().strip()
    
from heapq import heappop, heappush


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

def dijkstra(nodes, start):
    
    memo = [float('inf')] * (len(nodes))
    
    que = [(0, start)]
    memo[start] = 0
    
    while len(que) != 0:
        
        dist, cur = heappop(que)
        
        for nxt, cost in nodes[cur]:
            
            if memo[cur] + cost < memo[nxt]:
                memo[nxt] = memo[cur] + cost
                
                heappush(que, (memo[nxt], nxt))
    
    return memo

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

memo = dijkstra(nodes, K)

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

Solution (Python):


import sys
def input(): return sys.stdin.readline().strip()
    
from heapq import heappop, heappush


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

def dijkstra(nodes, start):
    
    memo = [float('inf')] * (len(nodes))
    
    que = [(0, start)]
    memo[start] = 0
    
    while len(que) != 0:
        
        dist, cur = heappop(que)
        
        for nxt, cost in nodes[cur]:
            
            if memo[cur] + cost < memo[nxt]:
                memo[nxt] = memo[cur] + cost
                
                heappush(que, (memo[nxt], nxt))
    
    return memo

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

memo = dijkstra(nodes, K)

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

Solution (Python):


"""
参考：https://img.atcoder.jp/abc070/editorial.pdf
・公式解が再帰だったのでやってみる
"""

import sys


sys.setrecursionlimit(10 ** 9)

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

memo = [0] * (N+1)
def dfs(cur, prev, dist):
    memo[cur] = dist
    for nxt, cost in nodes[cur]:
        if nxt == prev:
            continue
        dfs(nxt, cur, dist+cost)

Q, K = map(int, input().split())
dfs(K, -1, 0)

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

Solution (Python):


"""
・ダイクストラ(優先度付きキュー)
"""

from heapq import heappop, heappush


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

def dijkstra(nodes, start):
    
    memo = [float('inf')] * (len(nodes))
    
    que = [(0, start)]
    memo[start] = 0
    
    while len(que) != 0:
        
        dist, cur = heappop(que)
        
        for nxt, cost in nodes[cur]:
            
            if memo[cur] + cost < memo[nxt]:
                memo[nxt] = memo[cur] + cost
                
                heappush(que, (memo[nxt], nxt))
    
    return memo

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

memo = dijkstra(nodes, K)

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

Solution (Python):


"""
・ダイクストラ(優先度付きキュー)
"""

from heapq import heappop, heappush


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

def dijkstra(nodes, start):
    
    memo = [float('inf')] * (len(nodes))
    
    que = [(0, start)]
    memo[start] = 0
    
    while len(que) != 0:
        
        dist, cur = heappop(que)
        
        for i in range(len(nodes[cur])):
            nxt, cost = nodes[cur][i]
            
            if memo[cur] + cost < memo[nxt]:
                memo[nxt] = memo[cur] + cost
                
                heappush(que, (memo[nxt], nxt))
    
    return memo

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

memo = dijkstra(nodes, K)

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

Solution (Python):


"""
・ダイクストラ(優先度付きキュー)
"""

from heapq import heappop, heappush


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

def dijkstra(nodes, start):
    
    memo = [float('inf')] * (len(nodes))
    
    visited = [False] * (len(nodes))
    
    que = [(0, start)]
    memo[start] = 0
    
    while len(que) != 0:
        
        dist, cur = heappop(que)
        
        visited[cur] = True
        
        for i in range(len(nodes[cur])):
            nxt, cost = nodes[cur][i]
            
            if not visited[nxt] and memo[cur] + cost < memo[nxt]:
                memo[nxt] = memo[cur] + cost
                
                heappush(que, (memo[nxt], nxt))
    
    return memo

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

memo = dijkstra(nodes, K)

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

Solution (Python):


"""
・ダイクストラ(優先度付きキュー)
"""

from heapq import heappop, heappush


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

def dijkstra(nodes, start):
    
    memo = [float('inf')] * (len(nodes))
    
    visited = [False] * (len(nodes))
    
    que = [(0, start)]
    memo[start] = 0
    
    while len(que) != 0:
        
        dist, cur = heappop(que)
        
        visited[cur] = True
        
        for i in range(len(nodes[cur])):
            nxt, cost = nodes[cur][i]
            
            if not visited[nxt]:
                memo[nxt] = min(memo[cur] + cost, memo[nxt])
                
                heappush(que, (memo[nxt], nxt))
    
    return memo

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

memo = dijkstra(nodes, K)

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

Solution (Python):


"""
・ダイクストラ(優先度付きキュー)
"""

from heapq import heappop, heappush
from collections import deque


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

def dijkstra(nodes, start):
    
    memo = [float('inf')] * (len(nodes))
    
    visited = [False] * (len(nodes))
    
    que = [(0, start)]
    memo[start] = 0
    
    while len(que) != 0:
        
        dist, cur = heappop(que)
        
        visited[cur] = True
        
        while len(nodes[cur]) != 0:
            nxt, cost = nodes[cur].popleft()
            
            if not visited[nxt]:
                memo[nxt] = min(memo[cur] + cost, memo[nxt])
                
                heappush(que, (memo[nxt], nxt))
    
    return memo

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

memo = dijkstra(nodes, K)

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

Solution (Python):


"""
・ダイクストラ(優先度付きキュー)
"""

from heapq import heappop, heappush


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

def dijkstra(nodes, start):
    
    memo = [float('inf')] * (len(nodes))
    
    visited = [False] * (len(nodes))
    
    que = [(0, start)]
    memo[start] = 0
    
    while len(que) != 0:
        
        dist, cur = heappop(que)
        
        visited[cur] = True
        
        for i in range(len(nodes[cur])):
            nxt, cost = nodes[cur][i]
            
            if not visited[nxt]:
                memo[nxt] = min(memo[cur] + cost, memo[nxt])
                
                heappush(que, (memo[nxt], nxt))
    
    return memo

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

memo = dijkstra(nodes, K)

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)
N = int(input())
G = [[] for i 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())
K -= 1
dist = [-1] * N
dist[K] = 0


def dfs(n):
    for v, c in G[n]:
        if dist[v] < 0:
            dist[v] = dist[n] + c
            dfs(v)


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

Solution (Python):
V = int(input())
E = V - 1
G = {}
for i in range(V):
    G[i] = {}

for _ in range(E):
    s, t, c = [int(_) for _ in input().split()]
    s -= 1  
    t -= 1  
    G[s][t] = c
    G[t][s] = c
Q, K = [int(_) for _ in input().split()]
K -= 1  
XY = [[int(_) for _ in input().split()] for _ in range(Q)]

INF = float('inf')
D = [INF] * V
D[K] = 0
cand = []
for j in G[K].keys():
    cand += [(K, j)]
while True:
    if cand:
        x, y = cand.pop()
        if D[y] == INF:
            D[y] = D[x] + G[x][y]
            for z in G[y].keys():
                cand += [(y, z)]
    else:
        break
for x, y in XY:
    x -= 1
    y -= 1
    print(D[x] + D[y])

Solution (Python):
import heapq

V = int(input())
E = V - 1
G = {}
for i in range(V):
    G[i] = {}

for _ in range(E):
    s, t, c = [int(_) for _ in input().split()]
    s -= 1  
    t -= 1  
    G[s][t] = c
    G[t][s] = c
Q, K = [int(_) for _ in input().split()]
K -= 1  
XY = [[int(_) for _ in input().split()] for _ in range(Q)]

INF = float('inf')

que = []
i = K
d = 0
D = [INF] * V
D[i] = 0
used = [False] * V
used[i] = True

while True:
    for j in G[i].keys():
        heapq.heappush(que, (d + G[i][j], j))
    v = -1
    while que:
        d, j = heapq.heappop(que)
        if not used[j]:
            v = j
            break
    if v == -1:
        break
    else:
        used[v] = True
        D[v] = d
        i = v
for x, y in XY:
    x -= 1  
    y -= 1  
    print(D[x] + D[y])