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

def dijkstra(graph: 'List[List[int]]', s: int):
    """
    特定の始点から各点への最短距離を求めます。
    重みが非負であることを前提とします。
    ================
    s: 始点
    graph: 隣接リスト
    ----------------
    d: sから各頂点への最短距離
    counter: sから各頂点への最短経路の個数
    """
    import heapq
    INF = 1e18
    d = [INF] * len(graph)
    d[s]  = 0
    counter = [0] * len(graph)
    counter[s] = 1

    q = []
    heapq.heappush(q, (0, s))
    while q:
        (dd, vv) = heapq.heappop(q)
        if d[vv] < dd:
            continue
        for (to, cost) in graph[vv]:
            if d[to] > (d[vv] + cost):
                d[to] = d[vv] + cost
                counter[to] = counter[vv]
                heapq.heappush(q, (d[to], to))
            elif d[to] == (d[vv] + cost):
                counter[to] += counter[vv]
    return d, counter


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]", Q: int, K: int, x: "List[int]", y: "List[int]"):
    G = [[] for _ in range(N)]
    for i in range(N-1):
        G[a[i]-1].append((b[i]-1, c[i]))
        G[b[i]-1].append((a[i]-1, c[i]))
    dist, _ = dijkstra(G, K-1)

    for i in range(Q):
        print(dist[x[i]-1] + dist[y[i]-1])

    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())
A = [list(map(int,input().split())) for i in range(n-1)]
q, k = map(int,input().split())
X = [list(map(int,input().split())) for i in range(q)]

M = [[] for i in range(n+1)]
V = [0] * (n+1)
D = [0] * (n+1)

for i in range(n-1):
    M[A[i][0]].append([A[i][1], A[i][2]])
    M[A[i][1]].append([A[i][0], A[i][2]])



def d(x, dist):
    V[x] = 1
    D[x] = dist
    
    for i in range(len(M[x])):
        
        if V[M[x][i][0]] == 0:
            
            Q.append([M[x][i][0], dist+M[x][i][1]])

Q = [[k, 0]]

st = 0
while st < len(Q):
    
    d(Q[st][0], Q[st][1])
    st += 1

for i in range(q):
    print(D[X[i][0]] + D[X[i][1]])

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
Tree=[[] for _ in range(n)]
for _ 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=[float('inf')]*n
dist[k-1]=0
stack=[k-1]

while stack!=[]:
    p=stack.pop()
    for q in Tree[p]:
        qp,ql=q[0],q[1]
        if dist[qp]==float('inf'):
            dist[qp]=dist[p]+ql
            stack.append(qp)

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

Solution (Python):
from collections import defaultdict, deque
inf = float('inf')

def solve(graph, n, start_node, end_node):
  if start_node == end_node:
    return 0

  global costs_dict
  key = str(start_node) + '-' + str(end_node)
  if key in costs_dict:
    return costs_dict[key][end_node]

  costs = [inf for _ in range(n)]
  costs[start_node] = 0
  flgs = [False for _ in range(n)]

  while not all(flgs):
    prv_node = _get_min_idx(flgs,costs)
    flgs[prv_node] = True

    for node, dis in graph[prv_node]:
      if costs[node] > costs[prv_node] + dis:
        costs[node] = costs[prv_node] + dis
  costs_dict[key] = costs  
  return costs[end_node]
    
    
def _get_min_idx(flgs, costs):
    min_cost = inf
    min_idx = None
    cnt = 0
    for cost, flg in zip(costs, flgs):
      if min_cost > cost and flg is False:
        min_cost = cost
        min_idx = cnt
      cnt += 1
    return min_idx
        

n =int(input())
graph = defaultdict(list)
costs_dict = {}

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

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

l = [0 for _ in range(n)]
queue = deque()
queue.append(k)
while len(queue) > 0:
  a = queue.pop()
  for b, c in graph[a]:
    if l[b] == 0:
      l[b] = l[a] + c
      queue.append(b)

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

