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

import math

import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





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

Q,K = IL()
d = [-1 for i in range(N)]
d[K-1] = 0
q = deque([K-1])
while q:
  u = q.pop()
  for v,c in graph[u]:
    if d[v] < 0:
      d[v] = d[u]+c
      q.append(v)
for _ in range(Q):
  x,y = IL()
  print(d[x-1]+d[y-1])

Solution (Python):
from collections import deque
import sys

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


N = int(input())

G = [[] for _ in range(N + 1)]
for i in range(N - 1):
    a, b, c = [int(_) for _ in input().split()]
    G[a].append((b, c))
    G[b].append((a, c))
Q, K = [int(_) for _ in input().split()]


G2 = [10 ** 12] * (N + 1)

G2[K] = 0


def f():
    que = deque()
    que.append((K, 0))
    while que:
        v, p = que.pop()
        for nv, nc in G[v]:
            if nv == p: continue
            G2[nv] = G2[v] + nc
            que.append((nv, v))


f()

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

Solution (Python):
from collections import deque
import sys

sys.setrecursionlimit(10 ** 9)

N = int(input())

G = [[] for _ in range(N + 1)]
for i in range(N - 1):
    a, b, c = [int(_) for _ in input().split()]
    G[a].append((b, c))
    G[b].append((a, c))
Q, K = [int(_) for _ in input().split()]


G2 = [10 ** 12] * (N + 1)

G2[K] = 0


def f():
    que = deque()
    que.append((K, 0))
    while que:
        v, p = que.pop()
        for nv, nc in G[v]:
            if nv == p: continue
            G2[nv] = G2[v] + nc
            que.append((nv, v))


f()

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

Solution (Python):
N = int(input())
from heapq import heapify, heappush, heappop

inf = float("inf")
def dijkstra(graph, start):  
    vsize = len(graph)
    dist = [inf] * vsize
    seen = [False] * vsize
    prev = [None] * vsize
    pq = []
    heapify(pq)

    dist[start] = 0
    heappush(pq, (0, start))  
    while pq:
        cost, u = heappop(pq)
        seen[u] = True
        if dist[u] < cost:
            continue
        for v, w in graph[u]:
            temp_cost = dist[u] + w
            if not seen[v] and temp_cost < dist[v]:
                dist[v] = temp_cost
                prev[v] = u
                heappush(pq, (dist[v], v))
    return dist
graph = [[] for _ in range(N)]
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())
shortest_path_K = dijkstra(graph, K-1)
for _ in range(Q):
    x, y = map(int, input().split())
    print(shortest_path_K[x-1]+shortest_path_K[y-1])

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    n = int(input())
    v = [[0]+[]*(n+1) for i in range(n+1)]
    for i in range(n-1):
        a,b,c = map(int,input().split())
        v[a].append([b,c])
        v[b].append([a,c])

    q,k = map(int,input().split())
    l = [k]
    while l:
        now = l.pop()
        for i in v[now][1:]:
            if v[i[0]][0] == 0:
                v[i[0]][0] = i[1]+v[now][0]
                l.append(i[0])

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

if __name__ == '__main__':
    main()

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    n = int(input())
    v = [[0]+[]*(n+1) for i in range(n+1)]
    for i in range(n-1):
        a,b,c = map(int,input().split())
        v[a].append([b,c])
        v[b].append([a,c])

    q,k = map(int,input().split())
    l = [k]
    while l:
        now = l.pop()
        for i in v[now][1:]:
            if v[i[0]][0] == 0:
                v[i[0]][0] = i[1]+v[now][0]
                l.append(i[0])

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

if __name__ == '__main__':
    main()

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

q,k = map(int,input().split())
l = [k]
while l:
    now = l.pop()
    for i in v[now][1:]:
        if v[i[0]][0] == 0:
            v[i[0]][0] = i[1]+v[now][0]
            l.append(i[0])

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

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

q,k = map(int,input().split())
l = [k]
while l:
    now = l.pop()
    for i in v[now][1:]:
        if v[i[0]][0] == 0:
            v[i[0]][0] = i[1]+v[now][0]
            l.append(i[0])
            
for i in range(q):
    x,y = map(int,input().split())
    print(v[x][0]+v[y][0])

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

