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):
f_ = lambda: [int(x)-1 for x in input().split()]

n = int(input())
from collections import defaultdict
P = defaultdict(list)

for _ in range(n-1):
    a,b,c, = f_(); c += 1
    P[a].append((b,c))
    P[b].append((a,c))

q,k = f_(); q += 1
from collections import deque
que = deque([k])
dist = [None for i in range(n)]; dist[k] = 0

while que:
    p = que.popleft()
    for a,c in P[p]:
        if dist[a] is None:
            dist[a] = dist[p] + c
            que.append(a)

ans = []
for _ in range(q):
    x, y = f_()
    ans.append(dist[x]+dist[y])
print(*ans, sep='\n')

Solution (Python):

import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())


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, cur_node = heappop(heap)
        
        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
                heappush(heap, (dist[nex_node], nex_node))
    
    return dist


n = ni()


graph = [[] for _ in range(n)]
for _ in range(n-1):
    a,b,c = li()
    a -= 1
    b -= 1
    graph[a].append((c,b))
    graph[b].append((c,a))
    
q,k = li()
query = []
for _ in range(q):
    x,y = li()
    x -= 1
    y -= 1
    query.append((x,y))


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


for x,y in query:
    print(dist_k[x] + dist_k[y])

Solution (Python):
from collections import deque

n = int(input())
path = {}
for i in range(n-1):
    a, b, c = list(map(int, input().split()))
    if not a in path.keys():
        path[a] = [(b, c)]
    else:
        path[a].append((b, c))
        
    if not b in path.keys():
        path[b] = [(a, c)]
    else:
        path[b].append((a, c))
q, k = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(q)]

dist = [None]*(n+1)
dist[k] = 0
que = deque([(k, 0)])
while len(que) > 0:
    node, d = que.popleft()
    dist[node] = d
    for node_next, d_next in path[node]:
        if dist[node_next] is None:
            que.append((node_next, d+d_next))


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

Solution (Python):
from collections import deque
n=int(input())
l=[[] for _ in [0]*n]
for _ in [0]*(n-1):
  a,b,c=map(int,input().split())
  l[a-1].extend([(b-1,c)])
  l[b-1].extend([(a-1,c)])

q,k=map(int,input().split())
dst=[0 for _ in [0]*n]
que=deque([])
v,p,d=k-1,-1,0
que.append((v,p,d))
while que:
  v,p,d=que.pop()
  dst[v]=d
  for i,j in l[v]:
    if i==p:continue
    que.append((i,v,d+j))

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

Solution (Python):
def dfs():
  stack = [K]
  while len(stack) > 0:
    i = stack.pop()
    for k,v in E[i].items():
      if visited[k]:
        continue
      visited[k] = True
      distd[k] = distd[i] + v
      stack.append(k)


N = int(input())
E = {}

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

  if b in E:
    E[b].setdefault(a,c)
  else:
    E[b] = {a:c}



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


visited = [False] * (N+1)
distd = [1e15] * (N+1)

visited[K] = True
distd[K] = 0

dfs()

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

Solution (Python):
def dfs():
  stack = [K]
  while len(stack) > 0:
    i = stack.pop()
    for k,v in E[i].items():
      if visited[k]:
        continue
      visited[k] = True
      distd[k] = distd[i] + v
      stack.append(k)


N = int(input())
E = {}

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

  if b in E:
    E[b].setdefault(a,c)
  else:
    E[b] = {a:c}



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


visited = [False] * (N+1)
distd = [1e15] * (N+1)

visited[K] = True
distd[K] = 0

dfs()

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

Solution (Python):
from collections import deque

def bfs(start):
    queue = deque([start])
    visited = []

    while queue:
        label = queue.pop()

        
        visited.append(label)

        for v in d[label]:
            if dist[v[0]] == float("inf"):
                dist[v[0]] = dist[label] + v[1]
                queue.appendleft(v[0])

    return

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

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

bfs(k - 1)

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

Solution (Python):
from collections import deque

def bfs(start):
    queue = deque([start])
    visited = []

    while queue:
        label = queue.pop()

        
        visited.append(label)

        for v in d[label]:
            if dist[v[0]] == float("inf"):
                dist[v[0]] = dist[label] + v[1]
                queue.appendleft(v[0])

    return

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

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

