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

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

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

l = [[] for _ in range(n+1)]
for i in range(n-1):
    l[a[i]].append([b[i],c[i]])
    l[b[i]].append([a[i],c[i]])

d = [0] * (n+1)
check = [0] * (n+1)
check[k] = 1
que = [k]
count = 1

while len(que) > 0:
    tmp = que.pop(0)
    for i in l[tmp]:
        if check[i[0]] == 0:
            que.append(i[0])
            check[i[0]] = 1
            d[i[0]] = d[tmp] + i[1]
            count += 1
        else:
            pass
    if count >= n:
        break

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

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

N = int(input())
edge = [[] for i in range(N)]

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

D = [-1]*N 


def dfs(src, cost):
    D[src] = cost
    for e in edge[src]:
        if D[e[1]] == -1:
            dfs(e[1], cost + e[0])

def main():
    Q,K = map(int, input().split())
    dfs(K-1, 0)

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

if __name__ == '__main__':
    main()

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




import heapq
def dijkstra(s,n,edge):
    d = [float("inf")] * n 
    d[s] = 0
    q = [] 
    for e in edge[s]:
        heapq.heappush(q, e)
    
    while q:
        minedge = heapq.heappop(q)
        v = minedge[1]
        if d[v] < minedge[0]:
            continue 
        d[v] = minedge[0]
        for e in edge[v]:
            heapq.heappush(q, [e[0]+d[v], e[1]])

    return d

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

    Q,K = map(int, input().split())
    D = dijkstra(K-1, N, edge)

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

if __name__ == '__main__':
    main()

Solution (Python):

import sys 
input = sys.stdin.readline
from collections import deque
def solve():
  n = int(input())
  d = [[]*n for _ in range(n)]
  for i in range(n-1):
    a,b,c = (int(i) for i in input().split())
    d[a-1].append((b-1,c))
    d[b-1].append((a-1,c))
  q,k = (int(i) for i in input().split())
  
  d2 = [10**10]*n
  visit = [False]*n
  query = deque([(k-1,0)]) 
  while query:
    place,dist = query.pop()
    if visit[place]:
      continue
    else:
      visit[place] = visit
      d2[place] = dist
      for i in range(len(d[place])):
        np,nc = d[place][i]
        if not visit[np]:
          query.append((np,nc+dist))
  for i in range(q):
    x,y = (int(i) for i in input().split())
    print(int(d2[x-1] + d2[y-1]))

solve()

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

n = int(input())
graph = [list() for i in range(n+1)]

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

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

def dfs(pre, now, c):
    len_list[now] = min(len_list[now], len_list[pre] + c)

    while graph[now]:
        n, c = graph[now].pop()
        dfs(now, n, c)

len_list = [float("inf")] * (n + 1)
len_list[k] = 0
dfs(k, k, 0)

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

Solution (Python):
from collections import deque

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

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = deque([[v, T[K][v], K] for v in T[K].keys()])
for _ in range(N-1):
    v = queue.popleft()
    shortest_path[v[0]] = v[1]
    queue.extend([[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]])

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

Solution (Python):
import heapq
N = int(input())
node = [[] for _ in range(N)]
for _ in range(N-1):
  a,b,c = map(int,input().split())
  node[a-1].append([c,b-1])
  node[b-1].append([c,a-1])
Q,K = map(int,input().split())

flag = [True]*N
ques = [[0,K-1]]
D = [0]*N
while ques:
  d1,l1 = heapq.heappop(ques)
  if flag[l1]:
    flag[l1]=False
    D[l1] = d1
    for d2,l2 in node[l1]:
      if flag[l2]:
        heapq.heappush(ques,[d1+d2,l2])
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
from operator import itemgetter
sys.setrecursionlimit(10000000)

tmp = []
tree = []

def dfs(node, depth, fr):
    global tmp, tree
    tree[node] = (fr, depth)
    for i, c in tmp[node]:
        if i != fr:
            dfs(i, depth+c, node)

def main():
    global tmp, tree
    n = int(input().strip())
    tmp = [[] for _ in range(n)]
    tree = [0] * n
    for _ in range(n-1):
        a, b, c = map(int, input().strip().split())
        a -= 1
        b -= 1

        if b > a:
            a, b = b, a
        tmp[a].append((b, c))
        tmp[b].append((a, c))

    q, k = map(int, input().strip().split())
    k -= 1
    dfs(k, 0, -1)
    
    
    for _ in range(q):
        x, y = map(lambda x: x-1, map(int, input().strip().split()))
        print(tree[x][1] + tree[y][1])


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

