Problem:
 Score : 400 points    Problem Statement You are given a tree with N vertices. Here, a tree is a kind of graph, and more specifically, a connected undirected graph with N-1 edges, where N is the number of its vertices. The i -th edge (1≤i≤N-1) connects Vertices a_i and b_i , and has a length of c_i .  You are also given Q queries and an integer K . In the j -th query (1≤j≤Q) :   find the length of the shortest path from Vertex x_j and Vertex y_j via Vertex K .       Constraints  3≤N≤10^5   1≤a_i,b_i≤N (1≤i≤N-1)   1≤c_i≤10^9 (1≤i≤N-1)   The given graph is a tree.  1≤Q≤10^5   1≤K≤N   1≤x_j,y_j≤N (1≤j≤Q)   x_j≠y_j (1≤j≤Q)   x_j≠K,y_j≠K (1≤j≤Q)          Input Input is given from Standard Input in the following format:  N  a_1  b_1  c_1  :  a_{N-1}  b_{N-1}  c_{N-1}  Q  K  x_1  y_1  :  x_{Q}  y_{Q}       Output Print the responses to the queries in Q lines. In the j -th line j(1≤j≤Q) , print the response to the j -th query.        Sample Input 1 5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5      Sample Output 1 3
2
4  The shortest paths for the three queries are as follows:   Query 1 : Vertex 2 → Vertex 1 → Vertex 2 → Vertex 4 : Length 1+1+1=3   Query 2 : Vertex 2 → Vertex 1 → Vertex 3 : Length 1+1=2   Query 3 : Vertex 4 → Vertex 2 → Vertex 1 → Vertex 3 → Vertex 5 : Length 1+1+1+1=4         Sample Input 2 7
1 2 1
1 3 3
1 4 5
1 5 7
1 6 9
1 7 11
3 2
1 3
4 5
6 7      Sample Output 2 5
14
22  The path for each query must pass Vertex K=2 .       Sample Input 3 10
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
1 1
9 10      Sample Output 3 17000000000

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
n = int(input())
m = {}
np = [deque([]) for _ in range(n)]
for _ in range(n-1):
    a, b, c = [int(x) for x in input().strip().split()]
    m[(a, b)] = c
    m[(b, a)] = c
    np[a-1].append(b)
    np[b-1].append(a)

q, k = [int(x) for x in input().strip().split()]
master = [-1 for _ in range(n)]
master[k-1] = 0

def dfs(cur, pre, master):
    
    for p in np[cur-1]:
        if p == pre:
            continue
        master[p-1] = master[cur-1] + m[(cur, p)]
        dfs(p, cur, master)

dfs(k, -1, master)

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

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

def search_unseen(fr,to,cost):  
  cost_from_k[to] += cost_from_k[fr] + cost
  for n_to,n_cost in es[to]:
    if cost_from_k[n_to] == 0 and k!=n_to:
      search_unseen(to, n_to, n_cost)

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

cost_from_k = [0]*n      
search_unseen(k, k, 0)

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

Solution (Python):
import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, = map(int, input().split())







L = [[int(v) for v in input().split()] for _ in range(N - 1)]
Q, K = map(int, input().split())
QL = [[int(v) for v in input().split()] for _ in range(Q)]

m = {}
l = [set() for _ in range(N)]
for a, b, c in L:
    a -= 1
    b -= 1
    if m.get(a) == None:
        m[a] = {}
    if m.get(b) == None:
        m[b] = {}

    m[a][b] = c
    m[b][a] = c

    l[a].add(b)
    l[b].add(a)

ans = [None] * N
ans[K - 1] = 0
def dfs(now, a):
    for v in l[now]:
        p = a + m[now][v]
        if ans[v] == None:
            ans[v] = p
            dfs(v, ans[v])
        elif ans[v] > p:
            ans[v] = p
            dfs(v, ans[v])

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

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

def dfs(v, d=0):
    seen[v] = True
    dist[v] = d

    for i in graph[v]:
        next_v = i[0]
        l = i[1]
        if seen[next_v] == True:
            continue
        dfs(next_v, d+l)

    return

N = int(input())

graph = [[] for i in range(N + 1)]

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

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