bfs(k - 1)

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

Solution (Python):
import queue
N=int(input())
G=[dict() for i in range(N)]
for i in range(N-1):
    a,b,c=map(int,input().split())
    G[a-1][b-1]=c
    G[b-1][a-1]=c
Q,K=map(int,input().split());K-=1
x=[0 for i in range(Q)]
y=[0 for i in range(Q)]
for i in range(Q):
    x[i],y[i]=map(int,input().split())
    x[i]-=1
    y[i]-=1
q=[]
q.append(K)
dist=[-1 for i in range(N)]
dist[K]=0
while(len(q)>0):
    r=q[-1]
    q.pop()
    for p in G[r]:
        if dist[p]!=-1:
            continue
        dist[p]=dist[r]+G[p][r]
        q.append(p)
for i in range(Q):
    print(dist[x[i]]+dist[y[i]])

Solution (Python):
import queue
N=int(input())
G=[dict() for i in range(N)]
for i in range(N-1):
    a,b,c=map(int,input().split())
    G[a-1][b-1]=c
    G[b-1][a-1]=c
Q,K=map(int,input().split());K-=1
x=[0 for i in range(Q)]
y=[0 for i in range(Q)]
for i in range(Q):
    x[i],y[i]=map(int,input().split())
    x[i]-=1
    y[i]-=1
q=queue.Queue()
q.put(K)
dist=[-1 for i in range(N)]
dist[K]=0
while(not(q.empty())):
    r=q.get()
    for p in G[r]:
        if dist[p]!=-1:
            continue
        dist[p]=dist[r]+G[p][r]
        q.put(p)
for i in range(Q):
    print(dist[x[i]]+dist[y[i]])

Solution (Python):
n = int(input())
p = []
for i in range(n-1):
    p.append(list(map(int, input().split())))
q,k = map(int,input().split())
kue = []
for i in range(q):
    a,b=input().split()
    kue.append((int(a), int(b)))
import heapq

def shortest_path(edge,num_v,start):
    inf = float("inf")
    cost = [[] for i in range(n+1)]
    for path in edge:
      cost[path[0]].append((path[1],path[2]))
      cost[path[1]].append((path[0],path[2]))
    d = [inf for j in range(num_v)]
    q = []
    heapq.heappush(q, (0, start))
    d[start] = 0
    while len(q) != 0:
      prov_cost, src = heapq.heappop(q)
      if d[src] < prov_cost:
                continue
      for dest,weight in cost[src]:
        if weight != float('inf') and d[dest] > d[src] + weight:
          d[dest] = d[src] + weight
          heapq.heappush(q, (d[dest], dest))
    return d
kno = shortest_path(p,n+1,k)
for i in kue:
  print(kno[i[0]] + kno[i[1]])

Solution (Python):
import sys
import math
import collections
import itertools
import array
import inspect


sys.setrecursionlimit(1000000)



def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))



def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]




dp = None
D = None
D_dfs_d = None


def dfs_d(v, pre, dist):
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def main():
    global D
    global D_dfs_d

    N = int(input())
    D_dfs_d = [-1] * (N + 1)
    D = [[] for _ in range(N + 1)]

    for i in range(N - 1):
        a, b, c = li_input()
        D[a].append((b, c))
        D[b].append((a, c))

    Q, K = li_input()

    
    dfs_d(K, -1, 0)

    for i in range(Q):
        x, y = li_input()
        print(D_dfs_d[x] + D_dfs_d[y])


main()

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

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

D = [0] * N
def dfs(pos, pre, dis):
    D[pos] = dis
    for (to, cost) in G[pos]:
        if to == pre:
            continue
        dfs(to, pos, dis + cost)


dfs(K - 1, -1, 0)

while Q:
    Q = Q - 1
    x, y = list(map(lambda a:int(a) - 1, input().split()))
    ans = D[x] + D[y]
    print (ans)

Solution (Python):
import sys

sys.setrecursionlimit(10**5+100)
n = int(input())

edges = [[] for _ in xrange(n)]
distance = [-1 for _ in xrange(n)]

for _ in xrange(n-1):
	f,t,c = map(int,raw_input().split())

	f -= 1
	t -= 1

	edges[f].append((t,c))
	edges[t].append((f,c))

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