N = int(input())

depth = [""] * N

lis = [0] * N

dic = {}

for i in range(N-1):

    a,b,c = map(int,input().split())

    a -= 1
    b -= 1

    if a not in dic:
        dic[a] = []
    if b not in dic:
        dic[b] = []

    dic[a].append([b,c])
    dic[b].append([a,c])

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

queue = deque([])
queue.append(K)
depth[K] = 0

while len(queue) > 0:

    now = queue.pop()

    if now not in dic:
        continue

    for bc in dic[now]:

        b = bc[0]
        c = bc[1]
        
        if depth[b] != "":
            continue

        depth[b] = depth[now] + 1
        lis[b] = lis[now] + c
        queue.append(b)

for i in range(Q):

    x,y = map(int,input().split())

    x -= 1
    y -= 1

    print (lis[x] + lis[y])

Solution (Python):

from collections import deque

def DFS(ls,start):
    que = deque([])
    que.append(start)
    visited = [0 for _ in range(len(ls))]

    while len(que):
        now = que.popleft()
        for nex in ls[now]:

            if visited[nex[0]]==0:
                que.append(nex[0])
                visited[nex[0]] = visited[now] + nex[1]

    return visited




def main():
    n = int(input())
    ls = [[] for _ in range(n+1)]
    for _ in range(n-1):
        a,b,c = map(int,input().split())
        ls[a].append([b,c])
        ls[b].append([a,c])
    q,k = map(int,input().split())
    x,y = [0 for _ in range(q)],[0 for _ in range(q)]
    for i in range(q):
        x[i],y[i] = map(int,input().split())
    
    memo = DFS(ls,k)

    for i in range(q):
        print(memo[x[i]]+memo[y[i]])
    
if __name__ == "__main__":
    main()

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

n=int(input())
dct=defaultdict(list)

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


q,k=map(int,input().split())
lk=[0]*(n)

def dfs(v,p,d):
  lk[v-1]=d

  for l in dct[v]:
    if l[0]==p or lk[l[0]-1]!=0:
      continue
    else:
      dfs(l[0],v,d+l[1])
  return

dfs(k,-1,0)



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

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

visited = [-1]*n
todo = deque()
visited[k] = 0
todo.append(k)

while todo:
    v = todo.pop()
    d = visited[v]
    for to, cost in tree[v]:
        if visited[to] == -1:
            visited[to] = d+cost
            todo.append(to)
            
ans = []
for _ in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    ans.append(visited[x] + visited[y])

print(*ans, sep="\n")

Solution (Python):
from collections import deque

N = int(input())
d_list = [[] for _ in range(N+1)]
costs = [0] * (N+1)
for _ in range(N-1):
  a, b, c = map(int, input().split())
  d_list[a].append((a, b, c))
  d_list[b].append((b, a, c))
Q, K = map(int, input().split())
que = deque([])
for e in d_list[K]:
  que.append(e)
while len(que) > 0:
  _from, _to,  _cost = que.popleft()
  costs[_to] += costs[_from] + _cost
  for e in d_list[_to]:
    if e[1] != _from:
      que.append(e)
for _ in range(Q):
  f, t = map(int, input().split())
  print(costs[f] + costs[t])

Solution (Python):
import sys

sys.setrecursionlimit(10**6)

input = sys.stdin.readline

n = int(input())

es = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    es[a].append((b, c))
    es[b].append((a, c))
ds = [0] * (n + 1)


def dfs(cur, prev, c):
    ds[cur] = ds[prev] + c
    for e, c in es[cur]:
        if e != prev:
            dfs(e, cur, c)


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

dfs(k, k, 0)
for _ in range(q):
    x, y = map(int, input().split())
    print(ds[x] + ds[y])

Solution (Python):
import sys

sys.setrecursionlimit(10**6)

input = sys.stdin.readline

n = int(input())
ls = [list(map(int, input().split())) for _ in range(n - 1)]

es = [[] for _ in range(n + 1)]
for a, b, c in ls:
    es[a].append((b, c))
    es[b].append((a, c))
ds = [0] * (n + 1)


def dfs(cur, prev, c):
    ds[cur] = ds[prev] + c
    for e, c in es[cur]:
        if e != prev:
            dfs(e, cur, c)


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

