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 heapq

N = int(input())

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

def dijkstra(s):
  hq = [(0, s)]
  heapq.heapify(hq)
  cost = [float('inf')] * N
  cost[s] = 0
  while hq:
    c, v = heapq.heappop(hq)
    if c > cost[v]:
      continue
    for d, u in Tree[v]:
      tmp = d + cost[v]
      if tmp < cost[u]:
        cost[u] = tmp
        heapq.heappush(hq, (tmp, u))
  return cost

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

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

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

Q,s = map(int,input().split())
from heapq import heapify,heappush,heappop
D_INF = 10**15
d = [D_INF]*(N+1)
d[s] = 0
que = []
heapify(que)
heappush(que,(d[s],s))

while(len(que)):
    time,place = heappop(que)
    if time > d[place]:
        continue
    for i in range(0,len(adj_list[place]),1):
        if d[adj_list[place][i][0]] > time + adj_list[place][i][1]:
            d[adj_list[place][i][0]] = time + adj_list[place][i][1]
            heappush(que,(d[adj_list[place][i][0]],adj_list[place][i][0]))


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

for i in range(len(ans)):
    print(ans[i])

Solution (Python):
from collections import deque

N=int(input())

E={i:{} for i in range(1,N+1)}

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

Q,K=map(int,input().split())
inf=float("inf")
Dist=[inf]*(N+1)
Dist[K]=0
X=deque([K])

while X:
    u=X.popleft()
    for v in E[u]:
        if Dist[v]==inf:
            X.append(v)
            Dist[v]=Dist[u]+E[u][v]

T=[0]*Q
for i in range(Q):
    x,y=map(int,input().split())
    T[i]=Dist[x]+Dist[y]

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

Solution (Python):
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict 
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  
  
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright






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

queue= deque([ [k,l[0],l[1]] for l in G[k] ] )

dist=[-1]*n ; dist[k]=0
while queue:
    pre, now, kati = queue.pop()
    
    dist[now]= dist[pre]+kati
    for to,katin in G[now]:
        if to!= pre:
            queue.appendleft([now,to,katin ])

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

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
c = [-1]*n
c[k] = 0
stack = [k]
while stack:
    cur = stack.pop()
    for next_,cost in g[cur]:
        if c[next_]<0:
            c[next_] = c[cur]+cost
            stack.append(next_)

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

Solution (Python):
from collections import deque

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

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

d = [-1] * n
d[k] = 0
q = deque()
q.append([k, 0])
while q:
    f, cc = q.pop()
    for t, nc in e[f]:
        if d[t] == -1:
            d[t] = cc + nc
            q.append([t, d[t]])

for i in range(m):
    f, t = map(int,input().split())
    f -= 1
    t -= 1
    print(d[f] + d[t])

Solution (Python):
from collections import deque

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

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

d = [-1] * n
d[k] = 0
q = deque()
q.append([k, 0])
while q:
    f, cc = q.pop()
    for t, nc in e[f]:
        if d[t] == -1:
            d[t] = cc + nc
            q.append([t, d[t]])

for i in range(m):
    f, t = map(int,input().split())
    f -= 1
    t -= 1
    print(d[f] + d[t])

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

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())
K -= 1
query = [tuple(int(x) for x in input().split()) for _ in range(Q)]

        
seen = {K} 
v = [K]
distfromK =[0] * N
while len(v) != 0:  
    for nv in graph[v[0]]:
        if nv[0] in seen:
            continue
        distfromK[nv[0]] = distfromK[v[0]] + nv[1]
        v.append(nv[0])
        seen.add(nv[0])
    v.pop(0)

for q in query:
    print(distfromK[q[0]-1]+distfromK[q[1]-1])

Solution (Python):

from heapq import heappop,heappush

icase=0
if icase==0:
    n=int(input())
    g=[[] for i in range(n)]
    for i in range(n-1):
        ai,bi,ci=map(int,input().split())
        g[ai-1].append((bi-1,ci))
        g[bi-1].append((ai-1,ci))
if icase==1:
    n=5
    g=[[(1, 1), (2, 1)], [(0, 1), (3, 1)], [(0, 1), (4, 1)], [(1, 1)], [(2, 1)]]
