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,bisect,string,math,time,functools,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase

input=lambda: sys.stdin.readline().rstrip()

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True








class SegTree:

    def __init__(self,n,init_val=0,function=lambda a,b:a+b,ide=0):
        self.n=n
        self.ide_ele=ide_ele=ide
        self.num=num=2**(n-1).bit_length()
        self.seg=seg=[self.ide_ele]*2*self.num
        self.lazy=lazy=[self.ide_ele]*2*self.num
        self.segfun=segfun=function
        
        for i in range(n):
            self.seg[i+self.num-1]=init_val
        
        for i in range(self.num-2,-1,-1):
            self.seg[i]=self.segfun(self.seg[2*i+1],self.seg[2*i+2])
    
    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfun(self.seg[k*2+1],self.seg[k*2+2])
        
        
    def evaluate(k,l,r): 
        if lazy[k]!=0:
            node[k]+=lazy[k]
            if(r-l>1):
                lazy[2*k+1]+=lazy[k]//2
                lazy[2*k+2]+=lazy[k]//2

        lazy[k]=0
        
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfun(res,self.seg[p])
            if q&1 == 1:
                res = self.segfun(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfun(res,self.seg[p])
        else:
            res = self.segfun(self.segfun(res,self.seg[p]),self.seg[q])
        return res
    
    def find_min_index(self,p,q,m):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfun(res,self.seg[p])
            if q&1 == 1:
                res = self.segfun(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfun(res,self.seg[p])
        else:
            res = self.segfun(self.segfun(res,self.seg[p]),self.seg[q])
        return res


    def __str__(self):
        
        rt=self.seg[self.num-1:self.num-1+self.n]
        return str(rt)


ans=0


class Tree:
    def __init__(self,init=True):
        if init:
            self.stdin()
        return

    def stdin(self,inp_size=None):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1)
        return
    
    def listin(self,ls):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda x,y,z:x+z,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb in self.edges[c]:
                d=1
                if type(nb) is not int:
                    nb,d=nb
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x,func=lambda x:x+1,root_v=0):
        q=deque()
        q.append((-1,x))
        v=[None]*self.size
        v[x]=root_v
        et=[]
        while q:
            cb,ce=q.pop()
            et.append(ce)
            for nb in self.edges[ce]:
                if v[nb]==None:
                    q.append((nb,ce))
                    q.append((ce,nb))
                    v[nb]=func(v[ce])
        vid=[[-1,-1]for i in range(self.size)]
        for i,j in enumerate(et):
            if vid[j][0]==-1:
                vid[j][0]=i
            else:
                vid[j][1]=i
        return v,et,vid
    
    def LCA_init(self,depth,et):
        self.st=SegTree(self.size*2-1,func=min,ide=inf)
        for i,j in enumerate(et):
            self.st.update(i,j)
        self.LCA_init_stat==True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            depth,et,vid=self.EulerTour(root)
            self.LCA_init(depth,et)
        return self.st.query(x,y+1)
        

tr=Tree()
q,k=LI()

v=tr.dfs(k-1)

for i in range(q):
    x,y=LI_()
    print(v[x]+v[y])

Solution (Python):
import heapq
def dijkstra_heap(s,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

import sys
input = sys.stdin.readline
n = int(input())
edge = [[] for i in range(n)]
for i in range(n-1):
    x,y,z = map(int,input().split())
    edge[x-1].append([z,y-1]) 
    edge[y-1].append([z,x-1]) 

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

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

Solution (Python):
from sys import stdin
from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)
N = int(stdin.readline().rstrip())
adj = defaultdict(set)

for i in range(N-1):
    a,b,c = [int(x) for x in stdin.readline().rstrip().split()]
    adj[a].add((b,c))
    adj[b].add((a,c))
    
Q,K = [int(x) for x in stdin.readline().rstrip().split()]

visited = [False]*(N+1)
dist = [0]*(N+1)