dfs(k, k, 0)
for x, y in qs:
    print(ds[x] + ds[y])

Solution (Python):

import sys
from collections import deque, defaultdict
import copy
import bisect

import math
import heapq
from itertools import product, permutations,combinations
import fractions

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

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

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

que = deque([])
que.append(K - 1)
dist = [-1 for _ in range(N)]
dist[K - 1] = 0
while len(que) > 0:
	node = que.popleft()
	for edge in tree[node]:
		if dist[edge[0]] == -1:
			que.append(edge[0])
			dist[edge[0]] = dist[node] + edge[1]

for i in range(Q):
	a, b = list(map(int, input().split()))
	print(dist[a - 1] + dist[b - 1])

Solution (Python):
import heapq as hp

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

Q, K = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(Q)]

INF = int(1E17)

D = [INF for _ in range(N)] 
D[K-1] = 0 
q = [] 
hp.heappush(q, (0, K-1))

while q:
    nd, np = hp.heappop(q) 
    if D[np] < nd: 
        continue
    for d, p in graph[np]:
        if D[p] > D[np] + d: 
            D[p] = D[np] + d
            hp.heappush(q, (D[p], p))

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

Solution (Python):
from collections import deque
n,*t=map(int,open(0).read().split())
con=[[] for _ in range(n)]
dist_f_k=[0]*n
l1,l2=t[:3*n-3],t[3*n-1:]

for a,b,c in zip(*[iter(l1)]*3):
	con[a-1].append((b-1,c))
	con[b-1].append((a-1,c))

k=t[3*n-2]
que=deque([k-1])
while que:
	cur=que.popleft()
	for nxt,dd in con[cur]:
		if dist_f_k[nxt]==0 and nxt!=k-1:
			que.append(nxt)
			dist_f_k[nxt]=dist_f_k[cur]+dd

for x,y in zip(*[iter(l2)]*2):
	print(dist_f_k[x-1]+dist_f_k[y-1])

Solution (Python):
def solve():
	from collections import deque
	n,*t=map(int,open(0).read().split())
	con=[[] for _ in range(n)]
	dist_f_k=[0]*n
	l1,l2=t[:3*n-3],t[3*n-1:]

	for a,b,c in zip(*[iter(l1)]*3):
		con[a-1].append((b-1,c))
		con[b-1].append((a-1,c))

	k=t[3*n-2]
	que=deque([k-1])
	while que:
		cur=que.popleft()
		for nxt,dd in con[cur]:
			if dist_f_k[nxt]==0 and nxt!=k-1:
				que.append(nxt)
				dist_f_k[nxt]=dist_f_k[cur]+dd

	for x,y in zip(*[iter(l2)]*2):
		print(dist_f_k[x-1]+dist_f_k[y-1])
		
if __name__=="__main__":
	solve()

Solution (Python):
from collections import deque
n,*t=map(int,open(0).read().split())
con=[[] for _ in range(n)]
dist_f_k=[0]*n

for a,b,c in zip(t[:3*n-3:3],t[1::3],t[2::3]):
	con[a-1].append((b-1,c))
	con[b-1].append((a-1,c))

k=t[3*n-2]
que=deque([k-1])
while que:
	cur=que.popleft()
	for nxt,dd in con[cur]:
		if dist_f_k[nxt]==0 and nxt!=k-1:
			que.append(nxt)
			dist_f_k[nxt]=dist_f_k[cur]+dd

for x,y in zip(t[3*n-1::2],t[3*n::2]):
	print(dist_f_k[x-1]+dist_f_k[y-1])

Solution (Python):
from collections import deque
n=int(input())
con=[[] for _ in range(n)]
dist_f_k=[0]*n

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

q,k=map(int,input().split())
que=deque([k-1])
while que:
	cur=que.popleft()
	for nxt,dd in con[cur]:
		if dist_f_k[nxt]==0 and nxt!=k-1:
			que.append(nxt)
			dist_f_k[nxt]=dist_f_k[cur]+dd

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

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


