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):
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())
  tree[a-1].append([b-1,c])
  tree[b-1].append([a-1,c])
q,k=map(int,input().split())
dis=[-1 for i in range(n)]
dis[k-1]=0
que=deque()
que.append(k-1)
while que:
  x=que.popleft()
  for i,c in tree[x]:
    if dis[i]==-1:
      que.append(i)
      dis[i]=dis[x]+c
for i in range(q):
  x,y=map(int,input().split())
  print(dis[x-1]+dis[y-1])

Solution (Python):
def solve():
    N = int(input())
    T = [[] for _ in range(N+1)]
    searched = [False]*(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())
    distance = [10**9]*(N+1)
    distance[K] = 0
    
    
    queue = [K]
    while queue:
        dom = queue.pop()
        if searched[dom]:
            continue
        searched[dom] = True
        for cod, d in T[dom]:
            if searched[cod]:
                continue
            queue.append(cod)
            distance[cod] = distance[dom]+d
            
        
        
    
    
    for _ in range(Q):
        x,y = map(int, input().split())
        print(distance[x]+distance[y])
        
solve()

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

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


n = int(input())
lines = sys.stdin.readlines()
edges = [ [] for _ in range(n+1) ]
for i in range(n-1):
    e = tuple(map(int, lines[i].split(" ")))
    log(e)
    edges[e[0]].append((e[1],e[2]))
    edges[e[1]].append((e[0],e[2]))

q,k = map(int, lines[n-1].split(" "))

ddd = [0] * (n+1)


que = deque()
que.append(k)
def bfs(x):
    for y, d in edges[x]:
        if ddd[y]:
            continue
        ddd[y] = ddd[x] + d
        que.append(y)


while que:
    bfs(que.pop())

for i in range(n, n+q):
    x, y = map(int, lines[i].split(" "))
    log(x,y)
    print(ddd[x] + ddd[y])

Solution (Python):
from collections import deque
n = int(input())
G = [deque([]) for _ in range(n)]
for i in range(n - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append([b, c])
    G[b].append([a, c])
dist = [-1] * n

def dfs(v):
    cnt = 0
    stack = [[v, 0]]
    while stack:
        x = stack[-1]
        if len(G[x[0]]) > 0:
            w = G[x[0]].popleft()
            if dist[w[0]] == -1:
                dist[w[0]] = w[1] + dist[x[0]]
                stack.append(w)
        else: stack.pop()

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())

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

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

dist = [0] * (N + 1)


def dfs(v, p, d):
    dist[v] = d

    for n, dd in edges[v]:
        if n == p:
            continue
        dfs(n, v, d + dd)


dfs(K, -1, 0)

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

Solution (Python):

import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]", Q: int, K: int, x: "List[int]", y: "List[int]"):

    """graph.input.linkedlist_with_weight
        input: u[]:start, v[]:end, w[]:weight
        output:g[][]
    """
    g = [[] for i in range(N+1)]
    for i in range(N-1):
        g[a[i]].append([b[i], c[i]])
        g[b[i]].append([a[i], c[i]])

    def dikstra(nodes: int, graph: "List[List[int, int]]", start: int):
        """dikstra
        
        Arguments:
            nodes {int} -- Nodes in graph
            graph {List["List[int, int]"]} -- graph (adjancency matrix)
            start {int} -- start point
        
        Returns:
            [type] -- great distances from start point to each nodes in graph
        """
        INF = 1<<48
        from heapq import heapify, heappop, heappush
        hq = []
        heapify(hq)
        
        colors = ['W'] * (nodes+1)
        d = [INF] * (nodes+1)
        d[start] = 0
    
        heappush(hq, [start, start])
        colors[start] = 'G'
    
        while hq:
            f = hq.pop()
            u = f[1]
            colors[u]= 'B'
            
            if d[u] < -f[0]:
                continue
    
            for adj_i in graph[u]:
                v = adj_i[0]
                if colors[v] == 'B':
                    continue
                if d[v] > d[u] + adj_i[1]:
                    d[v] = d[u] + adj_i[1]
                    heappush(hq, [-d[v], v])
                    colors[v] = 'G'
        return d
    
    d = dikstra(N, g, K)

    for i in range(Q):
        print(d[x[i]]+d[y[i]])

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [int()] * (N - 1)  
    b = [int()] * (N - 1)  
    c = [int()] * (N - 1)  
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    Q = int(next(tokens))  
    K = int(next(tokens))  
    x = [int()] * (Q)  
    y = [int()] * (Q)  
    for i in range(Q):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, a, b, c, Q, K, x, y)