if icase==2:
    n=7
    g=[[(1, 1), (2, 3), (3, 5), (4, 7), (5, 9), (6, 11)], [(0, 1)], [(0, 3)], [(0, 5)], [(0, 7)], [(0, 9)], [(0, 11)]]

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

hq=[]
heappush(hq,(0,k)) 

inf=float("INF")
dist=[inf]*n
dist[k]=0
while len(hq)>0:
    dd,state = heappop(hq)

    for v,dv in g[state]:

        if dist[v]>dist[state]+dv:
            dist[v]=dist[state]+dv
            heappush(hq,(dist[v],v))


for i in range(q):
    xi,yi=map(int,input().split())
    print(dist[xi-1]+dist[yi-1])

Solution (Python):
import heapq
import sys

input = sys.stdin.readline

def dijkstra_heap(s,edge,n):
    
    d = [10**20] * 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 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,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):
import sys
import queue

n=int(input())

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

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

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

xy=[]

for i in range(q):
  xy.append(list(map(int,input().split())))


distance=[0 for i in range(n)]
seen=[0 for i in range(n)]

que=queue.Queue()

que.put(k)
seen[k-1]=1

while not que.empty():
  c=que.get()
  for aa,cc in clis[c-1]:
    if seen[aa-1]==0:
      distance[aa-1]=distance[c-1]+cc
      seen[aa-1]=1
      que.put(aa)

for i in range(q):
  print(distance[xy[i][0]-1]+distance[xy[i][1]-1])

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())
def NIJIGEN(H): return [list(input()) for i in range(H)]
def bfs(place,dis):
  for i in tree[place]:
    a,b=i
    if a not in finish:
      finish.add(a)
      disli[a]=dis+b
      bfs(a,dis+b)
N=INT()
tree=[[] for _ in range(N)]
for i in range(N-1):
  a,b,c=MAP()
  tree[a-1].append([b-1,c])
  tree[b-1].append([a-1,c])
Q,K=MAP()
disli=[0 for i in range(N)]
finish=set([K-1])
bfs(K-1,0)
for i in range(Q):
  a,b=MAP()
  print(disli[a-1]+disli[b-1])

Solution (Python):
from collections import deque
n = int(input())
edges = [[]*n 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())
k -= 1
d = deque([k])
visited = [False]*n
visited[k] = True
distance_from_k = [0]*n
while d:
    p = d.popleft()
    for child, c in edges[p]:
        if visited[child]:
            continue
        visited[child] = True
        d.append(child)
        distance_from_k[child] += distance_from_k[p] + c


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

Solution (Python):
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())

def solve():
    N = INT()
    adj = [[] for _ in range(N)]
    for i in range(N-1):
        a, b, c = MAP()
        adj[a-1].append([b-1, c])
        adj[b-1].append([a-1, c])

    Q, K = MAP()
    K -= 1

    def dijkstra(K, adj):
        
        d = [inf]*N
        d[K] = 0
        que = []
        heappush(que, K)

        while que:
            v = heappop(que)
            for b, c in adj[v]:
                if d[b] > d[v] + c:
                    d[b] = d[v] + c
                    heappush(que, b)
        return d

    d = dijkstra(K, adj)
    for i in range(Q):
        x, y = MAP()
        print(d[x-1]+d[y-1])

if __name__ == '__main__':
    solve()

Solution (Python):
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())

def solve():
    N = INT()
    adj = [[] for _ in range(N)]
    for i in range(N-1):
        a, b, c = MAP()
        adj[a-1].append([b-1, c])
        adj[b-1].append([a-1, c])

    Q, K = MAP()
    K -= 1

    d = [inf]*N
    d[K] = 0
    que = []
    heappush(que, K)

    while que:
        v = heappop(que)
        for b, c in adj[v]:
            if d[b] > d[v] + c:
                d[b] = d[v] + c
                heappush(que, b)

    for i in range(Q):
        x, y = MAP()
        print(d[x-1]+d[y-1])

if __name__ == '__main__':
    solve()

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

def dijkstra(s):
  dist = [float('inf')]*N
  dist[s] = 0
  num = [0]*N
  num[s] = 1
  q = [[0, s]]
  heapq.heapify(q)
  while q:
    c, u = heapq.heappop(q)
    if dist[u] < c:
      continue
    for v, weight in graph[u]:
      if dist[v] > dist[u] + weight:
        dist[v] = dist[u] + weight
        num[v] = num[u]
        heapq.heappush(q, [dist[v], v])
      elif dist[v] == dist[u] + weight:
        num[v] += num[u]
  return dist, num