def dijkstra_heap(s, n, edge):
    
    d = [float("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


def main():
    N = int(input())

    edge = [[] for i 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_heap(K, N, edge)

    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):
def main():
    import sys
    input = sys.stdin.readline
    
    N = int(input())
    from collections import defaultdict
    D = defaultdict(list)
    for i in range(N-1):
        a,b,c = map(int,input().split())
        D[a].append([b,c])
        D[b].append([a,c])
        
    Q,K = map(int,input().split())
    fromK = [[0] for i in range(N+1)]
    
    visited = {}
    queue = [[K,0]]
    while queue != []:
        v,C = queue.pop()
        visited[v] = 1
        fromK[v] = C
        for i in D[v]:
            j,c = i
            if not j in visited:
                queue.append([j,C+c])
    for i in range(Q):
        x,y = map(int,input().split())
        print(fromK[x]+fromK[y])
    
    
main()

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

N = int(input())
E = [set() for _ in range(N)]
C = {}
for i in range(N-1):
  a,b,c = map(int,input().split())
  E[a-1].add(b-1)
  E[b-1].add(a-1)
  C[min(a-1,b-1)*N+max(a-1,b-1)] = c
  
Q,K = map(int,input().split())
K -= 1




Kcost = [0 for _ in range(N)]
def dfs(u,v):
  if v != -1:
    Kcost[u] = Kcost[v] + C[min(u,v)*N+max(u,v)]
  for t in E[u]:
    if t != K and Kcost[t] == 0:
      dfs(t,u)
dfs(K,-1)

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

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

N=int(input())
dp = [0]*N

E = []
for i in range(N):
    E.append([])

def dfs(cur,pre):
    for r,d in E[cur]:
        if r != pre:
            dp[r] = dp[cur] + d
            dfs(r,cur)


for i in range(N-1):
    x,y,d= list(map(int,input().split()))
    E[x-1].append((y-1,d))
    E[y-1].append((x-1,d))

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

dfs(K-1,-1)

for j in range(Q):
    s,g= list(map(int,input().split()))
    print(dp[s-1]+dp[g-1])

Solution (Python):
import sys
sys.setrecursionlimit(100002)
input=sys.stdin.readline
n=int(input())
graph=[{} for i in range(n)]
visited=[False]*n
for i in range(n-1):
    a,b,c=map(int,input().split())
    a-=1;b-=1
    graph[a][b]=c
    graph[b][a]=c
q,k=map(int,input().split())
dist=[0]*n
def dfs(chi,par,cost):
    dist[chi]=cost
    for i in graph[chi].keys():
        if visited[i]:continue
        if i==par:continue
        visited[i]=True
        dfs(i,chi,cost+graph[i][chi])
    return
dfs(k-1,-1,0)
for i in range(q):
    x,y=map(int,input().split())
    x-=1;y-=1
    print(dist[x]+dist[y])

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

N = int(input())

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

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

visited = [False] * N
visited[K-1] = True

distance = [-1]*N


def dfs(v, p, d):  
    distance[v-1] = d
    for i, c in G[v-1]:
        if visited[i-1] is False:
            if i == p:
                continue
            dfs(i, v, d+c)
    return


dfs(K, -1, 0)

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

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n=int(input())
    edges=[[] for _ in range(n)]
    for _ 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
    d=[INF]*n
    d[k]=0

    
    Q=[[k,0]]
    while(Q):
        v,dist=Q.pop()
        for u,cost in edges[v]:
            if d[u]>dist+cost:
                d[u]=dist+cost
                Q.append([u,d[u]])

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

resolve()

Solution (Python):
from collections import deque

N = int(input())

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

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

visited = [False] * N
visited[K-1] = True

distance = [-1]*N

que = deque([(K, 0)])
while que:
    cur, d = que.popleft()
    distance[cur-1] = d

    for nx, nd in G[cur-1]:
        if visited[nx-1] is False:
            visited[nx-1] = True
            que.append((nx, d+nd))

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

Solution (Python):
import sys
from collections import defaultdict
sys.setrecursionlimit(200000)
input = sys.stdin.readline

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

m = [set() for _ in range(N)]
c = {}
for x, y, z in L:
    m[x - 1].add(y - 1)
    m[y - 1].add(x - 1)

    if c.get(x - 1) == None:
        c[x - 1] = {}

    if c.get(y - 1) == None:
        c[y - 1] = {}

    c[x - 1][y - 1] = z
    c[y - 1][x - 1] = z

s = [None] * N
s[K - 1] = 0

def f(index, b):
    for v in m[index]:
        if s[v] == None:
            s[v] = b + c[index][v]
            f(v, s[v])
        else:
            if s[v] > b + c[index][v]:
                s[v] = b + c[index][v]
                f(v, s[v])

f(K - 1, 0)

for x, y in QL:
    print(s[x] + s[y])

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


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

dis=[None]*(n+1)

def set_dis(x,d):
    dis[x]=d
    for yy,dd in graph[x] :
        if dis[yy] is not None:
            continue
        set_dis(yy,dd+d)
set_dis(k,0)

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

Solution (Python):
from collections import deque
import sys
def main():
  def p(a,b):
    if a < b:
      return (a,b)
    else:
      return (b,a)
  input = sys.stdin.readline
  N = int(input())
  E = [[] for i in range(N)]
  C = {}
  D = [0] * N
  parent = [0]*N
  for i in range(N-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)
    C[p(a,b)] = c

  M, K = map(int, input().split())
  K -= 1
  parent[K] = K
  Q = deque()
  Q.append(K)

  while Q:
    u = Q.popleft()
    d = D[u]
    for v in E[u]:
      if parent[u] == v:
        continue
      parent[v] = u
      D[v] = d + C[p(u,v)]
      Q.append(v)

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

main()

Solution (Python):
from collections import deque

def main():
  def p(a,b):
    if a < b:
      return (a,b)
    else:
      return (b,a)
  input = open(0).readline
  N = int(input())
  E = [[] for i in range(N)]
  C = {}
  D = [0] * N
  parent = [0]*N
  for i in range(N-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)
    C[(a,b)] = c
    C[(b,a)] = c

  M, K = map(int, input().split())
  K -= 1
  parent[K] = K
  Q = deque()
  Q.append(K)

  while Q:
    u = Q.popleft()
    d = D[u]
    for v in E[u]:
      if parent[u] == v:
        continue
      parent[v] = u
      D[v] = d + C[(u,v)]
      Q.append(v)

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

main()

Solution (Python):
from collections import deque

def main():
  def p(a,b):
    if a < b:
      return (a,b)
    else:
      return (b,a)
  
  N = int(input())
  E = [[] for i in range(N)]
  C = {}
  D = [0] * N
  parent = [0]*N
  for i in range(N-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)
    C[p(a,b)] = c

  M, K = map(int, input().split())
  K -= 1
  parent[K] = K
  Q = deque()
  Q.append(K)

  while Q:
    u = Q.popleft()
    d = D[u]
    for v in E[u]:
      if parent[u] == v:
        continue
      parent[v] = u
      D[v] = d + C[p(u,v)]
      Q.append(v)

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

main()

Solution (Python):
from collections import deque

def main():
  def p(a,b):
    if a < b:
      return (a,b)
    else:
      return (b,a)
  input = open(0).readline
  N = int(input())
  E = [[] for i in range(N)]
  C = {}
  D = [0] * N
  parent = [0]*N
  for i in range(N-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)
    C[p(a,b)] = c

  M, K = map(int, input().split())
  K -= 1
  parent[K] = K
  Q = deque()
  Q.append(K)

  while Q:
    u = Q.popleft()
    d = D[u]
    for v in E[u]:
      if parent[u] == v:
        continue
      parent[v] = u
      D[v] = d + C[p(u,v)]
      Q.append(v)

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

main()

Solution (Python):
from collections import deque

N = int(input())
E = [[] for i in range(N)]
C = {}
D = [0] * N
parent = [0]*N
for i in range(N-1):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  E[a].append(b)
  E[b].append(a)
  C[(a,b)] = c
  C[(b,a)] = c
  
M, K = map(int, input().split())
K -= 1
parent[K] = K
Q = deque()
Q.append(K)

while Q:
  u = Q.popleft()
  d = D[u]
  for v in E[u]:
    if parent[u] == v:
      continue
    parent[v] = u
    D[v] = d + C[(u,v)]
    Q.append(v)

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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

n = getN()

vtxs = [[] for i in range(n)]
dist = [0 for i in range(n)]
visit = [0 for i in range(n)]

for i in range(n-1):
    a,b,c = getList()
    vtxs[a-1].append((b-1 ,c))
    vtxs[b-1].append((a-1 ,c))

ques, k = getList()

from collections import deque
q = deque([k-1])
visit[k-1] = 1
while(q):
    cur = q.popleft()
    cdist = dist[cur]
    for nx in vtxs[cur]:
        nxa, nxc = nx
        if visit[nxa] == 0:
            dist[nxa] = cdist + nxc
            visit[nxa] = 1
            q.append(nxa)

for i in range(ques):
    x, y = getList()
    print(dist[x-1] + dist[y-1])

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

class Node:
    def __init__(self, id):
        self.id = id
        self.link = []
        self.cost = []
        self.check = False

def main():
    N = int(input())
    
    nodes = [Node(i) for i in range(N+1)]

    for i in range(N-1):
        a, b, c = map(int, input().split())
        nodes[a].link.append(nodes[b])
        nodes[b].link.append(nodes[a])
        nodes[a].cost.append(c)
        nodes[b].cost.append(c)
    
    Q, K = map(int, input().split())

    q = deque()
    q.append((nodes[K], 0))
    nodes[K].check = True
    costs = [0] * (N+1)
    while len(q) > 0:
        node, cost = q.popleft()
        costs[node.id] = cost
        for i in range(len(node.link)):
            next_node = node.link[i]
            if not next_node.check:
                q.append((next_node, cost + node.cost[i]))
                next_node.check = True
    
    for i in range(Q):
        x, y = map(int, input().split())
        print(costs[x] + costs[y])
    

if __name__ == "__main__":
    main()

Solution (Python):
import collections
import heapq
def main():

    N = int(input())
    edges = collections.defaultdict(dict)
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        edges[a][b] = c
        edges[b][a] = c

    Q, K = map(int, input().split())
    dist = dict()
    cur = [[0, K]]
    while cur:
        d, a = heapq.heappop(cur)
        if a not in dist:
            dist[a] = d
            for b in edges[a]:
                if b not in dist:
                    heapq.heappush(cur, [d+edges[a][b], b])

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

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
def dfs(v,p,d):
    for i, j in tree[v]:
        if i != p:
            depth[i] = d + j
            dfs(i,v,d+j)

N = int(input())

tree = [[] for _ in range(N)]

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

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

depth = [0 for i in range(N)]
depth[K-1] = 0

dfs(K-1,-1,0)

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

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

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

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

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
N = int(input())

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

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

def dfs(s,pare):
    for i in graph[s]:
        if i.to != pare :
            dp[i.to] = dp[s] + i.cost
            dfs(i.to,s)
        else:
            continue 


Q,K = map(int,input().split())
dfs(K-1,-1)
for i in range(Q):
    x,y = map(int,input().split())
    print("{}".format(dp[x-1]+dp[y-1]))

Solution (Python):
N = int(input())
INF = float("inf")
es = [[] for _ in range(N)]
for i in range(N-1):
    a,b,c = map(int, input().split())
    a,b = a-1, b-1
    es[a].append((b,c))
    es[b].append((a,c))

Q, K = map(int, input().split())
xy = []
for i in range(Q):
    x,y = map(int, input().split())
    xy.append([x-1, y-1])

checked = [False] * N
d = [INF] * N
d[K-1] = 0

next_check = []
next_check.append(K-1)
while len(next_check):
    now = next_check.pop()
    for next,cost in es[now]:
        if not checked[next]:
            d[next] = min(d[next], d[now] + cost)
            checked[next] = True
            next_check.append(next)
    


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

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

N=int(input())

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

Q,K=map(int,input().split())
A=[list(map(int,input().split())) for i in range(Q)]


depth=[0 for i in range(N)]
depth[K-1]=0

def dfs(cur,p,d):
	for i,j in G[cur]:
		if i!=p:
			depth[i]=d+j
			dfs(i,cur,d+j)

dfs(K-1,-1,0)


for i,j in A:
	print(depth[i-1]+depth[j-1])

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

def main():
    N = int(input())
    X = [list(map(int,input().split())) for _ in range(N-1)]
    Q,K = map(int,input().split())
    Y = [list(map(int,input().split())) for _ in range(Q)]

    tree = [[] for _ in range(N)]
    dif = [10**15 for _ in range(N)]
    dif[K-1] = 0
    for i in range(N-1):
        tree[X[i][0]-1].append((X[i][1]-1,X[i][2]))
        tree[X[i][1]-1].append((X[i][0]-1,X[i][2]))

    queue = [K-1]
    while queue:
        a = queue.pop()
        for i in tree[a]:
            s,t = i[0],i[1]
            if dif[s] == 10**15:
                dif[s] = dif[a]+t
                queue.append(s)

    for i in range(Q):
        print(dif[Y[i][0]-1]+dif[Y[i][1]-1])

if __name__ == "__main__":
    main()