def dfs(v,c):
	if distance[v] == -1:
		distance[v] = c
		for to,cost in edges[v]:
			dfs(to,c+cost)

dfs(k,0)

for _ in xrange(q):
	x,y = map(int,raw_input().split())
	x -= 1
	y -= 1
	print distance[x] + distance[y]

Solution (Python):
from collections import deque
N = int( input())
D = dict()
Path = [ [] for _ in range(N)]
for _ in range(N-1):
    a, b, c = map( int, input().split())
    a, b = a-1, b-1
    D[1000000*a+b] = c
    D[1000000*b+a] = c
    Path[a].append(b)
    Path[b].append(a)
Q, K = map( int, input().split())
foot = [ 0 for _ in range(N)]
foot[K-1] = 1
length = [ 0 for _ in range(N)]
A = deque([])
for d in Path[K-1]:
    foot[d] = 1
    A.append(d)
    length[d] = D[1000000*d + K-1]
while len(A) != 0:
    d = A.pop()
    foot[d] = 1
    for g in Path[d]:
        if foot[g] == 0:
            length[g] = length[d] + D[1000000*d + g]
            A.append(g)
for _ in range(Q):
    x, y = map( int, input().split())
    print(length[x-1]+length[y-1])

Solution (Python):



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

Q, K = [int(t) for t in input().split()]

def dfs(s):
    '''Kからの距離を計算'''
    global dist
    work = [s]
    while len(work) > 0:
        s = work.pop()
        for t, c in edge[s]:
            if dist[t] == None:
                dist[t] = dist[s] + c
                work.append(t)

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

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

Solution (Python):
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N = int(input())

lines = defaultdict(set)
for i in range(N-1):
	a,b,c = inpl()
	a -= 1
	b -= 1
	lines[a].add((b,c))
	lines[b].add((a,c))

Q,s = inpl()
s -= 1
ss = [-1]*N
ss[s] = 0

def check(a,w):
	global ss
	for b,c in lines[a]:
		if ss[b] == -1:
			ss[b] = w + c
			check(b,w+c)

check(s,0)

for i in range(Q):
	x,y = inpl()
	print(ss[x-1]+ss[y-1])

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, ABC, Q, K, XY):
    kd = [0] * (N+1)
    kd[K] = 0
    g = defaultdict(dict)
    for a, b, c in ABC:
        g[a][b] = c
        g[b][a] = c

    q = [K]
    while q:
        n = q.pop()
        for m, c in g[n].items():
            if m != K and kd[m] == 0:
                kd[m] = kd[n] + c
                q.append(m)

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


def main():
    N = read_int()
    ABC = [read_int_n() for _ in range(N-1)]
    Q, K = read_int_n()
    XY = [read_int_n() for _ in range(Q)]

    slv(N, ABC, Q, K, XY)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
 
graph = [[] for x in range(n)]
 
for i in range(n - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append((b, c))
    graph[b].append((a, c))
 
q, k = map(int, input().split())
k -= 1
 
costs = [0 for x in range(n)]
que = []
que.append((k, 0))
while que:
    now, cost = que.pop()
    costs[now] = cost
    for node in graph[now]:
        if graph[node[0]] is not None:
            que.append((node[0], cost + node[1]))
    graph[now] = None
 
result = ""
for i in range(q):
    x, y = map(int, input().split())
    result += str(costs[x - 1] + costs[y - 1])
    result += "\n"
print(result)

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

N = int(input())


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):
    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):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


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

Q, K = map(int, input().split())
d = Dijkstra(g, K - 1)
for _ in range(Q):
    x, y = map(int, input().split())
    ans = d.shortest_distance(x - 1) + d.shortest_distance(y - 1)
    print(ans)

Solution (Python):
from collections import defaultdict
import heapq

N = int(input())
INF = float('inf')
edges = [list(map(int, input().split())) for _ in range(N-1)]
nodes = defaultdict(list)

for e in edges:
    nodes[e[0] - 1].append((e[2], e[1] - 1))
    nodes[e[1] - 1].append((e[2], e[0] - 1))


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

