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
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    G[a - 1].append([c, b - 1])
    G[b - 1].append([c, a - 1])
Q, K = map(int, input().split())

def dijkstra(s, N, G):
    d = [float('inf')] * N
    d[s] = 0
    hq = [[0, s]]
    heapq.heapify(hq)
    while len(hq) > 0:
        v, i = heapq.heappop(hq)
        if d[i] < v:
            continue
        for c, j in G[i]:
            if d[j] > d[i] + c:
                d[j] = d[i] + c
                heapq.heappush(hq, [d[j], j])
    return d

D = dijkstra(K - 1, N, G)

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

for d in dist:
    print(d)

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

INF = 10 ** 18

class Edge():
    def __init__(self, start, end, cost):
        self.start = start
        self.end = end
        self.cost = cost
    def __str__(self):
        return 'Edge: {} -> {}, cost {}'.format(self.start, self.end, self.cost)

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    h = []
    heapq.heappush(h, (0, s))

    while h:
        
        d, v = heapq.heappop(h)
        if dist[v] < d:
            continue
        
        for e in G[v]:
            if dist[e.end] > dist[v] + e.cost:
                dist[e.end] = dist[v] + e.cost
                heapq.heappush(h, (dist[e.end], e.end))
    return dist


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

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

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

d = dijkstra(n, es, k)

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
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([y-1,z])
    edge[y-1].append([x-1,z])
q,k=map(int,input().split())
dist=[-1]*n
def dfs(node,d):
    dist[node]=d
    for i in edge[node]:
        if dist[i[0]]==-1:
            dfs(i[0],d+i[1])
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
import heapq

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


INF = 10**18


def dijkstra(N, s0, edge):

    d = [INF] * N  
    used = [False] * N  
    edgelist = [(0, s0)]  
    heapq.heapify(edgelist)  

    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True
        for e in edge[v]:
            if d[e[1]] <= (e[0] + d[v]) or used[e[1]]:
                continue
            heapq.heappush(edgelist, [e[0] + d[v], e[1]])
    return d


def main():
    N = in_n()

    edge = [[]for _ in range(N)]
    for i in range(N - 1):
        a, b, c = in_nn()
        a, b = a - 1, b - 1
        edge[a].append((c, b))
        edge[b].append((c, a))

    Q, K = in_nn()
    d = dijkstra(N, K - 1, edge)

    ans = []
    for i in range(Q):
        x, y = in_nn()
        x, y = x - 1, y - 1
        ans.append(d[x] + d[y])

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


if __name__ == '__main__':
    main()

Solution (Python):







from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')

def dijkstra(s,n,g):
    seen = [False]*n
    cost = [INF]*n
    cost[s] = 0 
    next_q = [(0,s)]
    heapify(next_q)
    while len(next_q)>0:
        c, i = heappop(next_q)
        if cost[i] < c:
            continue
        for nedge, ncost in g[i]:
            nc = cost[i]+ncost
            if cost[nedge]>nc:
                cost[nedge] = nc
                heappush(next_q,(nc, nedge))
    return cost

def main():
    N = int(input())
    graph_F = [[] for _ in range(N)]

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


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

if __name__ == '__main__':
    main()

Solution (Python):

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

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

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

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

print(*result, sep='\n')

Solution (Python):

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

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

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

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

Solution (Python):

from collections import deque

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

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

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

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

print(*result, sep='\n')

Solution (Python):

from collections import deque

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

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

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

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

Solution (Python):

from heapq import heappop, heappush

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

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

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

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

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

Solution (Python):

from heapq import heappop, heappush

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

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

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

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

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

print('\n'.join(str(v) for v in result))

Solution (Python):
class Tree_with_edge_cost:
    def __init__(self, n, edge):
        self.n = n
        self.nexts = [[] for _ in range(n)]
        for u, v, c in edge:
            self.nexts[u].append((v, c))
            self.nexts[v].append((u, c))
        self.parent = [-1] * self.n
        self.children = [[] for _ in range(self.n)]
        self.cost = [0] * self.n
        self.dist = [0] * self.n  
        self.depth = [0] * self.n  
        self.order = []

    def set_root(self, root):  
        self.order.append(root)
        stack = [root]
        while stack:
            v = stack.pop()
            for child, cost in self.nexts[v]:
                if child == self.parent[v]:
                    continue
                else:
                    self.parent[child] = v
                    self.children[v].append(child)
                    self.depth[child] = self.depth[v] + 1
                    self.dist[child] = self.dist[v] + cost
                    self.cost[child] = cost
                    self.order.append(child)
                    stack.append(child)

    def get_diameter(self, restore=False):  
        u = self.dist.index(max(self.dist))  
        dist_u = [-1] * self.n
        dist_u[u] = 0
        stack = [u]
        parent_u = [None for _ in range(self.n)]
        while stack:
            v = stack.pop()
            for child, cost in self.nexts[v]:
                if dist_u[child] == -1:
                    dist_u[child] = dist_u[v] + cost
                    parent_u[child] = v
                    stack.append(child)
        diameter = max(dist_u)
        v = dist_u.index(diameter)
        if restore:
            path = [v]
            while v != u:
                v = parent_u[v]
                path.append(v)
            path.reverse()  
            return diameter, path
        else:
            return diameter, u, v