seen = [False for i in range(N + 1)]
dist = [0 for i in range(N + 1)]
dfs(K)

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

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def dfs(N, nodes, src):
    """ DFS(木、スタック、重みあり) """

    stack = [(src, -1, 0)]
    dist = [INF] * N
    while stack:
        u, prev, c1 = stack.pop()
        dist[u] = c1
        for v, c2 in nodes[u]:
            if v != prev:
                stack.append((v, u, c1+c2))
    return dist

N = INT()
nodes = [[] for i in range(N)]
for i in range(N-1):
    a, b, c = MAP()
    a -= 1; b -= 1
    nodes[a].append((b, c))
    nodes[b].append((a, c))

Q, K = MAP()
K -= 1
res = dfs(N, nodes, K)
ans = []
for i in range(Q):
    x, y = MAP()
    x -= 1; y -= 1
    ans.append(str(res[x] + res[y]))
print('\n'.join(ans))

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def dfs(N, nodes, src):
    """ DFS(木、スタック、重みあり) """

    stack = [(src, -1, 0)]
    dist = [INF] * N
    while stack:
        u, prev, c1 = stack.pop()
        dist[u] = c1
        for v, c2 in nodes[u]:
            if v != prev:
                stack.append((v, u, c1+c2))
    return dist

N = INT()
nodes = [[] for i in range(N)]
for i in range(N-1):
    a, b, c = MAP()
    a -= 1; b -= 1
    nodes[a].append((b, c))
    nodes[b].append((a, c))

Q, K = MAP()
K -= 1
res = dfs(N, nodes, K)
for i in range(Q):
    x, y = MAP()
    x -= 1; y -= 1
    ans = res[x] + res[y]
    print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def dfs(N, nodes, src):
    """ DFS(木、スタック、重みあり) """

    stack = [(src, -1, 0)]
    dist = [INF] * N
    while stack:
        u, prev, c1 = stack.pop()
        dist[u] = c1
        for v, c2 in nodes[u]:
            if v != prev:
                stack.append((v, u, c1+c2))
    return dist

N = INT()
nodes = [[] for i in range(N)]
for i in range(N-1):
    a, b, c = MAP()
    a -= 1; b -= 1
    nodes[a].append((b, c))
    nodes[b].append((a, c))

Q, K = MAP()
K -= 1
res = dfs(N, nodes, K)
ans = []
for i in range(Q):
    x, y = MAP()
    x -= 1; y -= 1
    ans.append(str(res[x] + res[y]))
print('\n'.join(ans))

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def dfs(N, nodes, src):
    """ DFS(木、スタック、重みあり) """

    stack = [(src, -1, 0)]
    dist = [INF] * N
    while stack:
        u, prev, c1 = stack.pop()
        dist[u] = c1
        for v, c2 in nodes[u]:
            if v != prev:
                stack.append((v, u, c1+c2))
    return dist

N = INT()
nodes = [[] for i in range(N)]
for i in range(N-1):
    a, b, c = MAP()
    a -= 1; b -= 1
    nodes[a].append((b, c))
    nodes[b].append((a, c))

Q, K = MAP()
K -= 1
res = dfs(N, nodes, K)
for i in range(Q):
    x, y = MAP()
    x -= 1; y -= 1
    ans = res[x] + res[y]
    print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def dijkstra(N: int, nodes: list, src: int) -> list:
    """ ダイクストラ高速化版(頂点数, 隣接リスト(0-indexed), 始点) """
    from heapq import heappush, heappop

    
    res = [INF] * N
    
    que = [src]
    res[src] = 0
    
    while len(que) != 0:
        
        cur = heappop(que)
        
        dist = cur // N
        cur %= N
        
        for nxt, cost in nodes[cur]:
            
            if dist + cost < res[nxt]:
                res[nxt] = dist + cost
                
                heappush(que, (dist+cost)*N+nxt)
    
    return res

N = INT()
nodes = [[] for i in range(N)]
for i in range(N-1):
    a, b, c = MAP()
    a -= 1; b -= 1
    nodes[a].append((b, c))
    nodes[b].append((a, c))

Q, K = MAP()
K -= 1
res = dijkstra(N, nodes, K)
for i in range(Q):
    x, y = MAP()
    x -= 1; y -= 1
    ans = res[x] + res[y]
    print(ans)

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