dist, _ = dijkstra(K-1)

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

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())

from collections import deque
from heapq import heappop, heappush
def main():
        

    def dijkstra(k):
        def push(v, x):
            if dist[v] <= x:
                return
            dist[v] = x
            heappush(q, (x, v))

        inf = 10**18
        dist = [inf]*n
        q = []
        push(k, 0)
        while q:
            x, v = heappop(q)
            if x > dist[v]:
                continue
            for nv, c in g[v]:
                push(nv, x+c)
        return dist

    n = ii()
    g = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b, c = mi()
        a -= 1
        b -= 1

        g[a].append((b, c))
        g[b].append((a, c))
    q, k = mi()
    k -= 1
    dist = dijkstra(k)
    for i in range(q):
        a, b = mi()
        a -= 1
        b -= 1
        print(dist[a]+dist[b])


if __name__ == '__main__':
    main()

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

length=[-1]*(N+1)
length[K]=0

import heapq
q=[[tmp[1], tmp[0], K] for tmp in links[K]]
heapq.heapify(q)
while q:
  tmp=heapq.heappop(q)
  length[tmp[1]]=tmp[0]+0
  for x in links[tmp[1]]:
    if tmp[2]!=x[0]:
      heapq.heappush(q, [tmp[0]+x[1], x[0], tmp[1]])

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

Solution (Python):
from collections import deque
def bfs(start, g, visited):
    q = deque([])
    k_neibs = g[start]
    visited[start] = (0,start)
    for neib, dist in k_neibs:
        q.append((neib, neib)) 
        visited[neib] = (dist, neib) 

    while q:
        curr_node, root_pare = q.popleft()
        for next_node, dist in g[curr_node]:
            if visited[next_node] != (-1,-1): continue
            curr_dist = visited[curr_node][0]
            visited[next_node] = (curr_dist+dist, root_pare)
            q.append((next_node, root_pare))


def main():
    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())
    visited = [(-1,-1)] * (n+1) 
    bfs(k, g, visited)

    ansl = []
    for _ in range(q):
        x,y = map(int, input().split())
        xd, xp = visited[x]
        yd, yp = visited[y]
        
        if xp == yp:
            ans = xd+yd
            ansl.append(ans)
        else:
            ans = xd+yd
            ansl.append(ans)

    for a in ansl: print(a)

if __name__ == "__main__":
    main()

Solution (Python):
import sys,math,collections,itertools
input = sys.stdin.readline

N=int(input())
tree = [[] for i in range(N+1)]

for _ in range(N-1):
    a,b,c=list(map(int,input().split()))
    tree[a].append([b,c])
    tree[b].append([a,c])
Q,K=list(map(int,input().split()))
    
memo = [-1]*(N+1)
q = collections.deque([K])
memo[K]=0
while q:
    now = q.pop()
    for direct,cost in tree[now]:
        if memo[direct]== -1:
            memo[direct]=memo[now]+cost
            q.append(direct)
for _ in range(Q):
    a,b=map(int,input().split())
    ans =memo[a]+memo[b]
    print(ans)

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    G = [[] for _ in range(N)] 
    for _ in range(N - 1):
        a, b, c = LI()
        G[a-1].append((b - 1, c))
        G[b-1].append((a - 1, c))
    Q, K = LI()
    K -= 1

    dist = [-1] * N
    dist[K] = 0
    que = collections.deque()
    que.append(K)
    while que:
        c = que.popleft()
        for n, l in G[c]:
            if dist[n] == -1:
                dist[n] = dist[c] + l
                que.append(n)

    for _ in range(Q):
        x, y = LI_()
        ans = dist[x] + dist[y]
        print(ans)

if __name__ == '__main__':
    resolve()

Solution (Python):
import sys,math,collections,itertools
input = sys.stdin.readline

N=int(input())
tree = [[] for i in range(N+1)]

for _ in range(N-1):
    a,b,c=list(map(int,input().split()))
    tree[a].append([b,c])
    tree[b].append([a,c])
Q,K=list(map(int,input().split()))
    
memo = [-1]*(N+1)
q = collections.deque([K])
memo[K]=0
while q:
    now = q.pop()
    for direct,cost in tree[now]:
        if memo[direct]== -1:
            memo[direct]=memo[now]+cost
            q.append(direct)