def dijkstra(x):
    que = []
    heapq.heapify(que)
    dist = [INF for _ in range(N)]
    dist[x] = 0
    heapq.heappush(que, (0, x))

    while que:
        p = heapq.heappop(que)
        v = p[1]
        if dist[v] < p[0]:
            continue
        for e in nodes[v]:
            if dist[e[1]] > dist[v] + e[0]:
                dist[e[1]] = dist[v] + e[0]
                heapq.heappush(que, (dist[e[1]], e[1]))

    return dist

distk = dijkstra(K - 1)

for q in queries:
    x, y = q[0] - 1, q[1] - 1
    print(distk[x] + distk[y])

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

graph = [[] for x in range(n)]

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

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

costs = [0 for x in range(n)]
que = []
que.append((k, 0))
while que:
    now, cost = que.pop()
    costs[now] = cost
    for node in graph[now]:
        if graph[node[0]] is not None:
            que.append((node[0], cost + node[1]))
    graph[now] = None

result = ""
for i in range(q):
    x, y = map(int, input().split())
    result += str(costs[x - 1] + costs[y - 1])
    result += "\n"
print(result)

Solution (Python):
N = int(raw_input())
G = {}
for i in range(N):
  G[i] = {}
for i in range(N-1):
  a, b, c = map(int, raw_input().split())
  G[a-1][b-1] = G[b-1][a-1] = c
Q, K = map(int, raw_input().split())
K -= 1

d = [0]*N
p = [K]
while len(p)>0:
  v = p.pop()
  for n in G[v].keys():
    if n!=K and d[n]==0:
      d[n] = d[v]+G[v][n]
      p.append(n)

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

Solution (Python):
from collections import deque

N = int(input())

G, W = [[] for i in range(N)], [[] for l in range(N)]
check, dist = [0 for j in range(N)], [-1 for k in range(N)]


def bfs(s):
    q = deque()
    check[s], dist[s] = 1, 0
    q.append(s)

    while len(q) != 0:
        u = q.popleft()
        for v in range(len(G[u])):
            if check[G[u][v]] == 0:
                check[G[u][v]], dist[G[u][v]] = 1, dist[u] + W[u][v]
                q.append(G[u][v])

        check[u] = 2


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

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

    bfs(k-1)

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


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
T = [[] for i in range(N)]
for i in range(N - 1):
  [a, b, c] = [int(x) for x in input().split()]
  T[a-1].append((b-1, c))
  T[b-1].append((a-1, c))
[Q, K] = [int(x) for x in input().split()]
L = [[0, 0] for i in range(N)]
L[K-1] = [0, 1]
q = [K-1]
while(q):
  s = q.pop()
  for t in T[s]:
    if not L[t[0]][1]:
      L[t[0]][0] = L[s][0] + t[1]
      L[t[0]][1] = 1
      q.append(t[0])
for q in range(Q):
  [x, y] = [int(x) for x in input().split()]
  print(L[x-1][0] + L[y-1][0])

Solution (Python):
import heapq


def dijkstra(K):
    c_l = [float('inf')] * N
    c_l[K] = 0
    hq = [(K, 0)]
    while hq:
        u = heapq.heappop(hq)[0]
        for nv, c in adj_list[u]:
            if c_l[nv] > c_l[u] + c:
                c_l[nv] = c_l[u] + c
                heapq.heappush(hq, (nv, c_l[nv]))
    return c_l


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

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

Q, K = map(int, input().split())
c_l = dijkstra(K - 1)

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

Solution (Python):
import heapq


def dijkstra(K):
    c_l = [float('inf')] * N
    c_l[K] = 0
    hq = [(0, K)]
    while hq:
        u = heapq.heappop(hq)[1]
        for nv, c in adj_list[u]:
            if c_l[nv] > c_l[u] + c:
                c_l[nv] = c_l[u] + c
                heapq.heappush(hq, (c_l[u] + c, nv))
    return c_l


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

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

Q, K = map(int, input().split())
c_l = dijkstra(K - 1)

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

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

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

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

cost = [-1]*N
def calc(i,c):
    
    cost[i] = c
    
    for ni,nc in X[i]:
        
        if cost[ni] == -1:
            calc(ni,c+nc)

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

calc(K-1,0)

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

Solution (Python):
from collections import deque

N = int(input())
g = [[] for _ in range(0,N+1)]
for i in range(0,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())
xy = []
for i in range(0,Q):
    x,y = map(int,input().split())
    xy.append((x,y))