q,k = map(int,input().split())
l = [k]
while l:
    now = l.pop()
    for i in v[now][1:]:
        if v[i[0]][0] == 0:
            v[i[0]][0] = i[1]+v[now][0]
            l.append(i[0])
            
for i in range(q):
    x,y = map(int,input().split())
    print(v[x][0]+v[y][0])

Solution (Python):
import sys
from collections import deque
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    G = [[] for i in range(N)]
    for i in range(N - 1):
        a, b, c = map(int, readline().split())
        G[a-1].append((b-1, c))
        G[b-1].append((a-1, c))

    dist = [-1 for i in range(N)]
    Q, K = map(int, readline().split())
    dist[K-1] = 0
    q = deque([[K - 1, 0, -1]])
    while q:
        v, d, parent = q.popleft()
        dist[v] = d
        for child in G[v]:
            if child[0] == parent:
                continue
            q.append([child[0], d + child[1], v])

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys


import math
import collections

import bisect
import itertools
import fractions

import copy
import heapq
import decimal

import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))





def main():
    n = ni()
    edge = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b, c = ns()
        a -= 1
        b -= 1
        edge[a].append((b, c))
        edge[b].append((a, c))

    dist_table = [-1 for _ in range(n)]

    def dfs(node, dist):
        for t, cost in edge[node]:
            if dist_table[t] == -1:
                dist_table[t] = dist + cost
                dfs(t, dist_table[t])
        return

    q, k = ns()
    k -= 1
    dist_table[k] = 0
    dfs(k, 0)

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


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
n = int(input())

graph = [[] for i in range(n)]

for i 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_num, k = map(int, input().split())

seen = [-1 for i in range(n)]
seen[k-1] = 0


q = deque()

q.append((k-1, 0))

while len(q) > 0:
    cur = q.popleft()

    cur_node = cur[0]
    cur_cost = cur[1]

    for nx in graph[cur_node]:
        nx_node = nx[0]
        nx_cost = cur_cost + nx[1]

        if seen[nx_node] < 0:
            seen[nx_node] = nx_cost
            q.append((nx_node, nx_cost))

queries = []

for i in range(q_num):
    queries.append(list(map(int, input().split())))


for query in queries:
    print(seen[query[0]-1] + seen[query[1]-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
n = int(input())
visited = [0]*n
dist = [0]*n
edge = [[] for _ in range(n)]
def dfs(k):
    visited[k]=1
    for i in edge[k]:
        if visited[i[0]]==0:
            dist[i[0]]=i[1]+dist[k]
            dfs(i[0])


    return dist
def main():

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

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

    visited[k-1]=1
    dist = dfs(k-1)

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


    for i in range(q):
        print(res[i])
if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n = int(input())
visited = [0]*n
def dfs(edge, dist, k):
    visited[k]=1
    for i in edge[k]:
        if visited[i[0]]==0:
            dist[i[0]]=i[1]+dist[k]
            dfs(edge, dist, i[0])


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

    q,k=map(int, input().split())
    
    dist = [0]*n
    visited[k-1]=1
    dist = dfs(edge, dist, k-1)

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


    for i in range(q):
        print(res[i])
if __name__ == '__main__':
    main()

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
tree=[[] for i in range(n)]
for i in range(n-1):
    a,b,c=MI()
    a-=1
    b-=1
    tree[a].append([b,c])
    tree[b].append([a,c])
q,k=MI()

k-=1
dis=[[-1,0] for i in range(n)]
dis[k][0]=0
def dfs(x):
    for s,t in tree[x]:
        if dis[s][0]>=0:
            continue
        dis[s][0]=dis[x][0]+t
        if x==k:
            dis[s][1]=s
        else:
            dis[s][1]=x
        dfs(s)
dfs(k)
for i in range(q):
    x,y=MI()
    x-=1
    y-=1
    print(dis[x][0]+dis[y][0])

Solution (Python):
from collections import deque
n = int(input())
edge = []
dist = [-1]*(n+1)
for i in range(n+1):
    edge.append([])
for i 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())
dist[k] = 0
que = deque([k])
used = set()
used.add(k)
while que:
    here = que.popleft()
    dist_here = dist[here]
    for i in edge[here]:
        if i[0] not in used:
            que.append(i[0])
            used.add(i[0])
            dist[i[0]] = dist_here + i[1]
for i in range(q):
    x,y = map(int,input().split())
    print(dist[x]+dist[y])

Solution (Python):
import heapq
N = int(input())
edges = [[] for _ in range(N)]
for i 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())
K -= 1