graph = [[] for _ in range(N + 1)]
for A, B, C in ABC:
  graph[A].append((B, C))
  graph[B].append((A, C))


INF = 10 ** 15
stack = [K]
depth = [INF] * (N + 1)
depth[K] = 0

while stack:
  a = stack.pop()
  for b, d in graph[a]:
    if depth[b] > depth[a] + d:
      depth[b] = depth[a] + d
      stack.append(b)


for X, Y in XY:
  print(depth[X] + depth[Y])

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def main():
	N = INT()
	G = [[] for _ in range(N)]
	for _ in range(N-1):
		a, b, c = MAP()
		a -= 1
		b -= 1
		G[a].append([b, c])
		G[b].append([a, c])
	
	Q, K = MAP()
	queue = deque()
	queue.append(K-1)
	dist = [-1] * N
	dist[K-1] = 0
	while queue:
		v = queue.popleft()
		for nv in G[v]:
			edge, distance = nv
			if dist[edge] != -1: continue
			dist[edge] = dist[v] + distance
			queue.append(edge)
	
	
	for _ in range(Q):
		a, b = MAP()
		print(dist[a-1]+dist[b-1])

if __name__ == '__main__':
	main()

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

cnt, K = map(int, input().split())
K -= 1
Q = deque([(K, 0)])
Dist = [0]*N
check = [0]*N
while Q:
    n, d = Q.popleft()
    check[n] = 1
    Dist[n] = d
    for v, e in D[n]:
        if check[v]:
            continue
        else:
            Q.append((v, d+e))

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

Solution (Python):
import sys

n = int(sys.stdin.readline().rstrip())
g = [[] for _ in range(n+1)]
for _ in range(n-1):
    a, b, c = map(int, sys.stdin.readline().split())
    g[a].append((b, c))
    g[b].append((a, c))

q, k = map(int, sys.stdin.readline().split())
xy = zip(*[map(int, sys.stdin.read().split())] * 2)

def dfs(v):
    dist = [None] * (n + 1)
    stack = [(v, 0)]
    while stack:
        x, d = stack.pop()
        dist[x] = d
        for y, dd in g[x]:
            if dist[y] is None:
                stack.append((y, d + dd))
    return dist

def main():
    dist_k = dfs(k)
    
    for x, y in xy:
        yield dist_k[x] + dist_k[y]

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

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
ab = [list(map(int, input().split(' '))) for i in range(n-1)]
graph = [[] for i in range(n+1)]
parent = [0 for i in range(n+1)]
Q,K = map(int, input().split(' '))
root = K
d = 0
stack = [root]
order = []
for a,b,e in ab:
    graph[a].append(b)
    graph[b].append(a)
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if parent[x] == y:
            continue
        parent[y] = x
        stack.append(y)
dist = [0 for i in range(n+1)]
for a,b,e in ab:
    if parent[a] == b:
        dist[a] = e
    else:
        dist[b] = e
visited = [0 for i in range(n+1)]
visited[root] = 1
ans = [0 for i in range(n+1)]
for i in order:
    if i == root:
        continue
    ans[i] += dist[i]
    if visited[parent[i]] == 1:
        ans[i] += ans[parent[i]]
        visited[i] = 1
for i in range(Q):
    s,t = map(int, input().split(' '))
    print(ans[s]+ans[t])

Solution (Python):
from collections import deque


def main():
    n = int(input())
    tree = AdjacentListGraph([Vertex() for _ in range(n)])
    for _ in range(n - 1):
        a, b, c = map(int, input().split())
        tree.add_edge(a - 1, b - 1, c)
        tree.add_edge(b - 1, a - 1, c)
    q, k = map(int, input().split())
    distances = distances_from(tree, k - 1)
    
    answers = []
    for _ in range(q):
        x, y = map(int, input().split())
        answers.append(distances[x - 1] + distances[y - 1])
    print("\n".join(map(str, answers)))


def distances_from(
    graph: "Graph", from_: int, break_if=lambda node: False
) -> "List[int]":
    distances = [None for _ in range(graph.size)]
    distances[from_] = 0
    queue = deque([from_])
    while queue:
        node = queue.popleft()
        if break_if(node):
            break
        curDist = distances[node]
        for edge in graph.edges_from(node):
            if distances[edge.to] is not None:
                continue
            delta = edge.weight if edge.weight else 0
            distances[edge.to] = curDist + delta
            queue.append(edge.to)
    return distances


