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
sys.setrecursionlimit(1000000)

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

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

Qn, K = list(map(int, input().split(" ")))

Q = []
for i in range(Qn):
    Q.append(list(map(int, input().split(" "))))

distance = [0]*(N+1)

def dfs(k, parent, dist):
    for n, x in M[k]:
        if n != parent:
            distance[n] = dist + x
            dfs(n, k, dist + x)

dfs(K, 0, 0)
for q in Q:
    print(distance[q[0]] + distance[q[1]])

Solution (Python):
import sys
from collections import deque




def main():
    n = int(input())
    adj = [[] for u in range(n+1)]
    for i in range(n - 1):
        a, b, c = map(int, input().split())
        adj[a].append((b, c))
        adj[b].append((a, c))

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

    Q = deque([(k, 0, 0)])
    while Q:
        u, parent, dist = Q.popleft()
        Q.extend([(v, u, dist+w) for v, w in adj[u] if v != parent])
        d[u] = dist

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


main()

Solution (Python):
import sys
from collections import deque





def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


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


def read_str():
    return input()


def main():
    n = read_int()
    adj = [[] for u in range(n+1)]
    for i in range(n - 1):
        a, b, c = map(int, input().split())
        adj[a].append((b, c))
        adj[b].append((a, c))

    d = [0] * (n+1)
    q, k = read_int_list()

    
    Q = deque([(k, 0, 0)])
    while Q:
        u, parent, dist = Q.popleft()
        for v, w in adj[u]:
            if v != parent:
                Q.append((v, u, dist+w))
        d[u] = dist

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


main()

Solution (Python):
from sys import stdin
input = stdin.readline
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  import queue
  dist=[-1]*N
  dist[K]=0
  que=queue.Queue()
  que.put(K)
  while que.qsize():
    label=que.get()
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que.put(i)
  return dist
 
N=int(input())
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  path[a-1]+=[(b-1,c)]
  path[b-1]+=[(a-1,c)]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,path,N)
for i in range(Q):
  print(distance[xy[i][0]-1]+distance[xy[i][1]-1])

Solution (Python):
from sys import stdin
input = stdin.readline
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  from collections import deque
  dist=[-1]*N
  dist[K]=0
  que=deque()
  que.append(K)
  while len(que):
    label=que.popleft()
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que+=[i]
  return dist
 
N=int(input())
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  path[a-1]+=[(b-1,c)]
  path[b-1]+=[(a-1,c)]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,path,N)
for i in range(Q):
  print(distance[xy[i][0]-1]+distance[xy[i][1]-1])

Solution (Python):
from sys import stdin
input = stdin.readline
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  from collections import deque
  dist=[-1]*N
  dist[K]=0
  que=deque()
  que.append(K)
  while que:
    label=que.popleft()
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que+=[i]
  return dist
 
N=int(input())
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  path[a-1].append((b-1,c))
  path[b-1].append((a-1,c))
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,path,N)
for i in range(Q):
  print(distance[xy[i][0]-1]+distance[xy[i][1]-1])

Solution (Python):
from sys import stdin
input = stdin.readline
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  from collections import deque
  dist=[-1]*N
  dist[K]=0
  que=deque()
  que.append(K)
  while que:
    label=que.popleft()
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que+=[i]
  return dist
 
N=int(input())
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  path[a-1]+=[(b-1,c)]
  path[b-1]+=[(a-1,c)]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,path,N)
for i in range(Q):
  print(distance[xy[i][0]-1]+distance[xy[i][1]-1])

Solution (Python):
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  from collections import deque
  dist=[-1]*N
  dist[K]=0
  que=deque()
  que.append(K)
  while que:
    label=que.popleft()
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que+=[i]
  return dist
 
N=int(input())
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  path[a-1]+=[[b-1,c]]
  path[b-1]+=[[a-1,c]]
Q,K=map(int,input().split())
distance=BFS(K-1,path,N)
for i in range(Q):
  x,y=map(int,input().split())
  print(distance[x-1]+distance[y-1])

Solution (Python):
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  from collections import deque
  dist=[-1]*N
  dist[K]=0
  que=deque()
  que.append(K)
  while que:
    label=que.popleft()
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que+=[i]
  return dist
 