n = int(input())
edges = []
for _ in range(n-1):
    a, b, c = (int(x) for x in input().split())
    a -= 1
    b -= 1
    edges.append((a, b, c))
q, k = (int(x) for x in input().split())
queries = [tuple(int(x) for x in input().split()) for _ in range(q)]
tree = Tree_with_edge_cost(n, edges)
tree.set_root(k-1)

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

Solution (Python):
class RadixHeap:
    __slots__ = ["data", "last", "siz", "used"]

    
    def __init__(self, N, C):
        self.data = [[] for i in range(C.bit_length() + 1000)]
        self.last = self.siz = 0
        self.used = [0] * N

    def push(self, x, key):
        
        self.siz += 1
        self.data[(x ^ self.last).bit_length()].append((x, key))

    def pop(self):
        data = self.data
        used = self.used
        
        if not data[0]:
            i = 1
            while not data[i]:
                i += 1
            d = data[i]
            new_last, new_key = min(d)
            used[new_key] = 1
            for val in d:
                x, key = val
                if used[key]:
                    self.siz -= 1
                    continue
                data[(x ^ new_last).bit_length()].append(val)
            self.last = new_last
            data[i] = []
        else:
            new_last, new_key = data[0].pop()
            used[new_key] = 1
            self.siz -= 1
        return new_last, new_key

    def __len__(self):
        return self.siz

def dijkstra(N, G, s):
    que = RadixHeap(N, 10**9 + 1)

    dist = [10**18] * N
    dist[s] = 0
    que.push(0, s)
    while que:
        cost, v = que.pop()
        if dist[v] < cost:
            continue
        for w, c in G[v]:
            if cost + c < dist[w]:
                dist[w] = r = cost + c
                que.push(r, w)
    return dist



n = int(input())
ABC = [tuple(int(x) for x in input().split()) for _ in range(n - 1)]
q, k = (int(x) for x in input().split())
queries = [tuple(int(x) for x in input().split()) for _ in range(q)]
G = [[] for _ in range(n)]
for a, b, c in ABC:
    a -= 1
    b -= 1
    G[a].append((b, c))
    G[b].append((a, c))
dist = dijkstra(n, G, k-1)
for x, y in queries:
    x -= 1
    y -= 1
    print(dist[x] + dist[y])

Solution (Python):
import sys
def input():return sys.stdin.readline().strip()
from collections import deque

def main():
    N = int(input())
    info = [tuple(map(int, input().split())) for _ in range(N-1)]
    Q, K = map(int, input().split())
    queries = [tuple(map(int, input().split())) for _ in range(Q)]

    to = [[] for _ in range(N)]
    for a, b, c in info:
        a -= 1
        b -= 1
        to[a].append((b, c))
        to[b].append((a, c))
    
    INF = 10**18
    dist = [INF]*N
    def dfs(s):
        stack = deque()
        push = stack.append
        pop = stack.pop

        dist[s] = 0
        push(s)

        while stack:
            now = pop()
            now_cost = dist[now]

            for nv, c in to[now]:
                if dist[nv] != INF:
                    continue
                dist[nv] = now_cost + c
                push(nv)


    
    K -= 1
    dfs(K)
    ans = []
    for x, y in queries:
        x -= 1
        y -= 1
        xy = dist[x] + dist[y]
        ans.append(xy)

    print(*ans, sep="\n")
if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque


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


def bfs(start):
    q = deque([start])
    dist = [-1] * (N + 1)
    dist[start] = 0
    while q:
        v = q.popleft()
        for nv, nw in g[v]:
            if dist[nv] > 0:
                continue
            dist[nv] = dist[v] + nw
            q.append(nv)
    return dist


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 = bfs(K)
ans = []
for _ in range(Q):
    x, y = map(int, input().split())
    print(d[x] + d[y])

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


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