Solution (Python):
from collections import defaultdict, deque
from heapq import heappush, heappop, heapify
import math
import bisect
import random
import sys


def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
mod = 1000000007


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



q, k = LI()
q_ab = LIRM(q)



dist = n * [-1]
dist[k-1] = 0
que = deque([k-1])
while que:
    cur = que.pop()
    for nxt, c in graph[cur]:
        if dist[nxt] == -1:
            dist[nxt] = dist[cur] + c
            que += [nxt]



for a, b in q_ab:
    print(dist[a] + dist[b])

Solution (Python):
from collections import defaultdict as dd
from collections import deque
N = int(input())
D =dd(list)
for i 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())
K -= 1
L = [0 for _ in range(N)]
q = deque([])
q.append(K)
while len(q) > 0:
  a = q.pop()
  for b, c in D[a]:
    if L[b] == 0:
      L[b] = L[a] + c
      q.append(b)

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

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")


def A():
    n = S()
    n1 = n[::-1]
    for i in range(len(n)):
        if n1[i] != n[i]:
            print("No")
            return
    print("Yes")
    return


def B():
    a, b, c, d = LI()
    ans = [0 for i in range(101)]
    ans[a] += 1
    ans[b] -= 1
    ans[c] += 1
    ans[d] -= 1
    for i in range(100):
        ans[i+1] += ans[i]
    print(ans.count(2))

def C():
    n = II()
    ans = 1
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    for _ in range(n):
        t = II()
        ans = ans // gcd(ans, t) * t
    print(ans)
    return


def D():
    n = II()
    vedg = defaultdict(list)
    for _ in range(n-1):
        a, b, c = LI()
        vedg[a].append((b, c))
        vedg[b].append((a, c))
    dist = defaultdict(lambda :inf)
    Q, k = LI()
    q = deque([k])
    dist[k] = 0
    while q:
        f = q.pop()
        for t, value in vedg[f]:
            if dist[t] > dist[f] + value:
                dist[t] = dist[f] + value
                q.append(t)
    for _ in range(Q):
        x, y = LI()
        print(dist[x] + dist[y])
    return


if __name__ == '__main__':
    D()

Solution (Python):
from collections import defaultdict as dd
from collections import deque
N = int(input())
D =dd(list)
for i 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())
K -= 1
L = [0 for _ in range(N)]
q = deque([])
q.append(K)
while len(q) > 0:
  a = q.pop()
  for b, c in D[a]:
    if L[b] == 0:
      L[b] = L[a] + c
      q.append(b)

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

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

n=int(input())
l=[list(map(int,input().split())) for _ in [0]*(n-1)]
q,k=map(int,input().split())
L=[list(map(int,input().split())) for _ in [0]*q]

neighbor=[[] for _ in range(n+1)]
for i in range(n-1):
    neighbor[l[i][0]].append([l[i][1],l[i][2]])
    neighbor[l[i][1]].append([l[i][0],l[i][2]])

cost=[-1]*(n+1)
cost[k]=0
c=0

def sol(i,p,d):
    global cost
    cost[i]=d
    for x in neighbor[i]:
        if x[0]!=p:
            sol(x[0],i,d+x[1])
sol(k,-1,0)

for i in range(q):
    print(cost[L[i][0]]+cost[L[i][1]])

Solution (Python):
N = int(input())
E = [[] for i in range(N)]
for i in range(N-1):
  a, b, c = map(int, input().split())
  a, b = a-1, b-1
  E[a].append((b, c))
  E[b].append((a, c))
Q, K = map(int, input().split())
K = K-1
D = [-1]*N
D[K] = 0
q = [(K, 0)]
while q:
  k, d = q.pop()
  for n, c in E[k]:
    if D[n] < 0:
      D[n] = d+c
      q.append((n, d+c))

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

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
abc = [list(map(int,input().split())) for _ in range(n-1)]
q,k = map(int,input().split())
query = [list(map(int,input().split())) for _ in range(q)]