N=int(input())
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  path[a-1]+=[[b-1,c]]
  path[b-1]+=[[a-1,c]]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,path,N)
for i in range(Q):
  print(distance[xy[i][0]-1]+distance[xy[i][1]-1])

Solution (Python):
from sys import stdin
input = stdin.readline
from collections import deque
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  dist=[-1]*N
  dist[K]=0
  que=deque()
  que.append(K)
  while que:
    label=que.popleft()
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que+=[i]
  return dist
 
N=int(input())
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  path[a-1]+=[[b-1,c]]
  path[b-1]+=[[a-1,c]]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,path,N)
for i in range(Q):
  print(distance[xy[i][0]-1]+distance[xy[i][1]-1])

Solution (Python):


N=int(input())
a=[]
b=[]
c=[]

for idx in range(0,N-1,1):
    mozir=input()
    hyo=mozir.split(' ')
    a.append(int(hyo[0])-1)
    b.append(int(hyo[1])-1)
    c.append(int(hyo[2]))

mozir=input()
hyo=mozir.split(' ')
Q=int(hyo[0])
K=int(hyo[1])-1



keiro=[]
for idx in range(0,N,1):
    keiro.append([])
    
for idx in range(0,N-1,1):
    keiro[a[idx]].append((b[idx],c[idx]))
    keiro[b[idx]].append((a[idx],c[idx]))

fare=[None]*N

fare[K]=0
shirabe=[(K,0)]
while shirabe :
    tugi_shirabe=[]
    for (node,tmpcost) in shirabe:
        for (kouho,c) in keiro[node]:
            if fare[kouho]==None:
                fare[kouho]=tmpcost+c
                tugi_shirabe.append((kouho,tmpcost+c))
                
    shirabe=tugi_shirabe



for idx in range(0,Q,1):
    mozir=input()
    hyo=mozir.split(' ')
    x=int(hyo[0])-1
    y=int(hyo[1])-1
    print(fare[x]+fare[y])

Solution (Python):

N = int(input())
nodes = []
for i in range(N - 1):
    tmp = input()
    nodes.append([int(a) for a in tmp.split()])
tmp = input()
M, top = [int(a) for a in tmp.split()]
querys = []
for i in range(M):
    tmp = input()
    querys.append([int(a) for a in tmp.split()])



nodes_dic = [[] for i in range(N + 1)]
for n in nodes:
    frm, to, dist = n
    nodes_dic[frm].append([to, dist])
    nodes_dic[to].append([frm, dist])


dist_dic = [-1 for i in range(N + 1)]
dist_dic[top] = 0
stack = [top]
while len(stack) > 0:
    n = stack.pop()
    for a in nodes_dic[n]:
        to, dist = a
        if dist_dic[to] >= 0:
            continue
        dist_dic[to] = dist_dic[n] + dist
        stack.append(to)


for q in querys:
    print(dist_dic[q[0]] + dist_dic[q[1]])

Solution (Python):



import sys
from collections import deque

N=input()

a=[[] for i in range(N+1)]

for i in range(N-1):
	x,y,z=list(map(int,raw_input().split()))
	a[x].append((y,z))
	a[y].append((x,z))



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


b=[]
for i in range(Q):
	b.append(map(int, raw_input().split()))





F=(N+1)*[0]


q=deque()


dist=[0 for i in range(N+1)]


length=0

q.append(K)
while len(q)!=0:
	v=q.popleft()
	F[v]=1
	for u,length in a[v]:
		if F[u]==0:
			q.append(u)
			dist[u]=dist[v]+length





for x in range(len(b)):
	print dist[ b[x][0] ]+ dist[ b[x][1] ]

Solution (Python):



import sys
sys.setrecursionlimit(200000)

N=input()


a=[[] for i in range(N+1)]


for i in range(N-1):
	x,y,z=list(map(int,raw_input().split()))
	a[x].append((y,z))
	a[y].append((x,z))


	

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


b=[]
for i in range(Q):
	b.append(map(int, raw_input().split()))





F=(N+1)*[0]


dist=[0 for i in range(N+1)]



def dfs(v,p,d):
	F[v]=1
	dist[v]=d
	for i,j in a[v]:
		
		if F[i]==0:
			
			dfs(i,v,d+j)


dfs(K,-1,0)

for x in range(len(b)):
	print dist[ b[x][0] ]+ dist[ b[x][1] ]