def dfs(i,j):
    if visited[i]:
        return
    dist[i] = j
    visited[i] = True
    
    for node,d in adj[i]:
        dfs(node,d+j)
        
dfs(K,0)

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

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    edge=[[] for _ in range(N)]
    for _ in range(N-1):
        a,b,c=map(int1,input().split())
        c+=1
        edge[a].append((c,b))
        edge[b].append((c,a))
    
    Q,K=map(int,input().split())
    K-=1
    from heapq import heappop,heappush
    def dijkstra(start,n,edges):
        d=[INF]*n
        used=[False]*n
        d[start]=0
        used[start]=True
        edgelist=[]
        for edge in edges[start]:
            heappush(edgelist,edge)
        while edgelist:
            minedge=heappop(edgelist)
            if used[minedge[1]]:
                continue
            v=minedge[1]
            d[v]=minedge[0]
            used[v]=True
            for edge in edges[v]:
                if not used[edge[1]]:
                    heappush(edgelist,(edge[0]+d[v],edge[1]))
        return d
    
    d=dijkstra(K,N,edge)
    for _ in range(Q):
        x,y=map(int1,input().split())
        print(d[x]+d[y])

if __name__ == '__main__':
    main()

Solution (Python):
from queue import deque

n = int(input())
li = [[] for _ in range(n)]
length = {}
length_path = [0]*n

for i in range(n-1):
    u,v,w = map(int,input().split())
    u,v = u-1,v-1
    if u < v:
        length[(u,v)] = w
    else:
        length[(v,u)] = w
    li[u].append(v)
    li[v].append(u)

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

work_queue = deque([])
visited = [False]*n

work_queue.append(k)

while work_queue:
    now = work_queue.popleft()
    visited[now] = True
    for i in li[now]:
        if visited[i]:
            continue
        work_queue.append(i)
        visited[i] = True
        if now < i:
            length_path[i] = length_path[now]+length[(now,i)]
        else:
            length_path[i] = length_path[now]+length[(i,now)]

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

Solution (Python):
import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
n=int(input())
edges=[[] for i in range(n)]
dis=[-1]*n
for _ in range(n-1):
  a,s,d=map(int,input().split())
  a-=1;s-=1
  edges[a].append((s,d))
  edges[s].append((a,d))
q,k=map(int,input().split())
dis[k-1]=0
def dfs(now):
  for i,d in edges[now]:
    if dis[i]==-1:
      dis[i]=dis[now]+d
      dfs(i)
dfs(k-1)
for _ in range(q):
  a,s=map(int,input().split())
  print(dis[a-1]+dis[s-1])

Solution (Python):
import sys
import heapq

input = sys.stdin.readline


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

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

    dist = [None] * N
    h = [(0, K, -1)]
    while h:
        d0, node, parent = heapq.heappop(h)
        dist[node] = d0
        for d1, child in nb[node]:
            if child != parent:
                heapq.heappush(h, (d0 + d1, child, node))

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import heapq

input = sys.stdin.readline


def main():

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

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

    dist = [2 ** 62] * N
    h = [(0, K, -1)]
    while h:
        d0, node, parent = heapq.heappop(h)
        if d0 >= dist[node]:
            continue
        dist[node] = d0
        for d1, child in nb[node]:
            if child != parent and d0 + d1 < dist[child]:
                heapq.heappush(h, (d0 + d1, child, node))

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


if __name__ == "__main__":
    main()

Solution (Python):


data=int(input())

abc=[list(map(int,input().split())) for _ in [0]*(data-1)]

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

array1=[list(map(int,input().split())) for _ in [0]*q]

k-=1

tree=[[] for _ in [0]*data]

dist=[-1]*data

dist[k]=0

[tree[a-1].append([b-1,c]) for a,b,c in abc]

[tree[b-1].append([a-1,c]) for a,b,c in abc]

q=[k]