class Vertex:
    def __init__(self, data=None):
        self.data = data
        self.edges = []

    def add_edge(self, to, weight=None):
        self.edges.append(Edge(to, weight))

    def remove_edge(self, to: int) -> bool:
        for i, edge in enumerate(self.edges):
            if edge.to == to:
                del self.edges[i]
                return True
        return False


class Edge:
    def __init__(self, to, weight=None):
        self.to = to
        self.weight = weight


class AdjacentListGraph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.size = len(vertices)

    def get_weight(self, from_: int, to: int):
        for edge in self.vertices[from_].edges:
            if edge.to == to:
                return edge.weight
        return None

    def edges_from(self, from_: int):
        return self.vertices[from_].edges

    def add_edge(self, from_: int, to: int, weight=None) -> bool:
        return self.vertices[from_].add_edge(to, weight)

    def remove_edge(self, from_: int, to: int) -> bool:
        return self.vertices[from_].remove_edge(to)

    def is_adjacent(self, from_: int, to: int) -> bool:
        return to in {edge.to for edge in self.edges_from(from_)}


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque


def main():
    n = int(input())
    tree = AdjacentListGraph([Vertex() for _ in range(n)])
    for _ in range(n - 1):
        a, b, c = map(int, input().split())
        tree.add_edge(a - 1, b - 1, c)
        tree.add_edge(b - 1, a - 1, c)
    q, k = map(int, input().split())
    distances = distances_from(tree, k - 1)
    
    answers = []
    for _ in range(q):
        x, y = map(int, input().split())
        answers.append(distances[x - 1] + distances[y - 1])
    print("\n".join(map(str, answers)))


def distances_from(
    graph: "Graph", from_: int, break_if=lambda node: False
) -> "List[int]":
    distances = [None for _ in range(graph.size)]
    distances[from_] = 0
    queue = deque([from_])
    while queue:
        node = queue.popleft()
        if break_if(node):
            break
        curDist = distances[node]
        for edge in graph.edges_from(node):
            if distances[edge.to] is not None:
                continue
            delta = edge.weight if edge.weight else 0
            distances[edge.to] = curDist + delta
            queue.append(edge.to)
    return distances


class Vertex:
    __slots__ = ("data", "edges")

    def __init__(self, data=None):
        self.data = data
        self.edges = set()

    def add_edge(self, to, weight=None):
        self.edges.add(Edge(to, weight))

    def remove_edge(self, to: int) -> bool:
        for i, edge in enumerate(self.edges):
            if edge.to == to:
                del self.edges[i]
                return True
        return False


class Edge:
    __slots__ = ("to", "weight")

    def __init__(self, to, weight=None):
        self.to = to
        self.weight = weight

    def __hash__(self) -> int:
        return hash(self.to)

class AdjacentListGraph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.size = len(vertices)

    def get_weight(self, from_: int, to: int):
        for edge in self.vertices[from_].edges:
            if edge.to == to:
                return edge.weight
        return None

    def edges_from(self, from_: int):
        return self.vertices[from_].edges

    def add_edge(self, from_: int, to: int, weight=None) -> bool:
        return self.vertices[from_].add_edge(to, weight)

    def remove_edge(self, from_: int, to: int) -> bool:
        return self.vertices[from_].remove_edge(to)

    def is_adjacent(self, from_: int, to: int) -> bool:
        return to in {edge.to for edge in self.edges_from(from_)}


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque


def main():
    n = int(input())
    tree = AdjacentListGraph([Vertex() for _ in range(n)])
    for _ in range(n - 1):
        a, b, c = map(int, input().split())
        tree.add_edge(a - 1, b - 1, c)
        tree.add_edge(b - 1, a - 1, c)
    q, k = map(int, input().split())
    distances = distances_from(tree, k - 1)
    
    answers = []
    for _ in range(q):
        x, y = map(int, input().split())
        answers.append(distances[x - 1] + distances[y - 1])
    print("\n".join(map(str, answers)))