Solution (Python):

import sys


N=input()


a=[[] for i in range(N+1)]


for i in range(N-1):
	x,y,z=list(map(int,raw_input().split()))
	a[x].append((y,z))
	a[y].append((x,z))


	

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


b=[]
for i in range(Q):
	b.append(map(int, raw_input().split()))





F=(N+1)*[0]


S=[]


dist=[0 for i in range(N+1)]


S.append(K)
former_v=0
v=0
while len(S) != 0:
	v=S.pop()
	
	if F[v]==0:
		F[v]=1

		for u,length in a[v]:
			if F[u]==0:
				S.append(u)
				dist[u]=dist[v]+length
				





for x in range(len(b)):

	print dist[ b[x][0] ]+ dist[ b[x][1] ]

Solution (Python):
import sys
sys.setrecursionlimit(int(1e5+10))

def search_dist(g, dist, e):
    for b, c in g.get(e):
        if dist[b] is not None:
            continue
        dist[b] = dist[e] + c
        search_dist(g, dist, b)

def main():
    g = {}
    N = int(input())
    for i in range(N+1):
        g[i] = []
    for _ in range(N-1):
        a, b, c = list(map(int, input().split(' ')))
        g[a] += [(b, c)]
        g[b] += [(a, c)]
    Q, K = list(map(int, input().split(' ')))
    dist = [None]*(N+1)
    dist[K] = 0
    search_dist(g, dist, K)
    cood = []
    for _ in range(Q):
        cood.append(list(map(int, input().split(' '))))

    for x, y in cood:
        print(dist[x]+dist[y])

if __name__ == '__main__':
    main()

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

tree = dict()
cost = dict()

N = int(input())
for i in range(N - 1):
    a, b, c = map(int, input().split())
    if a in tree:
        tree[a].append(b)
    else:
        tree[a] = []
        tree[a].append(b)
    if b in tree:
        tree[b].append(a)
    else:
        tree[b] = []
        tree[b].append(a)
    cost[(a, b)] = c
    cost[(b, a)] = c
starts = []
ends = []
Q, K = map(int, input().split())
for i in range(Q):
    x, y = map(int, input().split())
    starts.append(x)
    ends.append(y)

depth = [1000000000000000 for i in range(N)]

def dps(position, total_cost):
    if depth[position - 1] > total_cost:
        depth[position - 1] = total_cost
    for next_position in tree[position]:
        if depth[next_position - 1] == 1000000000000000:
            dps(next_position, depth[position - 1] + cost[(position, next_position)])

depth[K-1] = 0
dps(K, 0)

for start, end in zip(starts, ends):
    print(depth[start - 1] + depth[end - 1])

Solution (Python):
import sys
sys.setrecursionlimit(int(1e5+10))
N = int(input())
edge = [[] for i in range(N)]
depth = [0 for i in range(N)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    a, b = a-1, b-1
    edge[a].append((b,c))
    edge[b].append((a,c))
Q, K = map(int, input().split())
K = K - 1

def dfs(v, p, c):
    depth[v] = c
    for nv, nc in edge[v]:
        if nv != p:
            dfs(nv, v, c + nc)
            
dfs(K, -1, 0)

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

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
 
sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**9
mod = 10**9 + 7
 
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
 
 
def main():
    n = I()
    e = collections.defaultdict(list)
    for _ in range(n-1):
        a,b,c = LI()
        e[a].append((b,c))
        e[b].append((a,c))
 
    
    def search(s):
        d = collections.defaultdict(lambda: inf)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True
 
            for uv, ud in e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))
 
        return d
 
    q,k = LI()
 
    d = search(k)
    r = []
    for _ in range(q):
        x,y = LI()
        r.append(d[x]+d[y])
 
    return '\n'.join(map(str,r))
 
 
 
print(main())

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

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

depth = [0] * (n + 1)
def dfs(v, p, d):
    depth[v] = d
    for to, cost in tree[v]:
        if to != p:
            dfs(to, v, d + cost)

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

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

Solution (Python):
n = int(input())
path = [[] for i in range(n)]

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


q, k = map(int, input().split())
distance = [None] * n
distance[k-1] = 0
queue = [k-1]
while(len(queue)):
    p = queue.pop()
    for i,c in path[p]:
        if(distance[i] == None):
            distance[i] = distance[p] + c
            queue.append(i)

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

