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):
def BFS(K,edges,N):
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a-1]+=[(b-1,c)]
    roots[b-1]+=[(a-1,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist
 
N=int(input())
edges=[]
for i in range(N-1):
  edges+=[list(map(int,input().split()))]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,edges,N)
for i in range(Q):
  print(distance[xy[i][0]-1]+distance[xy[i][1]-1])

Solution (Python):
from collections import Counter,defaultdict,deque
import sys
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n=int(input())
    graph = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=map(int,input().split())
        a-=1
        b-=1
        graph[a].append((b,w))
        graph[b].append((a,w))
    graph = tuple(graph)
    q,k = map(int,input().split())
    que = deque([k-1])
    dis = [-1 for _ in range(n)]
    dis[k-1]=0
    while que:
        i = que.pop()
        for j in range(len(graph[i])):
            go = graph[i][j][0]
            d = graph[i][j][1]
            if dis[go]==-1:
                dis[go] = dis[i] + d
                que.append(go)
    for _ in range(q):
        x,y = map(int,input().split())
        print( dis[x-1] + dis[y-1] ) 

if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import defaultdict
from heapq import *

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    to=defaultdict(list)
    n=int(input())
    for _ in range(n-1):
        a,b,c=MI()
        a,b=a-1,b-1
        to[a].append([b,c])
        to[b].append([a, c])
    q,k=MI()
    k-=1
    dist=[-1]*n
    hp=[]
    heappush(hp,[0,k])
    while hp:
        d,u=heappop(hp)
        if dist[u]!=-1:continue
        dist[u]=d
        for v,c in to[u]:
            if dist[v]!=-1:continue
            heappush(hp,[d+c,v])
    for _ in range(q):
        u,v=MI1()
        print(dist[u]+dist[v])

main()

Solution (Python):





import sys

sys.setrecursionlimit(10000000)

n = int(input())
graph = [[] for _ in range(n)]

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

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

ans_list = [0 for _ in range(n)]


def dfs(node, weight):
    for data in graph[node]:
        if not used[data[0]]:
            used[data[0]] = True
            dfs(data[0], weight + data[1])
    ans_list[node] = weight


used = [False for _ in range(n)]
used[k] = True
dfs(k, 0)

for _ in range(q):
    a, b = map(lambda x: int(x) - 1, input().split())
    print(ans_list[a] + ans_list[b])

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

P = [-1] * N
DE = [0] * N
F = [0] * N
Q = [0]
while Q:
    i = Q.pop()
    for a, d in X[i][::-1]:
        if a != P[i]:
            P[a] = i
            DE[a] = DE[i] + 1
            F[a] = F[i] + d
            X[a].remove((i, d))
            Q.append(a)
KK = 17
D = [[P[i] for i in range(N)]] + [[-1]*N for _ in range(KK - 1)]
for k in range(1, KK):
    for i in range(N):
        a = D[k-1][i]
        if a > 0:
            D[k][i] = D[k-1][a]

def lca(u, v):
    if DE[u] < DE[v]:
        u, v = v, u
    while DE[u] > DE[v]:
        d = DE[u] - DE[v]
        dd = d.bit_length() - 1
        u = D[dd][u]
    if u == v:
        return u
    for i in range(KK)[::-1]:
        if D[i][u] != D[i][v]:
            u = D[i][u]
            v = D[i][v]
    return D[0][u]

def dist(u, v):
    w = lca(u, v)
    return F[u] + F[v] - F[w] * 2

T, K = map(int, input().split())
K -= 1
for _ in range(T):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    print(dist(a, K) + dist(b, K))

Solution (Python):

import sys
from collections import deque

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

    for i in range(N-1):
        if matrix.get(a[i]) == None:
            matrix[a[i]] = [(b[i],c[i])]
        else:
            matrix[a[i]].append((b[i],c[i]))

        if matrix.get(b[i]) == None:
            matrix[b[i]] = [(a[i],c[i])]
        else:
            matrix[b[i]].append((a[i],c[i]))

    
    distance_via_K = [-1]*(N+1)

    queue = deque()
    
    queue.append((K,0))

    while queue:
        q,cur_distance = queue.pop()
        distance_via_K[q] = cur_distance

        for node,distance in matrix[q]:
            if distance_via_K[node] == -1:
                queue.append((node,cur_distance+distance))

    for j in range(Q):
        print(distance_via_K[x[j]]+distance_via_K[y[j]])

    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):