def distances_from(
    graph: "Graph", from_: int, break_if=lambda node: False
) -> "List[int]":
    distances = [None for _ in range(graph.size)]
    distances[from_] = 0
    queue = deque([from_])
    while queue:
        node = queue.popleft()
        if break_if(node):
            break
        curDist = distances[node]
        for edge in graph.edges_from(node):
            if distances[edge.to] is not None:
                continue
            delta = edge.weight if edge.weight else 0
            distances[edge.to] = curDist + delta
            queue.append(edge.to)
    return distances


class Vertex:
    __slots__ = ("data", "edges")

    def __init__(self, data=None):
        self.data = data
        self.edges = []

    def add_edge(self, to, weight=None):
        self.edges.append(Edge(to, weight))

    def remove_edge(self, to: int) -> bool:
        for i, edge in enumerate(self.edges):
            if edge.to == to:
                del self.edges[i]
                return True
        return False


class Edge:
    __slots__ = ("to", "weight")

    def __init__(self, to, weight=None):
        self.to = to
        self.weight = weight


class AdjacentListGraph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.size = len(vertices)

    def get_weight(self, from_: int, to: int):
        for edge in self.vertices[from_].edges:
            if edge.to == to:
                return edge.weight
        return None

    def edges_from(self, from_: int):
        return self.vertices[from_].edges

    def add_edge(self, from_: int, to: int, weight=None) -> bool:
        return self.vertices[from_].add_edge(to, weight)

    def remove_edge(self, from_: int, to: int) -> bool:
        return self.vertices[from_].remove_edge(to)

    def is_adjacent(self, from_: int, to: int) -> bool:
        return to in {edge.to for edge in self.edges_from(from_)}


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque


def main():
    n = int(input())
    tree = AdjacentListGraph([Vertex() for _ in range(n)])
    for _ in range(n - 1):
        a, b, c = map(int, input().split())
        tree.add_edge(a - 1, b - 1, c)
        tree.add_edge(b - 1, a - 1, c)
    q, k = map(int, input().split())
    distances = distances_from(tree, k - 1)
    
    answers = []
    for _ in range(q):
        x, y = map(int, input().split())
        answers.append(distances[x - 1] + distances[y - 1])
    print("\n".join(map(str, answers)))


def distances_from(
    graph: "Graph", from_: int, break_if=lambda node: False
) -> "List[int]":
    distances = [None for _ in range(graph.size)]
    distances[from_] = 0
    queue = deque([from_])
    while queue:
        node = queue.popleft()
        if break_if(node):
            break
        curDist = distances[node]
        for edge in graph.edges_from(node):
            if distances[edge.to] is not None:
                continue
            delta = edge.weight if edge.weight else 0
            distances[edge.to] = curDist + delta
            queue.append(edge.to)
    return distances


class Vertex:
    __slots__ = ("data", "edges")

    def __init__(self, data=None):
        self.data = data
        self.edges = []

    def add_edge(self, to, weight=None):
        self.edges.append(Edge(to, weight))

    def remove_edge(self, to: int) -> bool:
        for i, edge in enumerate(self.edges):
            if edge.to == to:
                del self.edges[i]
                return True
        return False


class Edge:
    __slots__ = ("to", "weight")

    def __init__(self, to, weight=None):
        self.to = to
        self.weight = weight


class AdjacentListGraph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.size = len(vertices)

    def get_weight(self, from_: int, to: int):
        for edge in self.vertices[from_].edges:
            if edge.to == to:
                return edge.weight
        return None

    def edges_from(self, from_: int):
        return self.vertices[from_].edges

    def add_edge(self, from_: int, to: int, weight=None) -> bool:
        return self.vertices[from_].add_edge(to, weight)

    def remove_edge(self, from_: int, to: int) -> bool:
        return self.vertices[from_].remove_edge(to)

    def is_adjacent(self, from_: int, to: int) -> bool:
        return to in {edge.to for edge in self.edges_from(from_)}


if __name__ == "__main__":
    main()