point = [[] for _ in range(n+1)]
for l in abc:
  point[l[0]].append([l[1],l[2]])
  point[l[1]].append([l[0],l[2]])

done = set()
done.add(k)
d = [0]*(n+1)
lst = [k]

while lst:
  start = lst.pop()
  for l in point[start]:
    if l[0] not in done:
      d[l[0]] = d[start] + l[1]
      done.add(l[0])
      lst.append(l[0])

for l in query:
  print(d[l[0]]+d[l[1]])

Solution (Python):
from collections import deque

N = int(input())
to = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    to[a - 1].append((b - 1, c))
    to[b - 1].append((a - 1, c))
Q, K = map(int, input().split())
XY = []
for _ in range(Q):
    x, y = map(int, input().split())
    XY.append((x - 1, y - 1))

ds = [0] * N
q = deque()
q.append((K - 1, 0, -1))
while len(q):
    a, d, par = q.pop()
    ds[a] = d
    for b, c in to[a]:
        if b != par:
            q.append((b, d + c, a))

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

Solution (Python):

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def dfs(v: int, d) -> None:
    dist[v] = d
    for u, c in G[v]:  
        if dist[u] is None:
            dfs(u, d + c)


def main():
    global G, dist
    N = int(input())
    E = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    Q, K = tuple(map(int, input().split()))
    X = tuple(tuple(map(int, input().split())) for _ in range(Q))
    G = [[] for _ in range(N + 1)]  
    for v, u, c in E:  
        G[v] += [(u, c)]
        G[u] += [(v, c)]
    dist = [None] * (N + 1)  
    dist[K] = 0
    dfs(K, 0)
    ans = [dist[x] + dist[y] for x, y in X]
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Solution (Python):

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def dfs(v: int, p: int) -> None:
    d = dist[v]
    for u, c in G[v]:  
        if u != p:  
            dist[u] += d + c  
            dfs(u, v)


def main():
    global G, dist
    N = int(input())
    E = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    Q, K = tuple(map(int, input().split()))
    X = tuple(tuple(map(int, input().split())) for _ in range(Q))
    G = [[] for _ in range(N + 1)]  
    for v, u, c in E:  
        G[v] += [(u, c)]
        G[u] += [(v, c)]
    dist = [0] * (N + 1)  
    dfs(K, -1)
    ans = [dist[x] + dist[y] for x, y in X]
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Solution (Python):

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def dfs(v: int, p: int, G: "List[List[int]]", dist: "List[int]") -> None:
    d = dist[v]
    for u, c in G[v]:  
        if u != p:  
            dist[u] += d + c  
            dfs(u, v, G, dist)


def main():
    global G, dist
    N = int(input())
    E = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    Q, K = tuple(map(int, input().split()))
    X = tuple(tuple(map(int, input().split())) for _ in range(Q))
    G = [[] for _ in range(N + 1)]  
    for v, u, c in E:  
        G[v] += [(u, c)]
        G[u] += [(v, c)]
    dist = [0] * (N + 1)  
    dfs(K, -1, G, dist)
    ans = [dist[x] + dist[y] for x, y in X]
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Solution (Python):

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

def dfs(v: int, p: int) -> None:
    d = dist[v]
    for u, c in G[v]:  
        if u != p:  
            dist[u] += d + c  
            dfs(u, v)


def main():
    global G, dist
    N = int(input())
    E = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    Q, K = tuple(map(int, input().split()))
    X = tuple(tuple(map(int, input().split())) for _ in range(Q))
    G = [[] for _ in range(N + 1)]  
    for v, u, c in E:  
        G[v] += [(u, c)]
        G[u] += [(v, c)]
    dist = [0] * (N + 1)  
    dfs(K, -1)
    ans = [dist[x] + dist[y] for x, y in X]
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