ans_list = []
def dijkstra(edges, num_v, start):
    dist = [float('inf')] * num_v
    dist[start] = 0
    q = []
    heapq.heappush(q, [0, start])

    while len(q) > 0:
        _, u = heapq.heappop(q)
        for edge in edges[u]:
            if dist[edge[0]] > dist[u] + edge[1]:
                dist[edge[0]] = dist[u] + edge[1]
                heapq.heappush(q, [dist[u] + edge[1], edge[0]])
    return dist
base = dijkstra(edges,  N, K)
for i in range(Q):
    x, y = map(lambda n: int(n) - 1, input().split())
    x_K = base[x]
    K_y = base[y]
    ans_list.append(x_K + K_y)

for i in ans_list:
    print(i)

Solution (Python):
from collections import defaultdict
 
n = int(input())
V = defaultdict(list)

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

def dfs(source):
    dist = [-1]*(n+1)
    dist[source] = 0
    q = [source]
    while q:
        a = q.pop()
        for b in V[a]:
            if dist[b[0]]!=-1:
                continue
            dist[b[0]] = dist[a] + b[1]
            q.append(b[0])
    return dist

q,k = map(int, input().split())
dk = dfs(k)

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

Solution (Python):



import sys
readline = sys.stdin.readline

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

dist = [-1 for i in range(N)] 
Q,K = map(int,readline().split())

dist[K - 1] = 0
from collections import deque

q = deque([[K - 1, 0, -1]])
while q:
  v, d, parent = q.popleft()
  dist[v] = d
  for child in G[v]:
    if child[0] == parent:
      continue
    q.append([child[0],d + child[1], v])

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

Solution (Python):
from heapq import heappop,heappush
def dijkstra(s,n,edge):
  """
  始点sから各頂点への最短距離を返す

  Parameters
  ----------
  s : int
      視点とする頂点（0-indexed）
  n : int
      グラフの要素数
  eage:list
      グラグ

  Returns
  -------
  dist ：list
  始点sから各頂点への最短距離
  """
  dist=[float("inf")]*n
  dist[s]=0
  used=[-1]*n
  hq=[[dist[s],s]]
  while hq:
    d,cur=heappop(hq)
    if dist[cur]<d:continue 
    for nx,nxd in edge[cur]:
      if dist[cur]+nxd<dist[nx]:
        dist[nx]=dist[cur]+nxd
        used[nx]=cur
        heappush(hq,[dist[cur]+nxd,nx])
  return dist

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


q,k=map(int,input().split())
xy=[list(map(int,input().split()))for _ in range(q)]
d=dijkstra(k-1,n,edge)
for x,y in xy:
  print(d[x-1]+d[y-1])

Solution (Python):

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

Q,K=map(int, input().split())
que=deque([(K-1,0)])
done=[-1]*N
while que:
    t=que.popleft()
    now,nowd=t
    done[now]=nowd
    for nex in T[now]:
        nexnode,nexd=nex
        if done[nexnode]!=-1:
            continue
        else:
            que.append((nexnode, nowd+nexd))


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

Solution (Python):
from collections import deque

N = int(input())
G = [[] for _ in range(N)]
for i in range(N-1):
  a, b, c = map(int, input().split())
  G[a-1].append((b-1, c))
  G[b-1].append((a-1, c))
  
Q, K = map(int, input().split())
K -= 1
costs = [0] * N
stack = deque([K])
visited = [False]*N
visited[K] = True

while stack:
  now = stack.pop()
  for nxt, c in G[now]:
    if visited[nxt]:
      continue
    visited[nxt] = True
    costs[nxt] = costs[now] + c
    stack.append(nxt)
    
for i in range(Q):
  x, y = map(int, input().split())
  print(costs[x-1] + costs[y-1])

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

N = int(input())
INF = 10 ** 14
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())
d = [INF] * N
d[K-1] = 0

def dfs(x):
    for u, cost in edges[x]:
        if d[u] == INF:
            d[u] = d[x] + cost
            dfs(u)

dfs(K-1)

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

Solution (Python):
from collections import deque
INFTY = 10**14+100
N = int(input())
T = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    a,b,c = map(int,input().split())
    T[a].append((b,c))
    T[b].append((a,c))