while(q):
	qq=[]
	for i in q:
		for j,k in tree[i]:
			if dist[j]<0:
				dist[j]=dist[i]+k
				qq.append(j)
	q=qq

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

Solution (Python):


data=int(input())

abc=[list(map(int,input().split())) for _ in [0]*(data-1)]

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

array1=[list(map(int,input().split())) for _ in [0]*q]

k-=1

tree=[[] for _ in [0]*data]

dist=[-1]*data

dist[k]=0

[tree[a-1].append([b-1,c]) for a,b,c in abc]

[tree[b-1].append([a-1,c]) for a,b,c in abc]

q=[k]

while(q):
	qq=[]
	for i in q:
		for j,k in tree[i]:
			if dist[j]<0:
				dist[j]=dist[i]+k
				qq.append(j)
	q=qq

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

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

def distance(k):
    seen = set()
    dis_l = {}
    d = 0
    stack = deque([[tree[k], d]])
    flag = True
    while stack:
        connect, d = stack.popleft()
        for i in connect:
            if i[0] not in seen:
                seen.add(i[0])
                d += i[1]
                dis_l[i[0]] = d
                stack.append([tree[i[0]], d])
                d -= i[1]
    return dis_l

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

Solution (Python):
n = int(input())
abc = [list(map(int, input().split())) for i in range(n-1)]
q,k = map(int, input().split())
tree = [list() for i in range(n+1)]
visited = [0] * (n+1)
dist = [0] * (n+1)
for a,b,c in abc:
  tree[a].append((b,c))
  tree[b].append((a,c))
stack = [k]
visited[k] = 1
while stack:
  now = stack.pop()
  for NEXT,d in tree[now]:
    if not visited[NEXT]:
      visited[NEXT] = 1
      dist[NEXT] = dist[now] + d
      stack.append(NEXT)
for i in range(q):
  x,y = map(int, input().split())
  print(dist[x]+dist[y])

Solution (Python):
import heapq


def dijkstra(start, n_nodes, edges):
    dist = [float("inf")] * n_nodes
    dist[start] = 0
    q = [(dist[start], start)]
    heapq.heapify(q)

    while q:
        d, i = heapq.heappop(q)
        if d > dist[i]:
            continue

        for w, j in edges[i]:
            if d + w < dist[j]:
                dist[j] = d + w
                heapq.heappush(q, (dist[j], j))

    return dist


def main():
    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((c, b))
        edges[b].append((c, a))

    Q, K = map(int, input().split())
    K -= 1
    query = []
    for _ in range(Q):
        x, y = map(int, input().split())
        x -= 1
        y -= 1
        query.append((x, y))
    dist = dijkstra(K, N, edges)
    for x, y in query:
        ans = dist[x] + dist[y]
        print(ans)


main()

Solution (Python):
import queue
n = int(input())

abc = [[] for i in range(n+1)]

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

Q,k = map(int,input().split())
xy = [[int(i) for i in input().split()] for j in range(Q)]

q = queue.Queue()

q.put(k)

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

while not q.empty():
    tmp = q.get()
    for i in range(len(abc[tmp])):
        
        
        num = abc[tmp][i][0]
        if path[num] != -1:
            continue
        else:
            path[num] = path[tmp] + abc[tmp][i][1]
            q.put(num)
            
for i in range(Q):
    print(path[xy[i][0]]+path[xy[i][1]])

Solution (Python):
import queue
import sys
sys.setrecursionlimit(10**7)
n = int(input())

abc = [[] for i in range(n+1)]

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

Q,k = map(int,input().split())
xy = [[int(i) for i in input().split()] for j in range(Q)]

q = queue.Queue()

q.put(k)

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

def dfs(p):
    for i in range(len(abc[p])):
        num = abc[p][i][0]
        if path[num] != -1:
            continue
        else:
            path[num] = path[p] + abc[p][i][1]
            dfs(num)

dfs(k)

for i in range(Q):
    print(path[xy[i][0]]+path[xy[i][1]])