class Heapq:
    def __init__(self, que=[], asc=True):
        if not asc:
            que = [-a for a in que]
        self.__que = que
        heapq.heapify(self.__que)
        self.__sign = 1 if asc else -1

    def pop(self):
        return heapq.heappop(self.__que) * self.__sign

    def push(self, value):
        heapq.heappush(self.__que, value * self.__sign)

    def pushpop(self, value):
        return heapq.heappushpop(self.__que, value * self.__sign) * self.__sign

    def top(self):
        return self.__que[0] * self.__sign

    def size(self):
        return len(self.__que)


def sol():
    N = int(input())
    edges = [[] for _ in range(N)]

    for _ in range(N - 1):
        fr, to, cost = map(int, input().split())
        fr -= 1
        to -= 1
        edges[fr].append((to, cost))
        edges[to].append((fr, cost))

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

    minDist = [float('inf')] * N
    que = Heapq([])
    que.push((0, K))

    while que.size():
        dist, now = que.pop()

        if minDist[now] < dist:
            continue
        minDist[now] = dist

        for to, cost in edges[now]:
            if minDist[to] > dist + cost:
                que.push((dist + cost, to))

    for _ in range(Q):
        fr, to = map(int, input().split())
        print(minDist[fr - 1] + minDist[to - 1])


sol()

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

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

visited = [-1] * N
def bfs(a, dist) :
    for b, c in v[a] :
        if visited[b] < 0 :
            visited[b] = dist + c
            bfs(b, dist + c)
          
Q, K = map(int, input().split())
visited[K-1] = 0
bfs(K-1, 0)
for _ in range(Q) :
    x, y = map(int, input().split())
    print(visited[x-1] + visited[y-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

import collections

def first_search(graph, root, depth_array):
    seen, queue = set([root]), collections.deque([[root, 0],])
    while queue:
        vertex, depth = queue.popleft()  
        depth_array[vertex] = depth
        for node, length in graph[vertex]:
            if node not in seen:
                seen.add(node)
                queue.append([node, depth+length])

def main(): 
    N = II()

    from collections import defaultdict
    tree = defaultdict(list)

    for _ in range(N-1):
        a,b,c = LI()
        tree[a].append((b,c))
        tree[b].append((a,c))

    Q, K = LI()

    depth_array = [0 for _ in range(N+1)]
    
    first_search(tree, K, depth_array)


    for _ in range(Q):
        x,y = LI()
        print(depth_array[x]+depth_array[y])


main()

Solution (Python):
import heapq

INF = float("inf")

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

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



D = [INF,] * (N+1)
visited = [0,] * (N+1)

D[K] = 0
visited[K] = 1
qE = []

for e in E[K]:
	heapq.heappush(qE, e)

while qE:
	
	c, b = heapq.heappop(qE)
	if visited[b]:
		continue
	D[b] = c
	visited[b] = 1

	
	for nc, nb in E[b]:
		if not visited[nb]:
			heapq.heappush(qE, (D[b]+nc, nb))

for x, y in W:
	print(D[x]+D[y])

Solution (Python):
from heapq import heappush, heappop
from collections import defaultdict
N = int(input())
E = defaultdict(list)
for i 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())


d = [float("inf")] * N
d[K - 1] = 0
q = []
heappush(q, (K - 1, 0))
while q:
    now, dist = heappop(q)
    if d[now] < dist:
        continue

    for nxt, w in E[now]:
        t = dist + w
        if t < d[nxt]:
            d[nxt] = t
            heappush(q, (nxt, t))
for _ in range(Q):
    t1, t2 = map(int, input().split())
    print(d[t1 - 1] + d[t2 - 1])

Solution (Python):
"""
最小共通祖先(LCA, lowest common ancestor)を求める
"""
class LCA_doubling:
    """
    parent: ダブリングテーブル
    depth: 元の深さ
    """
    def __init__(self,g,root): 
        def dfs(v,p): 
            if p != -1: self.depth[v] = self.depth[p]+1
            for c,d in g[v]:
                if c == p: continue
                self.parent[0][c] = v
                self.dist[0][c] = d
                dfs(c,v)

        def doubling_make_table(N,logN,Table,Dist):
            for i in range(1,logN):
                for j, Tiij in enumerate(Table[i-1]):
                    if Tiij != -1:
                        Table[i][j] = Table[i-1][Tiij]
                        Dist[i][j] = Dist[i-1][j] + Dist[i-1][Tiij]

        N = len(g)
        self.logN = len(bin(N))-2
        self.parent = [[-1]*N for _ in range(self.logN)]
        self.dist   = [[0]*N for _ in range(self.logN)]
        self.depth = [0]*(N) 
        dfs(root,-1) 
        doubling_make_table(N, self.logN, self.parent, self.dist) 


    def getLCA(self,u,v): 
        if self.depth[u] > self.depth[v]: u,v = v,u 
        d = 0
        dd = self.depth[v] - self.depth[u]
        for k in range(self.logN-1,-1,-1):
            if (dd >> k) & 1:
                d += self.dist[k][v]
                v = self.parent[k][v]
        if u == v: return u, d;
        for k in range(self.logN-1,-1,-1):
            if self.parent[k][u] != self.parent[k][v]:
                d += self.dist[k][u]
                d += self.dist[k][v]
                u,v = self.parent[k][u], self.parent[k][v]
        return self.parent[0][u], d+self.dist[0][u]+self.dist[0][v];

    def getdepth(self,u): 
        return self.depth[u]



import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

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

LCA = LCA_doubling(g, root=0)




"""
ABC070D

"""
q,k = [int(i) for i in readline().split()]
k -= 1
for _ in range(q):
    a,b = [int(i)-1 for i in readline().split()]
    
    u1,d1 = LCA.getLCA(a,k)
    u2,d2 = LCA.getLCA(b,k)
    print(d1+d2)

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

G = [[] * N for _ in range(N)]
for _ 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())