from collections import deque
N = int(input())
graph = [[] for _ in range(N)]
ditstant = [float('inf')]*N
visited = [False]*N
tmp = {}
for _ in range(N-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    tmp[a, b] = c
    tmp[b, a] = c
Q, K = map(int, input().split())
K -= 1
ditstant[K] = 0  
visited[K] = True
q = deque([K])
while len(q):
    v = q.popleft()
    for e in graph[v]:
        if visited[e]:
            continue
        visited[e] = True
        ditstant[e] = min(ditstant[e], ditstant[v]+tmp[v, e])
        q.append(e)
for _ in range(Q):
    x, y = map(lambda x: int(x)-1, input().split())
    print(ditstant[x] + ditstant[y])

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

n = int(input())
l = [[] for _ in range(n)]
for _ in range(n-1):
  a, b, c = map(int, input().split())
  l[a-1].append((b-1, c))
  l[b-1].append((a-1, c))
q, k = map(int, input().split())
dist = [-1]*n
dist[k-1] = 0
def dfs(v):
  for nv, c in l[v]:
    if dist[nv] == -1:
      dist[nv] = dist[v]+c
      dfs(nv)
dfs(k-1)
for _ in range(q):
  x, y = map(int, input().split())
  print(dist[x-1] + dist[y-1])

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

n = int(input())
l = [[] for _ in range(n)]
for _ in range(n-1):
  a, b, c = map(int, input().split())
  l[a-1].append([b-1, c])
  l[b-1].append([a-1, c])
q, k = map(int, input().split())
dist = [-1]*n
dist[k-1] = 0
def dfs(v):
  for nv, c in l[v]:
    if dist[nv] == -1:
      dist[nv] = dist[v]+c
      dfs(nv)
dfs(k-1)
for _ in range(q):
  x, y = map(int, input().split())
  print(dist[x-1] + dist[y-1])

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

N = int(sys.stdin.buffer.readline())

graph = [[]*N for _ in range(N)]

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

Q, K = map(int, sys.stdin.buffer.readline().split())
dist_K = [-1]*N

def cal_dist_K(u = K-1, current_dist = 0):
    dist_K[u] = current_dist
    for v,c in graph[u]:
        if dist_K[v] == -1:
            cal_dist_K(v, current_dist + c)

cal_dist_K()

ans = []
for _ in range(Q):
    x, y = map(int, sys.stdin.buffer.readline().split())
    ans.append(int(dist_K[x-1] + dist_K[y-1]))

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

Solution (Python):
N=int(input())
edges=[list(map(int,input().split())) for i in range(N-1)]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
root=[[] for _ in range(N)]
for a,b,c in edges:
        root[a-1].append((b-1,c))
        root[b-1].append((a-1,c))
d=[-1]*N
s=[K-1]
d[K-1]=0
while s:
        l=s.pop()

        for i,c in root[l]:
                if d[i]==-1:
                        d[i]=d[l]+c
                        s.append(i)
for i in range(Q):
        print(d[xy[i][0]-1]+d[xy[i][1]-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
N = int(input())
edge = [[] for _ in range(N+1)]
for _ in range(N-1):
    a,b,c = map(int,input().split())
    edge[a].append((b,c))
    edge[b].append((a,c))
Q,K = map(int,input().split())
distance = [None] * (N+1)
def dfs(v1,d):
    distance[v1] = d
    for v2,dd in edge[v1]:
        if distance[v2] is not None:
            continue
        dfs(v2,d+dd)

dfs(K,0)

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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
N = int(input())
edge = [[] for _ in range(N+1)]
for _ in range(N-1):
    a,b,c = map(int,input().split())
    edge[a].append((b,c))
    edge[b].append((a,c))
Q,K = map(int,input().split())
distance = [None] * (N+1)
def dfs(v1,d):
    distance[v1] = d
    for v2,dd in edge[v1]:
        if distance[v2] is not None:
            continue
        dfs(v2,d+dd)

dfs(K,0)

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

Solution (Python):
import heapq
import sys

input = sys.stdin.readline

def dijkstra(s, edge, N):
    d = [float('inf')] * N
    used = [True] * N
    d[s] = 0
    used[s] = False
    edgelist = []
    for a, b in edge[s]:
        heapq.heappush(edgelist, a * (10 ** 6) + b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)

        if not used[minedge%(10 ** 6)]:
            continue
        v = minedge % (10 ** 6)
        d[v] = minedge // (10 ** 6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist, (e[0] + d[v]) * (10 ** 6) + e[1])
    return d

def main():
    N = int(input())
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        edge[a].append([c,b])
        edge[b].append([c,a])
    Q, K = map(int, input().split())
    K -= 1
    d = dijkstra(K, edge, N)
    for _ in range(Q):
        x, y = map(int, input().split())
        x -= 1
        y -= 1
        print(d[x] + d[y])



if __name__ == "__main__":
    main()

Solution (Python):
N=int(input())
abc=[tuple(map(int,input().split())) for i in range(N-1)]
g=[set() for i in range(N)]
for a,b,c in abc:
  g[a-1].add((b-1,c))
  g[b-1].add((a-1,c))
memo=[-1]*N

Q,K=map(int,input().split())
import collections
q=collections.deque([(K-1,0)])
memo[K-1]=0
while(q):
  
  x,w = q.popleft()
  for a,b in g[x]:
    if memo[a]==-1:
      memo[a]=w+b
      q.append((a,w+b))
  
for i in range(Q):
  x,y=map(int,input().split())
  print(memo[x-1]+memo[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)]

from heapq import heappop, heappush

def main():
    cost = [[] for _ in range(n)]
    for i in range(n - 1):
        a = abc[i][0] - 1
        b = abc[i][1] - 1
        c = abc[i][2]
        cost[a].append((b, c))
        cost[b].append((a, c))
    

    start = K - 1
    d = [float('inf') for i in range(n)] 
    d[start] = 0

    q = [] 
    heappush(q, (d[start], start))
    while q:
        du, u = heappop(q) 
        if d[u] < du:
            continue
        for v, weight in cost[u]:
            alt = du + weight
            if d[v] > alt:
                d[v] = alt
                heappush(q, (alt, v))

    for goal1, goal2 in xy:
        print(d[goal1 - 1] + d[goal2 - 1])

if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
l=[[] for i in range(n+1)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  l[a].append([b,c])
  l[b].append([a,c])
q,k=map(int,input().split())
from heapq import heappush,heappop
inf=10**20
def dijkstra(s):
  q=[(0,s)]
  dist=[inf]*(n+1)
  dist[s]=0
  while q:
    c,v=heappop(q)
    if dist[v]<c:
      continue
    for i in l[v]:
      t=i[0]
      cost=i[1]
      if dist[v]+cost<dist[t]:
        dist[t]=dist[v]+cost
        heappush(q,[dist[t],t])
  return dist
d=dijkstra(k)
for i in range(q):
  x,y=map(int,input().split())
  print(d[x]+d[y])

Solution (Python):
n=int(input())
l=[[] for i in range(n+1)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  l[a].append([b,c])
  l[b].append([a,c])
q,k=map(int,input().split())
from heapq import heappush,heappop
inf=10**20
def dijkstra(s):
  q=[(0,s)]
  dist=[inf]*(n+1)
  dist[s]=0
  while q:
    c,v=heappop(q)
    if dist[v]<c:
      continue
    for i in l[v]:
      t=i[0]
      cost=i[1]
      if dist[v]+cost<dist[t]:
        dist[t]=dist[v]+cost
        heappush(q,[dist[t],t])
  return dist
d=dijkstra(k)
for i in range(q):
  x,y=map(int,input().split())
  print(d[x]+d[y])

Solution (Python):
import heapq
def dijkstra(n, edges, s):
    min_dist = [float('inf')] * n
    min_dist[s] = 0
    next_v = []
    heapq.heappush(next_v, (0, s))
    path = [-1] * n
    
    while True:
        if len(next_v) == 0: break
        d, v = heapq.heappop(next_v)
        
        for u, d in edges[v]:
            if min_dist[u] > min_dist[v] + d:
                min_dist[u] = min_dist[v] + d
                heapq.heappush(next_v, (min_dist[u], u))
                path[u] = v
                
    return min_dist, path

n = int(input())
edges = [[] for _ in range(n)]

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


q, k = map(int, input().split())
dist, _ = dijkstra(n, edges, k-1)

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

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

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

INF=10**9+1
distFromK=[-1 for i in range(n)]


stack=[]
stack.append([K-1,0,-1])
while stack:
  node=stack.pop()
  v=node[0]
  d=node[1]
  parent=node[2]
  if distFromK[v]==-1:
    distFromK[v]=d
  else:
    distFromK[v]=min(distFromK[v],d)
  targets=dist[v]
  for child in targets:
    if child[0]==parent or child[0]==v:
      continue
    stack.append([child[0],d+child[1],v])

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

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


def BFS(x):
    visited = [False for _ in range(N+1)]
    next_N = [False for _ in range(N+1)]
    INF = float('inf')
    dest = [INF for _ in range(N+1)]
    d = deque()
    visited[x] = True
    dest[x] = 0
    for B, C in edge[x]:
        d.append([B, C])
        next_N[B] = True
        dest[B] = dest[x] + C
    while d:
        now = d.popleft()
        visited[now[0]] = True
        for B, C in edge[now[0]]:
            if visited[B] == False and next_N[B] == False:
                d.append([B, C])
                next_N[B] = True
                dest[B] = dest[now[0]] + C
    return dest

Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(Q)]
DEST = BFS(K)
for X, Y in xy:
    print(DEST[X] + DEST[Y])

Solution (Python):
from collections import deque

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

q = deque()
q.append((K-1, 0))
d = [-1]*N
d[K-1] = 0
while q:
    temp = q.popleft()
    p = temp[0]
    r = temp[1]
    for t in E[p]:
        if d[t[0]] < 0:
            d[t[0]] = r+t[1]
            q.append((t[0], r+t[1]))
            
for i in range(Q):
    print(d[qlist[i][0]-1]+d[qlist[i][1]-1])

Solution (Python):
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    tmd = collections.defaultdict(list)
    cl = collections.defaultdict(int)
    for i in range(n-1):
        tma, tmb, tmc = list(map(int, readline().split()))
        tmd[tma-1] += [tmb-1]
        tmd[tmb-1] += [tma-1]
        cl[tma-1, tmb-1] = tmc
        cl[tmb-1, tma-1] = tmc
    q, k = list(map(int, readline().split()))

    ql = [[0, k-1]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(int)
    fq[k-1]
    while True:
        if len(ql) != 0:
            cost, tmp = ql.popleft()
            for tmv in tmd[tmp]:
                if tmv not in fq:
                    ql.append([cost + cl[tmv, tmp], tmv])
                    fq[tmv] = cost + cl[tmv, tmp]
                elif cost + cl[tmv, tmp] < fq[tmv]:
                    fq[tmv] = cost + cl[tmv, tmp]
        else:
            break
    for i in range(q):
        x, y = list(map(int, readline().split()))
        print(fq[x-1] + fq[y-1])


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
sys.setrecursionlimit(200000)
n = int(input())

path = [None]*(n + 1)
adjacent_list = [[] for i in range(n+1)]

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

def dfs(node_n ,distance,finished):
    
    finished.add(node_n)
    
    path[node_n] = distance
    
    for i in adjacent_list[node_n]:
        next = i[0]
        if next not in finished:
            
            dfs(next, distance + i[1],finished)

q,k = list(map(int, input().split()))
dfs(k, 0, set())

for i in range(q):
    s, g = list(map(int, input().split()))
    print(path[s] + path[g])

Solution (Python):
import sys

sys.setrecursionlimit(200000)

n = int(input())

path = [None]*(n + 1)
adjacent_list = [[] for i in range(n+1)]

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



def dfs(node_n, distance, finished):
    
    finished.add(node_n)
    
    path[node_n] = distance
    
    for i in adjacent_list[node_n]:
        next = i[0]
        if next not in finished:
            
            dfs(next, distance + i[1], finished)


q, k = list(map(int, input().split()))
dfs(k, 0, set())

for i in range(q):
    s, g = list(map(int, input().split()))
    print(path[s] + path[g])

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() 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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
G = [[] for _ in range(n)]
for a, b, c in LIR(n - 1):
    G[a - 1] += [(b - 1, c)]
    G[b - 1] += [(a - 1, c)]

q, k = LI()
dq = deque([k - 1])
dist = [-1] * n
dist[k - 1] = 0
while dq:
    u = dq.popleft()
    for v, c in G[u]:
        if dist[v] == -1:
            dist[v] = dist[u] + c
            dq += [v]

for _ in range(q):
    x, y = LI()
    print(dist[x - 1] + dist[y - 1])

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() 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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
G = [[] for _ in range(n)]
for a, b, c in LIR(n - 1):
    G[a - 1] += [(b - 1, c)]
    G[b - 1] += [(a - 1, c)]

q, k = LI()
dq = deque([k - 1])
dist = [-1] * n
dist[k - 1] = 0
while dq:
    u = dq.pop()
    for v, c in G[u]:
        if dist[v] == -1:
            dist[v] = dist[u] + c
            dq += [v]

for _ in range(q):
    x, y = LI()
    print(dist[x - 1] + dist[y - 1])

Solution (Python):


import collections


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


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


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

dist = [-1 for _ in range(N)]
dist[K-1] = 0
stack = [K-1]
while len(stack) != 0:
    a = stack.pop()
    for b, c in graph[a]:
        if dist[b] == -1:
            dist[b] = dist[a] + c
            stack.append(b)











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

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

distance = BFS(K - 1, abc, N)
for x, y in xy:
  print(distance[x - 1] + distance[y - 1])

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
  a,b,c = map(int,input().split())
  a-=1;b-=1
  g[a].append([b,c])
  g[b].append([a,c])
q,k = map(int,input().split())
k -= 1
con = [-1] * n
con[k] = 0
stack = [k]
while stack:
  cur = stack.pop()
  for i,j in g[cur]:
    if con[i] == -1:
      con[i] = con[cur] + j
      stack.append(i)
for i in range(q):
  x,y = map(int,input().split())
  x-=1;y-=1
  print(con[x]+con[y])

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
  a,b,c = map(int,input().split())
  a-=1;b-=1
  g[a].append([b,c])
  g[b].append([a,c])
q,k = map(int,input().split())
k -= 1
con = [-1] * n
con[k] = 0
stack = [k]
while stack:
  cur = stack.pop()
  for i,j in g[cur]:
    if con[i] == -1:
      con[i] = con[cur] + j
      stack.append(i)
for i in range(q):
  x,y = map(int,input().split())
  x-=1;y-=1
  print(con[x]+con[y])

Solution (Python):
n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
  a,b,c = map(int,input().split())
  a-=1;b-=1
  g[a].append([b,c])
  g[b].append([a,c])
q,k = map(int,input().split())
k -= 1
con = [-1] * n
con[k] = 0
stack = [k]
while stack:
  cur = stack.pop()
  for i,j in g[cur]:
    if con[i] == -1:
      con[i] = con[cur] + j
      stack.append(i)
for i in range(q):
  x,y = map(int,input().split())
  x-=1;y-=1
  print(con[x]+con[y])

Solution (Python):
n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
  a,b,c = map(int,input().split())
  a-=1;b-=1
  g[a].append([b,c])
  g[b].append([a,c])
q,k = map(int,input().split())
k -= 1
con = [-1] * n
con[k] = 0
stack = [k]
while stack:
  cur = stack.pop()
  for i,j in g[cur]:
    if con[i] == -1:
      con[i] = con[cur] + j
      stack.append(i)
for i in range(q):
  x,y = map(int,input().split())
  x-=1;y-=1
  print(con[x]+con[y])

Solution (Python):
import sys
import numpy as np
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import defaultdict

N = int(input())
lines = readlines()
graph = defaultdict(list)
for line in lines[:N-1]:
  a,b,c = map(int,line.split())
  graph[a].append((b,c))
  graph[b].append((a,c))
Q, K = map(int,lines[N-1].split())
XY = np.array([line.split() for line in lines[N:]],np.int64)

def degreesOfSeparation(graph,start):
    if start not in graph:
        return -1
    visited = set()
    frontier = set()
    table = [0] * (len(graph) + 1)
    degrees = 0
    visited.add(start)
    frontier.add(start)
    while len(frontier) > 0:
        
        
        newfront = set()
        for g in frontier:
            for next in graph[g]:
                if next[0] not in visited:
                    visited.add(next[0])
                    newfront.add(next[0])
                    table[next[0]] += next[1] + table[g]
        frontier = newfront
    return table
table = degreesOfSeparation(graph,K)
for q in range(Q):
  print(table[XY[q][0]] + table[XY[q][1]])

Solution (Python):
from collections import deque
n=int(input())
g=[[] for i 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())
qu=deque([[k-1,0]])
v=[0]*n
d=[0]*n
while len(qu)>0:
    s=qu.popleft()
    v[s[0]]=1
    for j in g[s[0]]:
        if not v[j[0]]:
            v[j[0]]=1
            d[j[0]]=s[1]+j[1]
            qu+=[[j[0],d[j[0]]]]
for i in range(q):
    x,y=map(int,input().split())
    print(d[x-1]+d[y-1])

Solution (Python):
n=int(input())
ki=[[] for _ in range(n)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  ki[a-1].append([b-1,c])
  ki[b-1].append([a-1,c])
q,k=map(int,input().split())
s=[0]*n
from collections import deque
d=deque()
d.append(k-1)
while d:
  g=d.popleft()
  for i in ki[g]:
    if s[i[0]]:
      continue
    d.append(i[0])
    s[i[0]]=s[g]+i[1]
for i in range(q):
  x,y=map(int,input().split())
  print(s[x-1]+s[y-1])

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000)
n=int(input())
visitedlist=[-1 for  i in range(n)]
kilist=[[] for i in range(n)]
anslist=[0 for i in range(n)]
searchedlist=[-1 for i in range(n)]
for i in range(n-1):
        a,b,c=map(int,input().split())
        kilist[a-1].append((b,c))
        kilist[b-1].append((a,c))        
def search(i):
        searchedlist[i-1]=1
        visitedlist[i-1]=1
        flag=0
        for j in kilist[i-1]:
            if visitedlist[j[0]-1]<0:
                visitedlist[j[0]-1]=1
                flag+=1
                anslist[j[0]-1]=anslist[i-1]+j[1]
        else:
            pass

        if flag>0:    
            for k in kilist[i-1]:
                if searchedlist[k[0]-1]==-1:
                    search(k[0])
q,k=map(int,input().split())
List=[0 for i in range(q)]
search(k)
for i in range(q):
    x,y=map(int,input().split())
    List[i]=anslist[x-1]+anslist[y-1]
for j in List:
    print(j)

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000)
n=int(input())
visitedlist=[-1 for  i in range(n)]
kilist=[[] for i in range(n)]
anslist=[0 for i in range(n)]
searchedlist=[-1 for i in range(n)]
for i in range(n-1):
        a,b,c=map(int,input().split())
        kilist[a-1].append((b,c))
        kilist[b-1].append((a,c))        
def search(i):
        searchedlist[i-1]=1
        visitedlist[i-1]=1
        flag=0
        for j in kilist[i-1]:
            if visitedlist[j[0]-1]<0:
                visitedlist[j[0]-1]=1
                flag+=1
                anslist[j[0]-1]=anslist[i-1]+j[1]
        else:
            pass

        if flag>0:    
            for k in kilist[i-1]:
                if searchedlist[k[0]-1]==-1:
                    search(k[0])
q,k=map(int,input().split())
List=[0 for i in range(q)]
search(k)
for i in range(q):
    x,y=map(int,input().split())
    List[i]=anslist[x-1]+anslist[y-1]
for j in List:
    print(j)