Solution (Python):
import queue
n = int(input())

abc = [[] for i in range(n+1)]

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

Q,k = map(int,input().split())
xy = [[int(i) for i in input().split()] for j in range(Q)]

q = queue.Queue()

q.put(k)

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

while not q.empty():
    tmp = q.get()
    for i in range(len(abc[tmp])):
        
        
        num = abc[tmp][i][0]
        if path[num] != -1:
            continue
        else:
            path[num] = path[tmp] + abc[tmp][i][1]
            q.put(num)
            
for i in range(Q):
    print(path[xy[i][0]]+path[xy[i][1]])

Solution (Python):
import sys
sys.setrecursionlimit(500000)
 
N = int(input())
ABC = [list(map(int, input().split())) for i in range(N-1)]
Q, K = map(int, input().split())
D = [0] * (N+1)
L = [[] for i in range(N+1)]
for a, b, c in ABC:
    L[a].append([b, c])
    L[b].append([a, c])
 
 
def dfs(n, np):
    for nc in L[n]:
        if nc[0] == np:
            continue
        else:
            D[nc[0]] = D[n] + nc[1]
            dfs(nc[0], n)
 
 
dfs(K, 0)
for i in range(Q):
    x, y = map(int, input().split())
    print(D[x] + D[y])

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

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


def dfs(s):
    d = [-1] * n
    d[s] = 0
    stack = [s]

    while stack:
        u = stack.pop()
        for v, c in adj[u]:
            if d[v] == -1:
                d[v] = d[u] + c
                stack.append(v)

    return d


d = dfs(k - 1)

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

Solution (Python):
import sys
sys.setrecursionlimit(500000)
 
N = int(input())
ABC = [list(map(int, input().split())) for i in range(N-1)]
Q, K = map(int, input().split())
D = [0] * (N+1)
L = [[] for i in range(N+1)]
for a, b, c in ABC:
    L[a].append([b, c])
    L[b].append([a, c])
 
 
def dfs(n, np):
    for nc in L[n]:
        if nc[0] == np:
            continue
        else:
            D[nc[0]] = D[n] + nc[1]
            dfs(nc[0], n)
 
 
dfs(K, 0)
for i in range(Q):
    x, y = map(int, input().split())
    print(D[x] + D[y])

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


def dfs(start, dist, distance_list, explored):
    for node, cost in tree[start]:
        if explored[node] is False:
            explored[node] = True
            distance_list[node] = dist + cost
            dfs(node, distance_list[node], distance_list, explored)
    return distance_list