Solution (Python):
import sys;sys.setrecursionlimit(int(1e7))
from sys import stdin
from collections import deque

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

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

depth = [None]*(N+1)
def DFS(v,p,d):
    depth[v] = d
    for e in tree[v]:
        if e[0] != p:
            DFS(e[0], v, d + e[1])
DFS(K,0,0)

for i in range(Qn):
    print(depth[XY[i][0]] + depth[XY[i][1]])

Solution (Python):
import sys;sys.setrecursionlimit(int(1e7))
from sys import stdin
from collections import deque

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

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

dist = [-1]*(N+1)
dist[K] = 0
Q = deque()
Q.append(K)
while len(Q):
    p = Q.popleft()
    for q,c in tree[p]:
        if dist[q] != -1: continue
        dist[q] = dist[p]+c
        Q.append(q)

for i in range(Qn):
    print(dist[XY[i][0]] + dist[XY[i][1]])

Solution (Python):
import sys;sys.setrecursionlimit(int(1e7))
from collections import deque

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

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

dist = [-1]*(N+1)
dist[K] = 0
Q = deque()
Q.append(K)
while len(Q):
    p = Q.popleft()
    for q,c in tree[p]:
        if dist[q] != -1: continue
        dist[q] = dist[p]+c
        Q.append(q)

for i in range(Qn):
    print(dist[XY[i][0]] + dist[XY[i][1]])

Solution (Python):
import sys;sys.setrecursionlimit(int(1e7))
from collections import deque

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

tree = [[] for _ in range(N+1)]
for abc in ABC:
    tree[abc[0]].append((abc[1],abc[2]))
    tree[abc[1]].append((abc[0],abc[2]))

dist = [-1]*(N+1)
dist[K] = 0
Q = deque()
Q.append(K)
while len(Q):
    p = Q.popleft()
    for q,c in tree[p]:
        if dist[q] != -1: continue
        dist[q] = dist[p]+c
        Q.append(q)

for i in range(Qn):
    print(dist[XY[i][0]] + dist[XY[i][1]])

Solution (Python):
import sys;sys.setrecursionlimit(int(1e7))

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

tree = [[] for _ in range(N+1)]
depth = [None]*(N+1)
for abc in ABC:
    tree[abc[0]].append((abc[1],abc[2]))
    tree[abc[1]].append((abc[0],abc[2]))

def DFS(v,p,d):
    depth[v] = d
    for e in tree[v]:
        if e[0] != p:
            DFS(e[0], v, d + e[1])

DFS(K,0,0)

for i in range(Q):
    print(depth[XY[i][0]] + depth[XY[i][1]])

Solution (Python):
import sys;sys.setrecursionlimit(int(1e7))

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

tree = [[] for _ in range(N+1)]
depth = [None]*(N+1)
for abc in ABC:
    tree[abc[0]].append([abc[1],abc[2]])
    tree[abc[1]].append([abc[0],abc[2]])

def DFS(v,p,d):
    depth[v] = d
    for e in tree[v]:
        if e[0] != p:
            DFS(e[0], v, d + e[1])

DFS(K,0,0)

for i in range(Q):
    print(depth[XY[i][0]] + depth[XY[i][1]])

Solution (Python):
import sys;sys.setrecursionlimit(int(1e7))

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

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

for abc in ABC:
    tree[abc[0]].append([abc[1],abc[2]])
    tree[abc[1]].append([abc[0],abc[2]])

def DFS(v,p,d):
    tree[v][0].append(d)
    for e in tree[v]:
        if e[0] != p:
            DFS(e[0], v, d + e[1])

DFS(K,0,0)

for i in range(Q):
    print(tree[XY[i][0]][0][2] + tree[XY[i][1]][0][2])

Solution (Python):
import sys;sys.setrecursionlimit(int(1e7))

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

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

for abc in ABC:
    tree[abc[0]].append([abc[1],abc[2]])
    tree[abc[1]].append([abc[0],abc[2]])

def DFS(v,p,d):
    for e in tree[v]:
        e.append(d)
        if e[0] != p:
            DFS(e[0], v, d + e[1])

DFS(K,0,0)