d = [-1 for _ in range(0,N+1)]
d[K] = 0
queue = deque([[K,g[K]]])
while queue:
    start,edge = queue.popleft()
    for to,cost in edge:
        if d[to] != -1:
            continue
        d[to] = d[start] + cost
        queue.append((to,g[to]))

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

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

from collections import defaultdict
from heapq import *

V = list(range(1, N + 1))
E = defaultdict(lambda:{})
for a, b, c in abc:
    E[a][b] = c
    E[b][a] = c

def Dijkstra(s, V, E):
    
    d = defaultdict(lambda:10**20)
    prev = defaultdict(lambda:None)
    d[s] = 0
    Q = []
    for v in V:
        heappush(Q, (d[v], v))
    while Q:
        x, u = heappop(Q)
        for v, y in E[u].items():
            alt = d[u] + y
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heappush(Q, (alt, v))
    return d, prev

d, prev = Dijkstra(K, V, E)

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

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

N = int(input())
ABC = [list(map(int, input().split())) for i in range(N-1)]
Q, K = map(int, input().split())
D = [0] * (N+1)
L = [[] for i in range(N+1)]
for a, b, c in ABC:
    L[a].append([b, c])
    L[b].append([a, c])


def dfs(n, np):
    for nc in L[n]:
        if nc[0] == np:
            continue
        else:
            D[nc[0]] = D[n] + nc[1]
            dfs(nc[0], n)


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

Solution (Python):
from heapq import heappush,heappop
N = int(input())
table=[[]for i in range(N)]
for i in range(N-1):
    a,b,c=map(int,input().split())
    table[a-1].append([b-1,c])
    table[b-1].append([a-1,c])
Q,K=map(int,input().split())
Que=[[int(i) for i in input().split()] for i in range(Q)]
inf=10**17
dis=[inf]*N
dis[K-1]=0
kei=[]
heappush(kei,[0,K-1])
while kei:
    q,x=heappop(kei)
    if dis[x]<q:
        continue
    for i,d in table[x]:
        if dis[x]+d<dis[i]:
            dis[i]=dis[x]+d
            heappush(kei,[dis[i],i])
ans =[]
for x,y in Que:
    ans.append(dis[x-1]+dis[y-1])
print('\n'.join(map(str,ans)))

Solution (Python):
def getDis(k, abc, n):
    r = [[] for i in range(n)]
    for a, b, c in abc:
        r[a-1] += [(b-1, c)]
        r[b-1] += [(a-1, c)]
    dis = [-1] * n
    stack = [k]
    dis[k] = 0
    while stack:
        label = stack.pop(-1)
        for i, c in r[label]:
            if dis[i] == -1:
                dis[i] = dis[label] + c
                stack.append(i)
    return dis


N = int(input())
abc = [[int(i) for i in input().split()] for i in range(N-1)]
Q, K = map(int, input().split())
xy = [[int(i) for i in input().split()] for i in range(Q)]
d = getDis(K-1, abc, N)
for i in range(Q):
    print(d[xy[i][0] - 1] + d[xy[i][1] - 1])

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


N = int(input())
edges = []
for i in range(N - 1):
    edges += [list(map(int, input().split()))]
Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for i in range(Q)]
distance = BFS(K-1, edges, N)
for i in range(Q):
    print(distance[xy[i][0] - 1] + distance[xy[i][1] - 1])

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

n = int(input())
tree = [[] for _ in range(n+1)]

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())
d = [0] * (n+1)

def dfs(x, c, p):
    global tree
    d[x] = c
    for l, c_ in tree[x]:
        if l == p:
            continue
        else:
            dfs(l, c_+c, x)

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

Solution (Python):
def main():
    N = int(input())
    treedic = {}
    for i in range(1, N+1):
        treedic[i] = {}
    for i in range(N-1):
        a, b, c = map(int, input().split())
        treedic[a][b] = c
        treedic[b][a] = c

    Q, K = map(int, input().split())
    checked = set([K])
    length = [0]*(N+1)
    check = set([K])

    while len(checked) < N:
        nextcheck = set()
        for i in check:
            for j in treedic[i].keys():
                if j not in checked:
                    length[j] = length[i] + treedic[i][j]
                    checked.add(j)
                    nextcheck.add(j)
        check = nextcheck

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
 