def dijkstra(adj_list, start):
    n = len(adj_list)
    dist = [float("inf")] * n
    dist[start] = 0

    pq = []
    heappush(pq, (0, start))
    visited = set()
    while pq:
        w, v = heappop(pq)
        if dist[v] < w:
            continue
        visited.add(v)
        for nv, nw in adj_list[v]:
            if nv in visited:
                continue
            if dist[nv] > dist[v] + nw:
                dist[nv] = dist[v] + nw
                heappush(pq, (dist[nv], nv))
    return dist


N = int(input())
g = defaultdict(list)
for _ 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
d = dijkstra(g, K)
ans = []
for _ in range(Q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    print(d[x] + d[y])

Solution (Python):
import sys

sys.setrecursionlimit(10**6)


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

SD=[0]*N
def DFS(v,p,d):
    SD[v]=d
    for i,co in G[v]:
        if i==p:continue
        DFS(i,v,d+co)
    return

DFS(K-1,-1,0)

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

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

SD=[0]*N
seen=[0]*N
stack=[]
stack.append([K-1,0])
seen[K-1]=1
while stack:
    x,d=stack.pop()
    for y,d0 in G[x]:
        if seen[y]==0:
            SD[y]=d+d0
            stack.append([y,d+d0])
            seen[y]=1
for i in range(Q):
    x,y=map(int,input().split())
    ans=SD[x-1]+SD[y-1]
    print(ans)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, deque

    n = int(readline())
    edge = defaultdict(list)

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

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

    que = deque()
    que.append((k, 0))
    dists = dict()

    while que:
        u, dist = que.popleft()
        for v, w in edge[u]:
            if v not in dists:
                dists[v] = dist + w
                que.append((v, dist + w))

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque

N = int(input())
connected = [[]for _ in range(N+1)]
for i in range(N-1):
    a, b, c = (int(x) for x in input().split())
    connected[a].append((b,c))
    connected[b].append((a,c))
Q, K = (int(x) for x in input().split())
distk = [-1] * (N+1)
d = deque([K])
distk[K] = 0
while d:
    temp = d.popleft()
    for vert, dist in connected[temp]:
        if distk[vert] == -1:
            d.append(vert)
            distk[vert] = distk[temp] + dist
for i in range(Q):
    x, y = (int(x) for x in input().split())
    print(distk[x]+distk[y])

Solution (Python):

def Graph(ab):
    G = [[] for i in range(n)]
    for a, b, c in ab:
        G[a - 1].append([b, c])
        G[b - 1].append([a, c])
    return G

from collections import deque
def bfs(k):
    q = deque()
    q.append((k, - 1, 0))
    dis = [0] * n 
    while q:
        V, P, cnt = q.popleft()
        for nv, d in G[V - 1]:
            if nv == P:continue
            dis[nv - 1] = cnt + d
            q.append((nv, V, cnt + d))
    
    return dis 

n = int(input())
abc = [list(map(int,input().split())) for _ in range(n - 1)]
G = Graph(abc)
q, k = map(int,input().split())
dis = bfs(k)

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

Solution (Python):
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
e = dd(list)
for _ in range(N - 1):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
  e[v].append((u, c))
Q, K = map(int, input().split())

dp = [10 ** 15] * (N + 1)
dp[K] = 0
s = [K]
while len(s):
  x = s.pop()
  for y, d in e[x]:
    if dp[y] > dp[x] + d:
      s.append(y)
      dp[y] = dp[x] + d

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

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
from collections import defaultdict
ns = defaultdict(set)
for i in range(n-1):
    u,v,c = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add((c,v))
    ns[v].add((c,u))

k = len(bin(n-1))-2

def cdepth(root=0):
    
    ps = [None] * n
    ps[0] = -1
    q = [0]
    while q:
        u = q.pop()
        for c,v in ns[u]:
            if ps[v] is None:
                ps[v] = u
                q.append(v)
    
    depth = [None] * n
    depth[root] = 0
    q = [root]
    while q:
        u = q.pop()
        for c,v in ns[u]:
            if depth[v] is None:
                depth[v] = depth[u] + 1
                q.append(v)
    return depth, ps
def dijkstra(start):
    import heapq
    vals = [None] * n
    h = [(0, start)] 
    vals[start] = 0
    while h:
        val, u = heapq.heappop(h)
        for d, v in ns[u]:
            if vals[v] is None or vals[v]>val+d:
                vals[v] = val+d
                heapq.heappush(h, (vals[v], v))
    return vals


def double(ps):
    
    k = 0
    while pow(2,k)<n:
        k += 1
    prev = [[None]*n for _ in range(k)] 
    for j in range(n):
        prev[0][j] = ps[j]
    for i in range(1,k):
        for j in range(n):
            p = prev[i-1][j]
            if p>=0:
                prev[i][j] = prev[i-1][p]
            else:
                prev[i][j] = p
    return prev
            


def cprev(u,i):
    """uからi個上の頂点を返す
    """
    for j in range(k):
        if i>>j&1:
            u = prev[j][u]
    return u


def lca(u,v):
    if depth[u]<depth[v]:
        v = cprev(v, depth[v]-depth[u])
    else:
        u = cprev(u, depth[u]-depth[v])
    if u==v:
        return u
    for i in range(k-1, -1, -1):
        if prev[i][u]!=prev[i][v]:
            u = prev[i][u]
            v = prev[i][v]
    return prev[0][u]

q,K = map(int, input().split())
K -= 1
dist = dijkstra(K)
ans = [None]*q
for i in range(q):
    x,y = map(int, input().split())
    x -= 1
    y -= 1
    ans[i] = dist[x] + dist[y]
write("\n".join(map(str, ans)))

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
from collections import defaultdict
ns = defaultdict(set)
for i in range(n-1):
    u,v,c = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add((c,v))
    ns[v].add((c,u))

k = len(bin(n-1))-2

def cdepth(root=0):
    
    ps = [None] * n
    ps[0] = -1
    q = [0]
    while q:
        u = q.pop()
        for c,v in ns[u]:
            if ps[v] is None:
                ps[v] = u
                q.append(v)
    
    depth = [None] * n
    depth[root] = 0
    q = [root]
    while q:
        u = q.pop()
        for c,v in ns[u]:
            if depth[v] is None:
                depth[v] = depth[u] + 1
                q.append(v)
    return depth, ps
def dijkstra(start):
    import heapq
    vals = [None] * n
    h = [(0, start)] 
    vals[start] = 0
    while h:
        val, u = heapq.heappop(h)
        for d, v in ns[u]:
            if vals[v] is None or vals[v]>val+d:
                vals[v] = val+d
                heapq.heappush(h, (vals[v], v))
    return vals


def double(ps):
    
    k = 0
    while pow(2,k)<n:
        k += 1
    prev = [[None]*n for _ in range(k)] 
    for j in range(n):
        prev[0][j] = ps[j]
    for i in range(1,k):
        for j in range(n):
            p = prev[i-1][j]
            if p>=0:
                prev[i][j] = prev[i-1][p]
            else:
                prev[i][j] = p
    return prev
            


def cprev(u,i):
    """uからi個上の頂点を返す
    """
    for j in range(k):
        if i>>j&1:
            u = prev[j][u]
    return u


def lca(u,v):
    if depth[u]<depth[v]:
        v = cprev(v, depth[v]-depth[u])
    else:
        u = cprev(u, depth[u]-depth[v])
    if u==v:
        return u
    for i in range(k-1, -1, -1):
        if prev[i][u]!=prev[i][v]:
            u = prev[i][u]
            v = prev[i][v]
    return prev[0][u]

dist = dijkstra(0)
depth, ps = cdepth(0)
prev = double(ps)
q,K = map(int, input().split())
K -= 1
ans = [None]*q
for i in range(q):
    x,y = map(int, input().split())
    x -= 1
    y -= 1
    l1 = lca(x,K)
    l2 = lca(y,K)

    ans[i] = (dist[x]+dist[K]-2*dist[l1]) + (dist[y]+dist[K]-2*dist[l2])
write("\n".join(map(str, ans)))

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    way = [[] for _ in range(n+1)]
    for _ in range(n-1):
        a,b,c = map(int,ipt().split())
        way[a].append((b,c))
        way[b].append((a,c))
    q,k = map(int,ipt().split())
    l = [-1]*(n+1)
    l[k] = 0
    Q = queue.Queue()
    Q.put(k)
    while not Q.empty():
        qi = Q.get()
        lq = l[qi]
        for bi,ci in way[qi]:
            if l[bi] == -1:
                l[bi] = lq+ci
                Q.put(bi)

    for i in range(q):
        x,y = map(int,ipt().split())
        print(l[x]+l[y])

    return

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
G = [[] for _ in range(n)]
for _ 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 = tuple(map(int, input().split()))
INF = 10**9*n + 1
dists = [INF] * n
dists[k-1] = 0

from collections import deque
q = deque([k-1])

while q:
    node = q.popleft()
    for to, c in G[node]:
        if dists[to] > dists[node] + c:
            dists[to] = dists[node] + c
            q.append(to)

for _ in range(Q):
    s, g = tuple(map(int, input().split()))
    print(dists[s-1] + dists[g-1])

Solution (Python):
n = int(input())
G = [[] for _ in range(n)]
for _ 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 = tuple(map(int, input().split()))
INF = 10**9*n + 1
dists = [INF] * n
dists[k-1] = 0

from collections import deque
q = deque([k-1])
visited = [0] * n
visited[k-1] = 1

while q:
    node = q.popleft()
    for to, c in G[node]:
        if visited[to] == 1:
            continue

        if dists[to] > dists[node] + c:
            dists[to] = dists[node] + c
            q.append(to)

for _ in range(Q):
    s, g = tuple(map(int, input().split()))
    print(dists[s-1] + dists[g-1])

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


def dijkstra(path, N, start):
    """
    Args:
        path (list): [[(cost, node), (cost, node), ...], [], [], ...]
    """
    visited = [False] * N
    que = [(0, start)]
    heapify(que)  
    dist = [-1] * N  
    dist[start] = 0  
    while que:
        d, v = heappop(que)  
        visited[v] = True  
        
        for d, to in path[v]:
            cost = dist[v] + d
            if dist[to] < 0 or cost < dist[to]:
                dist[to] = cost
                if not visited[to]:
                    heappush(que, (cost, to))

    return dist


def main():
    N = int(readline())
    path = [[] for _ in range(N)]

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

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


if __name__ == '__main__':
    main()

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


n = int(input())
query = [[] for i in range(n)]
for i in range(n-1):
    a, b, c = map(int, input().split())
    query[a-1].append((b-1, c))
    query[b-1].append((a-1, c))
q, k = map(int, input().split())
stack = deque([(k-1, 0, -1)])
dist = [0] * n
while stack:
    now, cnt, per = stack.pop()
    lis = query[now]
    dist[now] = cnt
    for nx, c in lis:
        if nx == per:
            continue
        if c != 0:
            stack.append((nx, cnt+c, now))
for i in range(q):
    x, y = map(int, input().split())
    print(dist[x-1] + dist[y-1])

Solution (Python):
from collections import *
import sys
S=sys.stdin.readlines()
N=int(S[0])
G=[[] for i in range(N)]
a,b,c=0,0,0
for i in range(N-1):
  a,b,c=map(int,S[i+1].split())
  a,b=a-1,b-1
  G[a].append((b,c))
  G[b].append((a,c))
Q,K=map(int,S[N].split())
D,Z=deque(),set()
def qao(x):
  global D,Z
  if x in Z:
    return False
  Z.add(x)
  D.append(x)
  return True

dist=[0]*N
def bfs():
  global dist,D,G
  v=0
  for i in range(len(D)):
    v=D.popleft()
    for j in range(len(G[v])):
      if qao(G[v][j][0]):
        dist[G[v][j][0]]=G[v][j][1]+dist[v]
  return len(D)

qao(K-1)
while bfs():
  pass
for i in range(Q):
  a,b=map(int,S[N+1+i].split())
  print(dist[a-1]+dist[b-1])

Solution (Python):
n = int(input())
V = [[] for i in range(n+1)]
for i in range(n-1):
    a,b,c = map(int,input().split())
    V[a].append([b,c])
    V[b].append([a,c])
q,k = map(int,input().split())
from collections import deque
dis = [-1]*(n+1)
Q = deque([])
Q.append(k)
dis[k] = 0
while Q:
    r = Q.popleft()
    for A,D in V[r]:
        if dis[A] == -1:
            Q.append(A)
            dis[A] = dis[r] + D
x = [0]*q
for i in range(q):
    x,y = map(int,input().split())
    print(dis[x]+dis[y])

Solution (Python):
from collections import deque, defaultdict

N = int(input())

e = defaultdict(list)
for i 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())

visits = [False]*(N+1)
costs = defaultdict(int)
q = deque()
q.append((K, 0))
visits[K] = True
while q:
    u, c1 = q.popleft()
    for v, c2 in e[u]:
        if not visits[v]:
            costs[(K, v)] = c1+c2
            visits[v] = True
            q.append((v, c1+c2))

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

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

TO_K = []
TREE = []

def dfs(parent, distance):
    for i_node in TREE[parent]:
        child, dd = i_node
        if TO_K[child] != -1:
            continue

        next_dt = distance + dd
        TO_K[child] = next_dt
        dfs(child, next_dt)

    return


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

    global TO_K
    
    TO_K = [-1]*(n+1)

    global TREE
    
    TREE = [[] for _ in range(n+1)]
    for a, b, c in abc:
        TREE[a].append([b, c])
        TREE[b].append([a, c])

    TO_K[k] = 0
    dfs(k, 0)

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


if __name__ == "__main__":
    main()
    sys.exit(0)