for i in range(Q):
    print(tree[XY[i][0]][0][2] + tree[XY[i][1]][0][2])

Solution (Python):
import sys;sys.setrecursionlimit(int(1e7))

N = int(input())

tree = [[] for _ in range(N+1)]
depth = [None]*(N+1)

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

for abc in ABC:
    tree[abc[0]].append((abc[1],abc[2]))
    tree[abc[1]].append((abc[0],abc[2]))

def DFS(v,p,d):
    depth[v] = d
    for e in tree[v]:
        if e[0] != p:
            DFS(e[0], v, d + e[1])

DFS(K,0,0)

for i in range(Q):
    print(depth[XY[i][0]] + depth[XY[i][1]])

Solution (Python):
import sys;sys.setrecursionlimit(int(1e7))

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

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

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

def DFS(v,p,d):
    depth[v] = d
    for e in tree[v]:
        if e.to == p:
            continue
        DFS(e.to, v, d + e.cost)
DFS(K,-1,0)

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

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**9
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    e = collections.defaultdict(list)
    for _ in range(n-1):
        a,b,c = LI()
        e[a].append((b,c))
        e[b].append((a,c))

    
    def search(s):
        d = collections.defaultdict(lambda: inf)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d

    q,k = LI()

    d = search(k)
    r = []
    for _ in range(q):
        x,y = LI()
        r.append(d[x]+d[y])

    return '\n'.join(map(str,r))



print(main())

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

INF = float('inf')
ds = [INF for i in range(N)]
ds[K] = 0
visited = [0 for i in range(N)]
q = [K]
heapq.heapify(q)
while q:
    now = heapq.heappop(q)
    visited[now] = 1
    for to,cost in es[now]:
        ds[to] = min(ds[to], ds[now]+cost)
        if visited[to]: continue
        heapq.heappush(q,to)

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

Solution (Python):
import collections

def bfs(tree, s, distance):
    queue = collections.deque([s])
    distance[s] = 0

    while queue:
        v = queue.popleft()
        v_c = distance[v]
        for node, cost in tree[v]:
            if distance[node] == -1:
                distance[node] = v_c + cost
                queue.append(node)

N = int(input())

Tree = collections.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))

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

distance = collections.defaultdict(lambda : -1)
bfs(Tree, k, distance)

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

Solution (Python):
import sys

stdin = sys.stdin

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

n = ni()
g = []
for i in range(n+1): g.append([])

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

q,k = na()

def dfs(cur, pre, g, par, dw, w):
    dw[cur] = w
    par[cur] = pre
    for e in g[cur]:
        if e[0] != pre:
            dfs(e[0], cur, g, par, dw, w + e[1])

par = [-1] * (n+2)
dw = [-1] * (n+2)
from asyncio import Queue
qs = Queue()
qs.put_nowait(k)
dw[k] = 0

while not qs.empty():
    cur = qs.get_nowait()
    for e in g[cur]:
        if e[0] != par[cur]:
            par[e[0]] = cur
            dw[e[0]] = dw[cur] + e[1]
            qs.put_nowait(e[0])




for z in range(q):
    x, y = na()
    print(dw[x] + dw[y])

Solution (Python):
def Q4(x):
    N = x[0][0]  
    edge = x[1:N][:]  
    Q = x[N][0]  
    K = x[N][1]  
    query = x[N + 1:][:]  

    
    tree = list(range(N))  
    for idx in range(N):
        tree[idx] = []

    for idx in range(len(edge)):
        
        
        a = edge[idx][0] - 1
        b = edge[idx][1] - 1
        c = edge[idx][2]
        tree[a].append([b, c])
        tree[b].append([a, c])

    
    dist = [0 for i in range(N)]  
    isVisit = [False for i in range(N)]  
    queue = [K - 1] 
    isVisit[K - 1] = True

    while queue:
        u = queue.pop()
        for p in tree[u]:
            v, w = map(int, p)
            if not isVisit[v]:
                isVisit[v] = True
                dist[v] = dist[u] + w
                queue.append(v)

    for q in query:
        print(dist[q[0] - 1] + dist[q[1] - 1])
        
N=int(input())
edge = [[int(i) for i in input().split()] for i in range(N-1)]
Q , K = (int(i) for i in input().split())
query = [[int(i) for i in input().split()] for i in range(Q)]
l = [[N]]+edge+[[Q,K]]+query
Q4(l)