def ans():
    def dfs(v, p, d):
        depth[v] = d
        for e, cost in tree[v]:
            if e == p:
                continue
            dfs(e, v, d + cost)
 
    n = int(input())
    tree = [[] for _ in range(n + 1)]
    depth = [0] * (n * 2)
    for _ in range(1, n):
        a, b, c = map(int, input().split())
        tree[a].append((b, c))
        tree[b].append((a, c))
 
    q, k = map(int, input().split())
    dfs(k, -1, 0)
    for _ in range(q):
        x, y = map(int, input().split())
        print(depth[x] + depth[y])
 
 
ans()

Solution (Python):
import queue
N=int(input())
a=[0 for i in range(N-1)]
b=[0 for i in range(N-1)]
c=[0 for i in range(N-1)]
VL=[dict() for i in range(N)]
for i in range(N-1):
    a[i],b[i],c[i]=map(int,input().split())
    a[i]-=1
    b[i]-=1
    VL[a[i]][b[i]]=c[i]
    VL[b[i]][a[i]]=c[i]
Q,K=map(int,input().split())
K-=1
x=[0 for i in range(Q)]
y=[0 for i in range(Q)]
for i in range(Q):
    x[i],y[i]=map(int,input().split())
    x[i]-=1
    y[i]-=1
reached=[False for i in range(N)]
dist=[0 for i in range(N)]
q=queue.Queue()
q.put(K)
reached[K]=True
while(not(q.empty())):
    r=q.get()
    for v in VL[r]:
        if not(reached[v]):
            q.put(v)
            dist[v]=VL[r][v]+dist[r]
            reached[v]=True
for i in range(Q):
    print(dist[x[i]]+dist[y[i]])

Solution (Python):
import queue
N=int(input())
a=[0 for i in range(N-1)]
b=[0 for i in range(N-1)]
c=[0 for i in range(N-1)]
VL=[dict() for i in range(N)]
for i in range(N-1):
    a[i],b[i],c[i]=map(int,input().split())
    a[i]-=1
    b[i]-=1
    VL[a[i]][b[i]]=c[i]
    VL[b[i]][a[i]]=c[i]
Q,K=map(int,input().split())
K-=1
x=[0 for i in range(Q)]
y=[0 for i in range(Q)]
for i in range(Q):
    x[i],y[i]=map(int,input().split())
    x[i]-=1
    y[i]-=1
reached=[False for i in range(N)]
dist=[0 for i in range(N)]
q=queue.Queue()
q.put(K)
reached[K]=True
while(not(q.empty())):
    r=q.get()
    for v in VL[r]:
        if not(reached[v]):
            q.put(v)
            dist[v]=VL[r][v]+dist[r]
            reached[v]=True
for i in range(Q):
    print(dist[x[i]]+dist[y[i]])

Solution (Python):
n = int(input())
a = [[int(i) for i in input().split()] for i in range(n-1)]
q,k = (int(i) for i in input().split())
question = [[int(i) for i in input().split()] for i in range(q)]
x,ans = [[] for i in range(n)],[False for i in range(n)]
for i in a:
	x[i[0]-1].append([i[1],i[2]])
	x[i[1]-1].append([i[0],i[2]])
visit = [False for i in range(n)]
visit[k-1],now = True,[k]
while now:
	p = now.pop()
	for i in x[p-1]:
		if not visit[i[0]-1]:
			visit[i[0]-1],ans[i[0]-1] = True,ans[p-1]+i[1]
			now.append(i[0])
for i in question:
	print(ans[i[0]-1]+ans[i[1]-1])

Solution (Python):

from collections import deque
def inpl(): return map(int, input().split())
N = int(input())

G = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, c = inpl()
    G[a].append([b, c])
    G[b].append([a, c])

Q, K = inpl()

def BFS(G, K):
    DQ = deque([K])
    D = [-1] * (N+1)
    D[K] = 0
    while DQ:
        p = DQ.popleft()
        for q, c in G[p]:
            if D[q] != -1:
                continue
            D[q] = D[p] + c
            DQ.append(q)
    return D

D = BFS(G, K)
for _ in range(Q):
    x, y = inpl()
    print(D[x] + D[y])