Q,K = map(int,input().split())
dist = [INFTY for _ in range(N+1)]
hist = [0 for _ in range(N+1)]
dist[K] = 0
hist[K] = 1
heap = deque([(K,0)])
while heap:
    x,d = heap.popleft()
    for y,d1 in T[x]:
        if hist[y]==0:
            heap.append((y,d+d1))
            dist[y] = d+d1
            hist[y]=1
for _ in range(Q):
    x,y = map(int,input().split())
    print(dist[x]+dist[y])

Solution (Python):
n = int(input())
import sys
sys.setrecursionlimit(10**8)
def D(now,pre,SUM):
    dist[now] = SUM
    for BC in G[now]:
        if BC[0] == pre:
            continue
        D(BC[0],now,SUM+BC[1])



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

k -= 1

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

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

n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b, c = [int(x) for x in input().split()]
    edge[a - 1].append([c, b - 1])
    edge[b - 1].append([c, a - 1])
q, k = [int(x) for x in input().split()]

import heapq
def dijkstra(s):
    d = [float("inf")]*n
    used = [False]*n
    d[s] = 0
    used[s] = True
    queue = []
    for e in edge[s]:
        heapq.heappush(queue, e)
    while queue:
        
        cost, to = heapq.heappop(queue)
        if used[to]:
            continue
        d[to] = cost
        used[to] = True
        for e in edge[to]:
            
            if used[e[1]]:
                continue
            heapq.heappush(queue, [d[to] + e[0], e[1]])
    return d

d = dijkstra(k - 1)

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

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