if __name__ == '__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]", Q: int, K: int, x: "List[int]", y: "List[int]"):
    """graph.input.linkedlist_with_weight
        input: u[]:start, v[]:end, w[]:weight
        output:g[][]
    """
    INF = 1<<48
    g = [[] for i in range(N+1)]
    for i in range(N-1):
        g[a[i]].append([b[i], c[i]])
        g[b[i]].append([a[i], c[i]])

    from heapq import heapify, heappop, heappush
    hq = []
    heapify(hq)
    
    s = K
    colors = ['W'] * (N+1)
    d = [INF] * (N+1)
    d[s] = 0

    heappush(hq, [s, s])
    colors[s] = 'G'

    while hq:
        f = hq.pop()
        u = f[1]
        colors[u]= 'B'
        
        if d[u] < -f[0]:
            continue

        for adj_i in g[u]:
            v = adj_i[0]
            if colors[v] == 'B':
                continue
            if d[v] > d[u] + adj_i[1]:
                d[v] = d[u] + adj_i[1]
                heappush(hq, [-d[v], v])
                colors[v] = 'G'

    for i in range(Q):
        print(d[x[i]]+d[y[i]])

    

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [int()] * (N - 1)  
    b = [int()] * (N - 1)  
    c = [int()] * (N - 1)  
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    Q = int(next(tokens))  
    K = int(next(tokens))  
    x = [int()] * (Q)  
    y = [int()] * (Q)  
    for i in range(Q):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, a, b, c, Q, K, x, y)

if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
edge = [[] for _ in range(N)]
for _ in range(N-1):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    edge[a].append((b,c))
    edge[b].append((a,c))
Q,K = map(int,input().split())
K -= 1
dist = [-1 for _ in range(N)]
dist[K] = 0
searched = [i == K for i in range(N)]
search = [e for e in edge[K]]
while len(search) > 0:
    e = search.pop()
    n,d = e[0], e[1]
    searched[n] = True
    dist[n] = d
    for c,d2 in edge[n]:
        if searched[c]:
            continue
        search.append((c, d+d2))
for _ in range(Q):
    x,y= map(int, input().split())
    x -= 1
    y -= 1
    print(dist[x]+dist[y])

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

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

def dfs(v):
    dist = [10 ** 20] * (n+1)
    stack = [v]
    dist[v] = 0
    while stack:
        v = stack.pop()
        for w,cost in graph[v]:
            if dist[w] >= dist[v] + cost:
                dist[w] = dist[v] + cost
                stack.append(w)
    return dist
q,k = map(int,input().split())
distance = dfs(k)
for i in range(q):
    x,y = map(int,input().split())
    print(distance[x]+distance[y])

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n=int(input())
abc=[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)]

lst=[[] for i in range(n+1)]

for i in range(n-1):
    a,b,c=abc[i]
    lst[a].append([b,c])
    lst[b].append([a,c])
dist=[float('inf')]*(n+1)


d=deque()
d.append([[[k,0]],0])
while d:
    tmp=d.popleft()
    
    for i in range(len(tmp[0])):
        
        if dist[tmp[0][i][0]]==float('inf'):
            dist[tmp[0][i][0]]=tmp[0][i][1]+tmp[-1]
            d.append([lst[tmp[0][i][0]],dist[tmp[0][i][0]]])

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
INF = 1001001001