Solution (Python):
import sys
x = input()
d = {}
dist = {}
for i in range(1, x+1):
    d[i] = []
    dist[i] = 0
for i in range(x-1):
    num1, num2, num3 = map(int, sys.stdin.readline().split())
    d[num1].append((num2, num3))
    d[num2].append((num1, num3))

q, k = map(int, raw_input().split())
vis = set()
vis.add(k)
current = [k]
newnode = []
while True:
    for i in range(len(current)):
        for j in range(len(d[current[i]])):
            if d[current[i]][j][0] not in vis:
                dist[d[current[i]][j][0]] = dist[current[i]]+d[current[i]][j][1]
                vis.add(d[current[i]][j][0])
                newnode.append(d[current[i]][j][0])
    if len(newnode) == 0:
        break
    current = []
    current = newnode
    newnode = []

for i in range(q):
    num1, num2 = map(int, sys.stdin.readline().split())
    hold = 0
    hold1 =0
    print dist[num1] + dist[num2]

Solution (Python):
import sys
import collections

sys.setrecursionlimit(int(1e7))

def dfs(node, parent, distance):
    depth[node] = distance
    for next_node, cost in Tree[node]:
        if next_node != parent:
            dfs(next_node, node, distance + cost)

N = int(input())

Tree = collections.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))

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

depth = {}
dfs(k, -1, 0)

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

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
n=int(input())
g=[[] for _ in range(n)]
for _ in range(n-1):
    a,b,c=map(int,input().split())
    g[a-1].append((b-1,c))
    g[b-1].append((a-1,c))
q,k=map(int,input().split())
d=[-1]*n
def f(k,c):
    d[k]=c
    for i,v in g[k]:
        if d[i]==-1:
            f(i,c+v)
f(k-1,0)
for _ in range(q):
    x,y=map(int,input().split())
    print(d[x-1]+d[y-1])

Solution (Python):
import queue
n=int(input())
r=[[] for i in range(n)]
d=[[] for i in range(n)]

for i in range(n-1):
    line=input().split()
    a=int(line[0])-1
    b=int(line[1])-1
    c=int(line[2])
    r[a].append(b)
    r[b].append(a)
    d[a].append(c)
    d[b].append(c)

line=input().split()
q=int(line[0])
k=int(line[1])-1

dist=[-1 for i in range(n)]

qd=queue.Queue()
qn=queue.Queue()
qd.put(0)
qn.put(k)

while not qn.empty():
    dd=qd.get()
    nn=qn.get()
    dist[nn]=dd
    for i in range(len(r[nn])):
        if dist[r[nn][i]]!=-1:
            continue
        qd.put(dd+d[nn][i])
        qn.put(r[nn][i])

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

Solution (Python):
from collections import deque

N = int(input())
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
    ai, bi, ci = map(int, input().split())
    edges[ai].append((bi, ci))
    edges[bi].append((ai, ci))
Q, K = map(int, input().split())

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







que = deque()
que.append(K); distance[K] = 0
while len(que):
    a = que.popleft()
    for b, c in edges[a]:
        if distance[b] == -1:
            distance[b] = c + distance[a]
            que.append(b)



for _ in range(Q):
    s, e = map(int, input().split())
    print(distance[s] + distance[e])

Solution (Python):
N = int(input())
g = {i: [] for i in range(1, N+1)}    

l = [0] * (N + 1)

for i 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())

stack = [K]

while len(stack):
    v = stack.pop()
    for c,ln in g[v]:
        if l[c] != 0:
            continue
        l[c] = l[v] + ln
        stack.append(c)

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

Solution (Python):
n = int(input())
edges = [[] for _ in range(n + 1)]
for a, b, c in (map(int, input().split()) for _ in range(n - 1)):
    edges[a].append((c, b))
    edges[b].append((c, a))
q, k = map(int, input().split())
stack = [(0, k, None)]
costs = [0] * (n + 1)
while stack:
    c, p, a = stack.pop()
    costs[p] = c
    stack.extend((c + c2, p2, p) for c2, p2 in edges[p] if p2 != a)
print('\n'.join(map(str, (costs[x] + costs[y] for x, y in (map(int, input().split()) for _ in range(q))))))