D = [-1] * N
s = [(K - 1, 0)]
while s:
  v, c = s.pop()
  D[v] = c
  for vv, cc in G[v]:
    if D[vv] < 0:
      s.append((vv, cc + c))

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

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

N = int(input())

G = [[] * N for _ in range(N)]
for _ 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())

D = [-1] * N
s = [(K - 1, 0)]
while s:
  v, c = s.pop()
  D[v] = c
  for vv, cc in G[v]:
    if D[vv] < 0:
      s.append((vv, cc + c))

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

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

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

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

D = [-1] * N
s = [(K - 1, 0)]
while s:
  v, c = s.pop()
  D[v] = c
  for vv, cc in G[v]:
    if D[vv] < 0:
      s.append((vv, cc + c))
  
for x, y in XY:
  print(D[x - 1] + D[y - 1])

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

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

D = [-1] * N
s = [(K - 1, 0)]
while s:
  v, c = s.pop()
  D[v] = c
  for vv, cc in G[v]:
    if D[vv] < 0:
      s.append((vv, cc + c))
  
for x, y in XY:
  print(D[x - 1] + D[y - 1])

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

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

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

D = [-1] * N

def dfs(v, d):
  D[v] = d
  for i, c in G[v]:
    if D[i] < 0:
      dfs(i, d + c)

dfs(K - 1, 0)

for x, y in XY:
  print(D[x - 1] + D[y - 1])

Solution (Python):
from collections import deque

N = int(input())
G = [[] * N for _ in range(N)]
for _ 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())

D = [-1] * N
D[K - 1] = 0

q = deque([K - 1])
while q:
  n = q.popleft()
  for i, c in G[n]:
    if D[i] < 0:
      q.append(i)
      D[i] = D[n] + c

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

Solution (Python):
from collections import deque

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

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

D = [-1] * N
D[K - 1] = 0

q = deque()
q.append(K - 1)
while q:
  n = q.popleft()
  for i, c in G[n]:
    if D[i] < 0:
      q.append(i)
      D[i] = D[n] + c

for x, y in XY:
  print(D[x - 1] + D[y - 1])

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

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

visited = [0] * n
d = [0] * n
def dfs(v, c):
    for u, c2 in edges[v]:
        if visited[u] == 0:
            d[u] = c + c2
            visited[u] = 1
            dfs(u, c + c2)