n = int(input())
tree = [[] for _ in range(n)]
distance = [float('inf') 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
query = []
distance[k] = 0

for _ in range(q):
    x, y = map(int, input().split())
    query.append((x-1, y-1))

XX = [False for _ in range(n)]
XX[k] = True

X = dfs(k, 0, distance, explored=XX)

for i, j in query:
    print(X[i] + X[j])

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(20000000)
from collections import defaultdict
n = int(input())

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

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


dist = [-1 for _ in range(n+1)]
is_checked = [False for _ in range(n+1)]
def dfs(num, cur_dist):
    global dist, is_checked
    for next_num, d in edges[num]:
        if not is_checked[next_num]:
            is_checked[next_num] = True
            dist[next_num] = cur_dist + d
            dfs(next_num, cur_dist + d)
dist[k] = 0
is_checked[k] = True
dfs(k, 0)

ans = []
for _ in range(q):
    x, y = map(int, input().split())
    ans.append(str(dist[x] + dist[y]))
print("\n".join(ans))

Solution (Python):
N = int(input())
import heapq
def dijkstra_heap(s):
    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


edge = [[] for i in range(N)]
for i in range(N-1):
    x,y,z = map(int,input().split())
    edge[x-1].append([z,y-1])
    edge[y-1].append([z,x-1])
Q, K = map(int, input().split())
result = dijkstra_heap(K-1)
for i in range(Q):
    x, y = map(int, input().split())
    print(abs(result[x-1]-result[K-1])+abs(result[y-1]+result[K-1]))

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

n = int(input())
from collections import defaultdict
abc = [tuple(map(int,input().split())) for i in range(n-1)]
es = [[] for i in range(n)]
for a,b,c in abc:
    a,b = a-1,b-1
    es[a].append((b,c))
    es[b].append((a,c))

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

dist = [-1]*n

def dfs(v=0,parent=-1,d=0):
    for next_v,dd in es[v]:
        if dist[next_v] == -1:
            dist[next_v] = d + dd
            dfs(next_v,v,dist[next_v])

dist[k-1] =0
dfs(k-1,-1,0)
ans=[]
for x,y in xy:
    x,y=x-1,y-1
    ans.append(dist[x]+dist[y])

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

Solution (Python):
import sys
import heapq
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt
INF = 1 << 60
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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 dijkstra_heap(s,edge):
    
    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 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 bfs(queue):
    visited = [0] * n
    while queue:
        
        node = queue.popleft()
        
        current = node[0]
        if visited[current] == 0:
            new_cost = node[1]
            cost = node[2]
            cost += new_cost
            dist[current] = min(dist[current], cost)
            visited[current] = 1
            for i in tree[current]:
                queue.append([i[0], i[1], cost])

n = int(input())
tree = [[] for i 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())
k -= 1
dist = [INF] * n

queue = deque([[k, 0, 0]])

bfs(queue)

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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
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((c, b))
    edges[b].append((c, a))
INF = float('inf')


def dfs(v, parent, distance):
    dist[v] = distance
    for d, v2 in edges[v]:
        if parent == v2:
            continue
        dfs(v2, v, distance+d)


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

Solution (Python):
import sys
import heapq
input = sys.stdin.readline
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((c, b))
    edges[b].append((c, a))
INF = float('inf')


def dijkstra(init_v):
    dist = [INF]*n
    dist[init_v] = 0
    tasks = [(0, init_v)]
    while tasks:
        d, v = heapq.heappop(tasks)
        if dist[v] < d:
            continue
        for d2, v2 in edges[v]:
            if dist[v2] <= dist[v]+d2:
                continue
            dist[v2] = dist[v]+d2
            heapq.heappush(tasks, ((dist[v2], v2)))
    return dist


q, k = map(int, input().split())
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
from collections import deque
input = sys.stdin.readline
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((c, b))
    edges[b].append((c, a))
INF = float('inf')


def bfs(init_v):
    dist = [INF]*n
    dist[init_v] = 0
    tasks = deque([(0, init_v)])
    while tasks:
        d, v = tasks.popleft()
        for d2, v2 in edges[v]:
            if dist[v2] <= dist[v]+d2:
                continue
            dist[v2] = dist[v]+d2
            tasks.append((dist[v2], v2))
    return dist


q, k = map(int, input().split())
dist = bfs(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
input = sys.stdin.readline
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((c, b))
    edges[b].append((c, a))
INF = float('inf')


def dfs(init_v):
    dist = [INF]*n
    dist[init_v] = 0
    tasks = [(0, init_v)]
    while tasks:
        d, v = tasks.pop()
        for d2, v2 in edges[v]:
            if dist[v2] <= dist[v]+d2:
                continue
            dist[v2] = dist[v]+d2
            tasks.append((dist[v2], v2))
    return dist


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

Solution (Python):
from heapq import heapify, heappush, heappop

import sys
sys.setrecursionlimit(100000000)

n = int(input())
G = [[] for _ in range(n + 1)]

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

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














queue = []
d = [None for _ in range(n + 1)]
heappush(queue, (0, K, -1))
while len(queue) > 0:
    dist, index, parent = heappop(queue)
    if d[index] is not None:
        continue
    d[index] = dist
    for (u, cvu) in G[index]:
        if u == parent:
            continue
        heappush(queue, (dist + cvu, u, index))

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