for _ in range(Q):
    a,b=map(int,input().split())
    ans =memo[a]+memo[b]
    print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(200000)

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

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

bit = [0 for _ in range(n)]
depth = [0 for _ in range(n)]
def dfs(v,d=0):
    bit[v] = 1
    depth[v] = d
    for j,k in tree[v]:
        if bit[j]==0:
            dfs(j,d+k)
dfs(k)

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

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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

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

def dijkstra(start):
    dist = [INF for _ in range(N)]
    visited = [False for _ in range(N)] 
    q = [(0, start)]
    dist[start] = 0
    while len(q) > 0:
        v = heapq.heappop(q)
        a = v[1]
        if visited[a]:
            continue
        visited[a] = True
        for u in adj[a]:
            w = u[0]
            b = u[1]
            if dist[a] + w < dist[b]: 
                dist[b] = dist[a] + w
                heapq.heappush(q, (dist[b], b))
    return dist

dist = dijkstra(K)

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

Solution (Python):
from collections import deque

N=int(input())
G=[{} for _ in range(N+1)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  G[a][b]=G[b][a]=c
  
def bfs(s):
    seen = [0 for i in range(N+1)]
    d = [0 for i in range(N+1)]
    cross = []
    todo = deque()
    seen[s]=1
    todo.append(s)
    while 1:
      if len(todo)==0:break
      a = todo.popleft()
      for b in G[a].keys():
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + G[a][b]
    return d

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

Solution (Python):
n = int(raw_input())
import collections
adj = collections.defaultdict(list)
for _ in range(n-1):
	u,v,w = map(int,raw_input().split())
	adj[u].append((v,w))
	adj[v].append((u,w))

dist =  {}
qq,k = map(int, raw_input().split())
vis = set([])
q = collections.deque([(k,0)])
while(q):
	u, c = q.popleft()
	dist[u]  = c
	for v,w in adj[u]:
		if v not in vis: 
			vis.add(v)
			q.append((v,w+c))
for _ in range(qq):
	u,v = map(int, raw_input().split())
	print dist[u] + dist[v]

Solution (Python):
import sys

def BFS(K,edges,N):
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a]+=[(b,c)]
    roots[b]+=[(a,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.append(i)
  return dist
      
      
a = []
edge = []
for l in sys.stdin:
    a.append(l.split())
V = int(a[0][0])
for i in range(V-1):
  buf = [int(a[i+1][0])-1, int(a[i+1][1])-1, int(a[i+1][2])]
  edge.append(buf)
n = int(a[V][0])
s = int(a[V][1])-1
ques = []
for i in range(n):
  buf = [int(a[V+i+1][0])-1, int(a[V+i+1][1])-1]
  ques.append(buf)
dist = BFS(s, edge, V)
for a, b in ques:
  res = dist[a] + dist[b]
  print(res)

Solution (Python):





import math
import fractions
import sys
import bisect
import heapq  
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    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 power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod



def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


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)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

n = ir()
maps = [[] for i in range(n)]
for i in range(n-1):
    a,b,c = lr()
    maps[a-1].append([b-1,c])
    maps[b-1].append([a-1,c])
Q,k  = lr()
k-=1
ans = [inf for i in range(n)]
visited = [False for i in range(n)]
visited[k] = True
q = [[k,0]]
q = deque(q)

while q:
    nown, dist = q.popleft()
    for nn, d in maps[nown]:
        if visited[nn] == False:
            ans[nn] = min(ans[nn], dist+d)
            q.append([nn, dist+d])
            visited[nn] = True
for i in range(Q):
    x,y = lr()
    x-=1
    y-=1
    print(ans[x]+ans[y])

Solution (Python):
import collections

n = int(input())
route = {i + 1 : {} for i in range(n)}
for i in range(n - 1):
    a, b, c = map(int, input().split())
    route[a][b] = c
    route[b][a] = c
q, k = map(int, input().split())
queue = collections.deque([k])
length = [0] * (n + 1)
while queue:
    search = queue.popleft()
    pairs = []
    for i, j in route[search].items():
        queue.append(i)
        length[i] = length[search] + j
        pairs.append([search, i])
    for i, j in pairs:
        del route[i][j]
        del route[j][i]
for i in range(q):
    x, y = map(int, input().split())
    print(length[x] + length[y])

Solution (Python):
import sys
from math import log2
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10**6)