visited[k] = 1
dfs(k, 0)

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

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

from collections import deque

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, a, c])
    graph[b].append([a, b, c])
distance = [-1] * (N + 1)

Q, K = map(int, input().split())
distance = [-1] * (N + 1)
distance[K] = 0
que = deque()
q_append = que.append
for i in graph[K]:
    q_append(i)

q_left = que.popleft
while len(que) != 0:
    for _ in range(len(que)):
        abc = q_left()
        if distance[abc[0]] == -1: 
            distance[abc[0]] = distance[abc[1]] + abc[2]
            for j in graph[abc[0]]:
                q_append(j)


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

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

from collections import deque

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, a, c])
    graph[b].append([a, b, c])
distance = [-1] * (N + 1)

Q, K = map(int, input().split())
distance = [-1] * (N + 1)
distance[K] = 0
que = deque()
for i in graph[K]:
    que.append(i)

while len(que) != 0:
    for _ in range(len(que)):
        abc = que.popleft()
        if distance[abc[0]] == -1: 
            distance[abc[0]] = distance[abc[1]] + abc[2]
            for j in graph[abc[0]]:
                que.append(j)


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

Solution (Python):

import sys
import math
from collections import defaultdict
from collections import deque
sys.setrecursionlimit(10**6)
INF = float("inf")


class Graph(object):
    """グラフを扱うオブジェクト
    """

    def __init__(self, N):
        self.N = N
        self.edges = defaultdict(list)
        pass

    def add_edges(self, from_, to_, weight):
        """必ず0インデックスで入力すること。
        """
        self.edges[from_].append([to_, weight])
        self.edges[to_].append([from_, weight])
        pass


def LCA_constract(g: Graph, root=0):
    """
    木gにおいて、頂点u, vのLCA(Lowest Common Ancestor)を求める
    g: 木。無向グラフとして与える。
    u, v:頂点
    root: 根
    元: https://tjkendev.github.io/procon-library/python/graph/lca-doubling.html
    """
    N = g.N
    LN = int(math.log2(g.N))

    
    
    
    par = [INF]*N
    depth = [INF]*N

    que = deque()
    que.append([root, 0, None])
    while len(que) > 0:
        curr, dep, pre = que.popleft()
        par[curr] = pre
        depth[curr] = dep
        for n, w in g.edges[curr]:
            if n != pre:
                que.append([n, dep+w, curr])

    
    
    

    anc = [par]

    for i in range(LN):
        buf = [None]*N
        for j in range(N):
            if anc[i][j] == None:
                continue
            buf[j] = anc[i][anc[i][j]]
        anc.append(buf)
    return anc, depth


def LCA_query(anc, depth, u: int, v: int):
    
    
    
    N = len(depth)
    LN = int(math.log2(g.N))

    dd = depth[v] - depth[u]
    if dd < 0:
        u, v = v, u
        dd = -dd

    
    for k in range(LN):
        if dd & 1:
            v = anc[k][v]
        dd >>= 1

    
    if u == v:
        return u

    for k in range(LN-1, -1, -1):
        pu = anc[k][u]
        pv = anc[k][v]
        if pu != pv:
            u = pu
            v = pv

    
    return anc[0][u]


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

    g = Graph(N)
    for aa, bb, cc in zip(a, b, c):
        g.add_edges(*[aa-1, bb-1, cc])

    anc, depth = LCA_constract(g, root=K-1)

    for i in range(Q):
        print(depth[x[i]-1]+depth[y[i]-1])

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

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

roots = [[] for _ in range(n)]
for a,b,c in edges:
    roots[a-1].append((b-1,c))
    roots[b-1].append((a-1,c))

dis = [-1] * n
dis[k-1] = 0
stack = [k-1]

while stack:
    label = stack.pop(-1)
    for i,c in roots[label]:
        if dis[i] == -1:
            dis[i] = dis[label] + c
            stack.append(i)

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