N = int(input())
g = [[] for _ 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 = [INF] * N
dist[K-1] = 0

def dfs(n, d):
    if dist[n] == INF:
        dist[n] = d
    for i, c in g[n]:
        if dist[i] == INF:
            dfs(i, dist[n]+c)
    return

dfs(K-1, 0)


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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 8)
N = int(input())
graph = [[] * N for _ 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())
xy = [list(map(int, input().split())) for _ in range(Q)]

depth = [0] * N
def dfs(v, p, d):
    depth[v] = d
    for new_v_list in graph[v]:
        new_v = new_v_list[0]
        if new_v == p:
            continue
        dfs(new_v, v, d + new_v_list[1])

dfs(K-1, -1, 0)
for i in range(Q):
    print(depth[xy[i][0] - 1] + depth[xy[i][1] - 1])

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 8)
N = int(input())
graph = [[] * N for _ 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())
xy = [list(map(int, input().split())) for _ in range(Q)]

depth = [0] * N
def dfs(v, p, d):
    depth[v] = d
    for new_v_list in graph[v]:
        new_v = new_v_list[0]
        if new_v == p:
            continue
        dfs(new_v, v, d + new_v_list[1])

dfs(K-1, -1, 0)
for i in range(Q):
    print(depth[xy[i][0] - 1] + depth[xy[i][1] - 1])

Solution (Python):
from collections import deque
N = int(input())
graph = [[] * N for _ 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())
xy = [list(map(int, input().split())) for _ in range(Q)]


dist = [-1 for _ in range(N)]   
que = deque()


dist[K-1] = 0
que.append(K-1)


while que:
    v = que[0]
    que.popleft()
    for new_v_list in graph[v]:
        new_v = new_v_list[0]
        if dist[new_v] != -1:   
            continue
        
        dist[new_v] = dist[v] + new_v_list[1]
        que.append(new_v)


for i in range(Q):
    print(dist[xy[i][0] - 1] + dist[xy[i][1] - 1])

Solution (Python):
from collections import deque
N = int(input())
graph = [[] * N for _ 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())
xy = [list(map(int, input().split())) for _ in range(Q)]


dist = [-1 for _ in range(N)]   
que = deque()


dist[K-1] = 0
que.append(K-1)


while que:
    v = que[0]
    que.popleft()
    for new_v_list in graph[v]:
        new_v = new_v_list[0]
        if dist[new_v] != -1:   
            continue
        
        dist[new_v] = dist[v] + new_v_list[1]
        que.append(new_v)


for i in range(Q):
    print(dist[xy[i][0] - 1] + dist[xy[i][1] - 1])

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

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

INF = 10 ** 15
dist = [INF] * (N+1)
def set_dist(x, d):
    dist[x] = d
    for next, dd in edges[x]:
        if dist[next] != INF:
            continue
        set_dist(next, d + dd)


Q, K = lr()
set_dist(K, 0)
for i in range(Q):
    x, y = lr()
    print(dist[x] + dist[y])

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def measure(x):
    dist = [INF] * (N)
    dist[x] = 0
    que = deque()
    que.append(x)
    while que:
        cur = que.popleft()
        cur_dist = dist[cur]
        for next, c in edges[cur]:
            if dist[next] == INF:
                dist[next] = cur_dist + c
                que.append(next)
    
    return dist

N = ir()
INF = 10 ** 15
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = lr()
    edges[a-1].append((b-1, c))
    edges[b-1].append((a-1, c))

Q, K = lr()
dist = measure(K-1)
for _ in range(Q):
    x, y = lr()
    print(dist[x-1] + dist[y-1])