Solution (Python):
import collections
N=int(input())
Branch=[[] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  Branch[a-1].append([b-1,c])
  Branch[b-1].append([a-1,c])
Q,K=map(int,input().split())
Dist=[float("Inf") for i in range(N)]
flag = [0 for i in range(N)]

que=collections.deque()
que.append(K-1)
Dist[K-1]=0
while len(que):
  u=que.pop()
  for i,j in Branch[u]:
    if Dist[i]==float("Inf"):
      Dist[i]=Dist[u]+j
      que.append(i)

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

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(1000000)
N = int(input())
graph = [[] for _ in range(N+1)]
for i in range(1, N):
    tmpa, tmpb, tmpc = map(int, input().split())
    graph[tmpa].append((tmpb, tmpc))
    graph[tmpb].append((tmpa, tmpc))

Q, K = map(int, input().split())
question = [[] for _ in range(Q+1)]
for i in range(1, Q+1):
    question[i] = list(map(int, input().split()))



seen = [False] * (N+1)
dist = [0] * (N+1)

def dfs(here, seen, kyori):
    seen[here] = True
    dist[here] = kyori
    
    for node in graph[here]:
        nextkyori = kyori
        if not seen[node[0]]:
            nextkyori += node[1]
            dfs(node[0], seen, nextkyori)

dfs(K, seen, 0)
for quest in question[1:]:
    print(dist[quest[0]] + dist[quest[1]])

Solution (Python):
N = int(input())
tl = [[] for _ in range(N+1)]
d = {}
for _ in range(N-1):
    a, b, c = map(int, input().split())
    tl[a].append(b)
    tl[b].append(a)
    d[(a, b)] = c
    d[(b, a)] = c
Q, K = map(int, input().split())
seen = [False]*(N+1)
stack = [K]
seen[K] = True
while len(stack):
    n = stack.pop()
    for v in tl[n]:
        if not seen[v]:
            stack.append(v)
            seen[v] = True
            if n != K:
                d[(K, v)] = d[(K, n)]+d[(n, v)]
for _ in range(Q):
    x, y = map(int, input().split())
    print(d[(K, x)]+d[(K, y)])

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

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

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

S, D = [(K - 1, K - 1)], [0] * N
while len(S) > 0:
    p, pp = S.pop()
    for c, d in neig[p]:
        if not c == pp:
            D[c] = D[p] + d
            S.append((c, p))

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

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

n = int(input())

from collections import defaultdict
d = defaultdict(list)

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

global dist
dist = [-1 for _ in range(n)]
def dfs(l, pos):
    dist[pos] = l
    for to, c in d[pos]:
        if dist[to] == -1:
            dfs(l+c,to)

dfs(0, 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

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

Q,K=map(int,input().split())
d=[-1 for i in range(N+1)]
q=deque()
q.append(K);d[K]=0
while q:
    u=q.popleft()
    for v,c in adj[u]:
        if d[v]==-1:
            d[v]=d[u]+c
            q.append(v)

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

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
g = [[] for i in range(n)]
cc = dict()
for i in range(n-1):
    a,b,c = inpl()
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
    cc[(a,b)] = c
    cc[(b,a)] = c
q,k = inpl()
k -= 1
cost = [INF] * n
cost[k] = 0
def dfs(node,c):
    for next in g[node]:
        if cost[next] == INF:
            cost[next] = c + cc[(node,next)]
            dfs(next,cost[next])

dfs(k,0)
res = [0] * q
for i in range(q):
    x,y = inpl()
    x -= 1
    y -= 1
    res[i] = cost[x] + cost[y]
for z in res:
    print(z)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
g = [[] for i in range(n)]
cc = dict()
for i in range(n-1):
    a,b,c = inpl()
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
    cc[(a,b)] = c
    cc[(b,a)] = c
q,k = inpl()
k -= 1
cost = [INF] * n
cost[k] = 0
def dfs(node,c):
    for next in g[node]:
        if cost[next] == INF:
            cost[next] = c + cc[(node,next)]
            dfs(next,cost[next])

dfs(k,0)
res = [0] * q
for i in range(q):
    x,y = inpl()
    x -= 1
    y -= 1
    res[i] = cost[x] + cost[y]
for z in res:
    print(z)

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

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

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

queue = [K-1]
dist = [None]*N
dist[K-1] = 0
while queue:
  queue_new = []
  for q in queue:
    for e in E[q]:
      if dist[e[0]] is not None: continue
      dist[e[0]] = dist[q] + e[1]
      queue_new.append(e[0])
  queue = queue_new

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