def bfs():
    q = deque([K-1])
    dist = [-1]*N
    dist[K-1] = 0
    
    while q:
        v = q.popleft()
        
        for nv, w in G[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+w
                q.append(nv)
    
    return dist

N = int(input())
G = [[] 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())
dist = bfs()

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

graph = [[] for _ in range(N)]
for ai, bi, ci in abc:
    graph[ai - 1].append((bi - 1, ci))
    graph[bi - 1].append((ai - 1, ci))

MY_INF = 10 ** 18
import heapq

q = [(0, K - 1)]
d = [MY_INF] * N
d[K - 1] = 0
while len(q) > 0:
    dist, src = heapq.heappop(q)
    for dst, c_tmp in graph[src]:
        dist_tmp = dist + c_tmp
        if d[dst] > dist_tmp:
            d[dst] = dist_tmp
            heapq.heappush(q, (dist_tmp, dst))

for xi, yi in xy:
    print(d[xi - 1] + d[yi - 1])

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

N = int(input())

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

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

d = [-1] * (N + 1)
d[K] = 0
stack = [K]
while stack:
    now = stack.pop()
    for tmp in G[now]:
        next_ = tmp[0]
        if d[next_] == -1:
            d[next_] = d[now] + tmp[1]
            stack.append(next_)

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

Solution (Python):
from heapq import heappush, heappop
INF = 10**15
def dijkstra(s, edges):
    n = len(edges)
    que = []
    d = [INF] * n
    prev = [-1] * n
    d[s] = 0
    heappush(que, (0, s))
    while len(que) > 0:
        (c, v) = heappop(que)
        if d[v] < c:
            continue
        for (cc, w) in edges[v]:
            if d[w] > d[v] + cc:
                d[w] = d[v] + cc
                prev[w] = v
                heappush(que, (d[w], w))
    return d, prev

n = int(input())
edges = [[] for i in range(n)]
for i in range(n-1):
    ai, bi, ci = map(int, input().split())
    ai, bi = ai-1, bi-1
    edges[ai].append((ci, bi))
    edges[bi].append((ci, ai))

q, k = map(int, input().split())
k -= 1
d, prev = dijkstra(k, edges)
ans = []
for i in range(q):
    xi, yi = map(int, input().split())
    xi, yi = xi-1, yi-1
    ans.append(d[xi]+d[yi])

for i in ans:
    print(i)

Solution (Python):
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
XY = [tuple(map(lambda a: int(a) - 1, input().split())) for _ in range(Q)]

minDist = [10**18] * N
minDist[K] = 0
st = [K]
while st:
    now = st.pop()
    dist = minDist[now]
    for to, c in edges[now]:
        d = dist + c
        if minDist[to] > d:
            minDist[to] = d
            st.append(to)

ans = [minDist[x] + minDist[y] for x, y in XY]
print(*ans, sep='\n')

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

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

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

import heapq
INF = 10**18
def dijkstra_heap(s, edge, n):
    d = [INF] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d

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

Solution (Python):
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    Edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        Edge[a-1].append((b-1, c))
        Edge[b-1].append((a-1, c))
    Q, K = map(int, input().split())
    Ans = [0] * Q
    Dist = [-1] * N
    q = deque()
    q.append((K-1, K-1, 0))
    while q:
        nowN, pre, dist = q.popleft()
        if Dist[nowN] == -1:
            Dist[nowN] = dist
            for nextN, cost in Edge[nowN]:
                if nextN != pre: q.append((nextN, nowN, dist + cost))
    for i in range(Q):
        x, y = map(int, input().split())
        Ans[i] = Dist[x-1] + Dist[y-1]

    print(*Ans, sep="\n")
    return 0

if __name__ == "__main__":
    solve()

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

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

def dfs(start):
    for x,cost in graph[start]:
        if d[x]==-1:
            d[x]=d[start]+cost
            dfs(x)

Q,K=map(int,input().split())
K-=1
d=[-1]*N
d[K]=0
dfs(K)
for i in range(Q):
    x,y=map(int,input().split())
    x-=1
    y-=1
    print(d[x]+d[y])

Solution (Python):
from heapq import heappush, heappop

INF = float('inf')

n = int(input())
dn = {v: [] for v in range(n)}
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    dn[a - 1] += [(b - 1, c)]
    dn[b - 1] += [(a - 1, c)]

q, k = map(int, input().split())
xy = [map(int, input().split()) for _ in range(q)]

dd = [INF] * n
queue = []
heappush(queue, (0, k - 1))
while queue:
    d, v = heappop(queue)
    for neighbor, c in dn[v]:
        dtmp = d + c
        if dtmp < dd[neighbor]:
            dd[neighbor] = dtmp
            heappush(queue, (dtmp, neighbor))


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

Solution (Python):
from collections import defaultdict
import heapq


def dijkstra(N, start, adj_nodes, costs):
    INF = 10**15
    dist = [INF for _ in range(N)]
    dist[start] = 0
    frontier = [(0, start)]
    while len(frontier) > 0:
        d, node = heapq.heappop(frontier)
        for next_node in adj_nodes[node]:
            if dist[next_node] > d + costs[(node, next_node)]:
                dist[next_node] = d + costs[(node, next_node)]
                frontier.append((dist[next_node], next_node))
    return dist


def main():
    N = int(input())
    adj_nodes = defaultdict(list)
    costs = defaultdict(int)
    for _ in range(N - 1):
        a, b, c = list(map(int, input().split(' ')))
        a -= 1
        b -= 1
        adj_nodes[a].append(b)
        adj_nodes[b].append(a)
        costs[(a, b)] = c
        costs[(b, a)] = c
    Q, K = list(map(int, input().split(' ')))
    K -= 1
    queries = [list(map(lambda q: int(q) - 1, input().split(' '))) for _ in range(Q)]
    dist = dijkstra(N, K, adj_nodes, costs)
    for query in queries:
        x, y = query
        print(dist[x] + dist[y])


if __name__ == '__main__':
    main()

Solution (Python):
import heapq
import collections

INF = 10 ** 16

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

class edge:
    def __init__(self, to, cost): self.to, self.cost = to, cost

def main():
    N = Z()
    E = collections.defaultdict(list)
    for _ in range(N-1):
        a, b, c = ZZ()
        E[a].append(edge(b, c))
        E[b].append(edge(a, c))
    Q, K = ZZ()

    def dijkstra(s):
        que = list()
        heapq.heapify(que)
        newd = [INF] * (N+1)
        newd[s] = 0
        heapq.heappush(que, [newd[s], s])

        while que:
            p = heapq.heappop(que)
            v = p[1]
            if newd[v] < p[0]: continue
            for e in E[v]:
                if newd[e.to] > newd[v] + e.cost:
                    newd[e.to] = newd[v] + e.cost
                    heapq.heappush(que, [newd[e.to], e.to])
        return newd

    dist = dijkstra(K)
    output = []

    for _ in range(Q):
        x, y = ZZ()
        output.append(dist[x] + dist[y])
    print(*output, sep='\n')

    return

if __name__ == '__main__':
    main()