Solution (Python):
import sys
n = int(input())
graph = [[] for _ in range(n)]
for _ 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
xy = []
for _ in range(q):
    x, y = map(int, input().split())
    x-=1
    y-=1
    xy.append((x, y))

def DFS(node, p_node, length):
    l[node] = length
    for i, j in graph[node]:
        if i==p_node:
            continue
        DFS(i, node, length+j)
sys.setrecursionlimit(2 * n)
l = [0]*n
DFS(k, -1, 0)
for x, y in xy:
    print(l[x]+l[y])

Solution (Python):
from collections import deque


def dfs():
    dis_from_k = [float('inf') for _ in range(N+1)]
    q = deque()
    used = set()
    q.append([K, 0])
    used.add(K)

    while len(q) > 0:
        prv_node, prv_cost = q.pop()
        for node, cost in g[prv_node]:
            if node in used:
                continue
            dis_from_k[node] = min(dis_from_k[node], prv_cost + cost)
            q.append([node, prv_cost + cost])
            used.add(node)
    return dis_from_k


N = int(input())
g = {i: [] for i in range(1, 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())
dis_from_k = dfs()

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

Solution (Python):
from collections import deque

n=int(input())

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

def BFS(s):
 dist=[-1 for i in range(n)]
 dist[s]=0

 que=deque()
 que.append(s)

 while que:
  x=que.popleft()
  for i,c in tree[x]:
   if dist[i]==-1:
    que.append(i)
    dist[i]=dist[x]+c

 return dist

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

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

Solution (Python):
from collections import deque

n=int(input())

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

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

que=deque()
que.append(k-1)

while que:
 x=que.popleft()
 for i,c in tree[x]:
  if dist[i]==-1:
   que.append(i)
   dist[i]=dist[x]+c

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

Solution (Python):
from collections import deque
N = int(input())
edge = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    edge[a-1].append((b-1, c))
    edge[b-1].append((a-1, c))
Q, K = map(int, input().split())
seen = [0] * N
dist = [0] * N
seen[K-1] = 0
todo = deque([(K-1, 0)])
while todo:
    cur_v, cur_weight = todo.pop()
    seen[cur_v] = 1
    dist[cur_v] = cur_weight
    for next_v, next_weight in edge[cur_v]:
        if not seen[next_v]:
            todo.append((next_v, cur_weight + next_weight))

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

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

q, k = map(int, input().split())
k -= 1
hq = []
d = [10**18] * n
d[k] = 0
heapq.heappush(hq, (0, k))
while len(hq):
    dist, v = heapq.heappop(hq)
    if d[v] < dist:
        continue
    for e in g[v]:
        nv, l = e
        if d[nv] > d[v] + l:
            d[nv] = d[v] + l
            heapq.heappush(hq, (d[nv], nv))

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

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline

def main():    
    for i in range(N-1):
        a, b, c = map(int, input().split())
        a -= 1; b -= 1
        g[a].append((b, c))
        g[b].append((a, c))
        
    Q, K = map(int, input().split())
    K -= 1
        
    q = deque([(K, 0, -1)])

    while q:
        v, c, p = q.popleft()
        
        dist[v] = c
        for u, d in g[v]:
            if u == p: continue
            q.append((u, c+d, v))
    
    for i in range(Q):
        x, y = map(int, input().split())
        print(dist[x-1]+dist[y-1])
 
if __name__ == '__main__':
    N = int(input())
    g = [[] for i in range(N)]
    dist = [0] * N
    main()

Solution (Python):
import sys
from heapq import heappush, heappop, heapify
input = sys.stdin.readline

def main():
    N = int(input())
    g = [[] for i in range(N)]
    
    for i in range(N-1):
        a, b, c = map(int, input().split())
        a -= 1; b -= 1
        g[a].append((c, b))
        g[b].append((c, a))
        
    Q, K = map(int, input().split())
    K -= 1
    dist = [0] * N
    visited = [False] * N
    
    q = [(c, v) for c, v in g[K]]
    heapify(q)
    
    dist[K], visited[K] = 0, True
    
    while q:
        c, v = heappop(q)
        
        if visited[v]: continue
        dist[v], visited[v] = c, True
        
        for d, u in g[v]:
            if visited[u]: continue
            heappush(q, (c+d, u))
        
    for i in range(Q):
        x, y = map(int, input().split())
        
        print(dist[x-1]+dist[y-1])
        
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    T = [[] for _ in range(N+1)]
    cost = [None] * (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())
    cost[K] = 0
    stack = [K]
    while stack:
        x = stack.pop()
        d = cost[x]
        for y, c in T[x]:
            if cost[y] is None:
                cost[y] = d + c
                stack.append(y)
    for _ in range(Q):
        x, y = map(int, input().split())
        print(cost[x]+cost[y])

if __name__ == "__main__":
    main()

Solution (Python):

def main():
    n = int(input())
    edge = []
    for i in range(n):
        edge.append([])
    for i in range(n-1):
        abc = list(map(int, input().split()))
        edge[abc[0]-1].append((abc[1]-1, abc[2])) 
        edge[abc[1]-1].append((abc[0]-1, abc[2])) 
    q, k = map(int, input().split())
    k -= 1 
    xy = []
    for i in range(q):
        xy.append(list(map(int, input().split())))
        xy[-1][0] -= 1 
        xy[-1][1] -= 1 

    distance_from_k = []
    visited = []
    for i in range(n):
        distance_from_k.append(0)
        visited.append(False)
    st = [k]
    while st:
        now = st.pop()
        if visited[now]:
            continue
        visited[now] = True
        for x in edge[now]:
            if visited[x[0]]:
                continue
            distance_from_k[x[0]] = distance_from_k[now] + x[1]
            st.append(x[0])

    ans = []
    for i in range(q):
        ans.append(distance_from_k[xy[i][0]] + distance_from_k[xy[i][1]])

    for x in ans:
        print(x)

if __name__ == '__main__':
    main()

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

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


Q,K=[int(x) for x in input().split()]
dist=[0 for i in range(N+1)]

import heapq
queue=[[K,0]]
heapq.heapify(queue)
while queue:
	
	a=heapq.heappop(queue)
	node=a[0]
	cost=a[1]
	for temp in adj[node]:
		if dist[temp[0]]==0:
			heapq.heappush(queue,[temp[0],temp[1]+cost])
			dist[temp[0]]=cost+temp[1]

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

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

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



stack=[(K,0)]
dist=[0]*(N+1)
dist[K]=0
while stack:
    n,c=stack.pop()
    for to,cost in E[n]:
        if dist[to]:
            continue
        dist[to]=c+cost
        stack.append((to,c+cost))

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

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

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

Q, K = map(int, input().split())
qs = [tuple(map(int, input().split())) for _ in range(Q)]
K -= 1

INF = 10 ** 12
dist = [INF] * N

def dfs(v, p=-1, d=0):
    dist[v] = d
    for nv, c in es[v]:
        if nv == p:
            continue
        dfs(nv, v, d+c)

dfs(K, -1, 0)
for x, y in qs:
    print(dist[x-1]+dist[y-1])

Solution (Python):
N = int(input())
edge = [[] for i in range(N)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    edge[a-1].append((c, b-1))
    edge[b-1].append((c, a-1))
Q, K = map(int, input().split())
query = [tuple(map(int, input().split())) for _ in range(Q)]

import heapq

def dijkstra_heap(s):
    d = [10**12] * N
    used = [False] * N
    d[s] = 0
    used[s] = True
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist, e)
    while len(edgelist):
        min_edge = heapq.heappop(edgelist)
        if used[min_edge[1]]:
            continue
        v = min_edge[1]
        d[v] = min_edge[0]
        used[v] = True
        for e in edge[v]:
            heapq.heappush(edgelist, (e[0] + d[v], e[1]))
    return d

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

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

Q,K=map(int,input().split())
K-=1
from collections import deque
que=deque()
que.append(K)
unvisited=[1]*N
unvisited[K]=0
l=[0]*N
while que:
    v=que.pop()
    for u in g[v]:
        if unvisited[u]:
            l[u]=l[v]+length[(u,v)]
            que.appendleft(u)
            unvisited[u]=0

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

Solution (Python):
from collections import deque

N = int(input())
ABC=[map(int,input().split(' ')) for i in range(N-1)]
Q,K =  map(int,input().split(' '))
query = [map(int,input().split(' ')) for i in range(Q)]
tree = [[] for i in range(N+1)]
for a,b,c in ABC:
    tree[b].append((a,c))
    tree[a].append((b,c))
k_shortest = [0]*(N+1)
stack=deque([K])
while stack:
    k = stack.popleft()
    for v,d in tree[k]:
        if k_shortest[v] == 0:
            k_shortest[v] = k_shortest[k]+d
            stack.append(v)
for i,j in query:
    print(k_shortest[i]+k_shortest[j])

Solution (Python):
from collections import deque

def dfs(graph, start, n):
    stack = deque()
    push, pop = stack.append, stack.pop
    inf = float('INF')
    costs = [inf for i in range(n)]
    visited = [False] * n
    push((start, 0))
    visited[start] = True
    costs[start] = 0

    while stack:
        a,c = pop()
        for b,cc in graph[a].items():
            if visited[b]:
                continue
            if cc + c < costs[b]:
                push((b, cc+c))
                visited[b] = True
                costs[b] = cc + c
    return costs

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

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

Solution (Python):

import heapq
def dijkstra_heap(s):
    """
    始点sから各頂点への最短距離を返す

    Parameters
    ----------
    s : int
        視点とする頂点

    Returns
    -------
    d ：list
    始点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[0]]:
            continue
        v = minedge[0]
        d[v] = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[0]]:
                heapq.heappush(edgelist,[e[0],e[1]+d[v]])
    return d

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

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

Solution (Python):
import sys

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

Q, K = map(int, input().split())
dist = [0] * N
sys.setrecursionlimit(2 * N)
def rec(v, pred, d):
    dist[v] = d
    for u, c in E[v]:
        if u == pred:
            continue
        rec(u, v, d + c)
rec(K-1, -1, 0)
ans = [0] * Q
for i in range(Q):
    x, y = map(int, input().split())
    ans[i] = dist[x-1] + dist[y-1]

[print(a) for a in ans]

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

def calcurate_cost(fr, to, cost):
  cost_from_k[to] += cost_from_k[fr]+cost
  for n_to, n_cost in tree[to]:
    if n_to == fr:
      continue
    if K != n_to:
      calcurate_cost(to, n_to, n_cost)
      
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
calcurate_cost(K, K, 0)

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

Solution (Python):
from collections import deque

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

Q, K = map(int, input().split())
distance = [0] * N
stack = deque([K-1])

while stack:
    v = stack.pop()
    for u, c in E[v]:
        if distance[u] != 0:
            continue
        distance[u] = distance[v] + c
        stack.append(u)
    

ans = [0] * Q
for i in range(Q):
    x, y = map(int, input().split())
    ans[i] = distance[x-1] + distance[y-1]

[print(a) for a in ans]

Solution (Python):
from collections import deque

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

Q, K = map(int, input().split())
distance = [0] * N
stack = deque([K-1])
checked = [False] * N
while stack:
    v = stack.pop()
    for u, c in E[v]:
        if checked[u]:
            continue
        distance[u] = distance[v] + c
        stack.append(u)
    checked[v] = True

ans = [0] * Q
for i in range(Q):
    x, y = map(int, input().split())
    ans[i] = distance[x-1] + distance[y-1]

[print(a) for a in ans]