def main():
    """
    Kの指定があるのに気づかずダブリングでLCA求めちゃった・・・！
    https://algo-logic.info/lca/
    勉強になったから良しとする。ポイントとして
    1. parents[k][u]の求め方がまず再帰
    2. LCAでまず深さを揃えるとこも2べき（必ずfor文はint(log2(N))まで回すこと！）
    3. ダブリングは祖先が一致しない時だけ更新
    を押さえとけば自力で再現できそう？
    """
    N = int(input())
    repn = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b, c = map(int, input().split())
        repn[a - 1].append((b - 1, c))
        repn[b - 1].append((a - 1, c))
    depth = [-1] * N
    dist = [0] * N
    parents = [[-1] * N for _ in range(int(log2(N)) + 3)]  

    def dfs(u):
        for v, c in repn[u]:
            if depth[v] != -1: continue
            depth[v] = depth[u] + 1
            dist[v] = dist[u] + c
            parents[0][v] = u
            dfs(v)

    depth[0] = 0
    dfs(0)

    for k in range(int(log2(N)) + 2):
        for u in range(N):
            if parents[k][u] < 0:
                parents[k + 1][u] = -1
            else:
                parents[k + 1][u] = parents[k][parents[k][u]]

    def doubling(u, v):
        if depth[u] < depth[v]: u, v = v, u
        for k in range(int(log2(N)) + 1):
            if ((depth[u] - depth[v]) & (1 << k)):
                u = parents[k][u]
                k += 1
        if u == v: return u
        for k in range(int(log2(N)) + 1, -1, -1):
            if parents[k][u] != parents[k][v]:
                u = parents[k][u]
                v = parents[k][v]
        return parents[0][u]

    Q, K = map(int, input().split())
    for _ in range(Q):
        u, v = map(int, input().split())
        lca1 = doubling(u - 1, K - 1)
        lca2 = doubling(K - 1, v - 1)
        d1 = dist[u - 1] + dist[K - 1] - dist[lca1] * 2
        d2 = dist[K - 1] + dist[v - 1] - dist[lca2] * 2
        print(d1 + d2)



if __name__ == "__main__":
    main()

Solution (Python):






from heapq import heappush, heappop
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append((c, b))
    graph[b].append((c, a))
q, k = map(int, input().split())
queries = []
for _ in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    queries.append((x, y))


def dijkstra_with_heap(graph, start, v):
    distance = [float('infinity')] * v
    distance[start] = 0
    stack = [[0, start]] 
    while stack:
        _, vertex = heappop(stack)
        edges = graph[vertex]
        for d, t in edges:
            if d + distance[vertex] < distance[t]:
                distance[t] = d + distance[vertex]
                heappush(stack, (d, t))
    return distance


distance = dijkstra_with_heap(graph, k - 1, n)

for x, y in queries:
    ans = distance[x] + distance[y]
    print(ans)

Solution (Python):
from collections import defaultdict


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int()
    G = defaultdict(list)
    for _ in range(N-1):
        a, b, c = read_ints()
        G[a].append((b, c))
        G[b].append((a, c))
    Q, K = read_ints()

    dist = [0]*(N+1)
    stack = [(None, 0, K)]
    while stack:
        parent, base_d, node = stack.pop()
        for child, d in G[node]:
            if child != parent:
                dist[child] = base_d+d
                stack.append((node, base_d+d, child))

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


if __name__ == '__main__':
    solve()

Solution (Python):
import networkx as nx

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

G = nx.Graph()

for a, b, c in ABC:
    G.add_edge(a - 1, b - 1, weight=c)


dist = nx.shortest_path_length(G, K - 1, weight="weight", method="bellman-ford")

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

Solution (Python):
import networkx as nx

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

G = nx.Graph()

for a, b, c in ABC:
    G.add_edge(a - 1, b - 1, weight=c)


dist = nx.shortest_path_length(G, K - 1, weight='weight')

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

Solution (Python):
import networkx as nx

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

G = nx.Graph()

for a, b, c in ABC:
    G.add_edge(a - 1, b - 1, weight=c)

pred, dist = nx.dijkstra_predecessor_and_distance(G, K - 1)

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