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
import os
from collections import defaultdict
adj = defaultdict(list)
vis =[0 for i in range(1000000)]
dis =[0 for i in range(1000000)]


def dfs(u, p):
	for v, w in adj[u]:
		if v==p:
			continue
		dis[v]=dis[u]+w
		dfs(v, u)

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

	q, k = map(int , input().split())
	sys.setrecursionlimit(1000000)
	dfs(k , 0)
	for i in range(q):
		x, y  =map(int , input().split())
		
		print(dis[x]+dis[y])




if __name__ == "__main__":
	main()

Solution (Python):
import sys
import os
from collections import defaultdict
adj = defaultdict(list)
vis =[0 for i in range(1000000)]
dis =[0 for i in range(1000000)]
def dfs(u, p):
	for v, w in adj[u]:
		if v==p:
			continue
		dis[v]=dis[u]+w
		dfs(v, u)

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

	q, k = map(int , input().split())
	sys.setrecursionlimit(1000000)
	dfs(k , 0)
	for i in range(q):
		x, y  =map(int , input().split())
		print(dis[x]+dis[y])




if __name__ == "__main__":
	main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)
N=int(input())
l=[-1]*N
tree=[[] for i in range(N)]
for i in range(N-1):
   A,B,C=list(map(int,input().split()))
   A-=1;B-=1
   tree[A].append((B,C))
   tree[B].append((A,C))
Q,V=list(map(int,input().split()))
def DFS(now,past,dis):
   l[now]=dis
   for i in tree[now]:
      if i[0]==past:
         continue
      elif l[i[0]] == -1:
         DFS(i[0],now,dis+i[1])
DFS(V-1,-1,0)
for i in range(Q):
   s,e=list(map(int,input().split()))
   s-=1;e-=1
   print(l[s]+l[e])

Solution (Python):
def main():
    from collections import defaultdict
    from heapq import heappop, heappush
    N = int(input())
    edge = defaultdict(list)
    length = defaultdict(lambda : defaultdict(lambda : 10**20))
    
    for i in range(N-1):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
        if b<a:
            a,b = b,a
        length[a][b] = c
    Q,K = map(int,input().split())
    K -= 1
    cost = [0]*N
    length[K][K] = 0
    targets = [(0,K)]
    cost = [10**18]*N
    cost[K] = 0
    visited = [False]*N
    while targets:
        c,t = heappop(targets)
        if visited[t]:
            continue
        cost[t] = c
        visited[t] = True
        for v in edge[t]:
            if cost[v] > cost[t] + length[min(t,v)][max(t,v)]:
                heappush(targets,(cost[t] + length[min(t,v)][max(t,v)],v))

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

    print('\n'.join(map(str,out)))







main()

Solution (Python):
from collections import defaultdict,deque
import sys
finput=lambda: sys.stdin.readline().strip()

def main():
  n=int(finput())
  edges=[tuple(map(int,finput().split())) for _ in range(n-1)]
  q,k=map(int,finput().split())
  xy=[tuple(map(int,finput().split())) for _ in range(q)]
  ed=defaultdict(deque)
  wt=defaultdict(int)
  for e in edges:
    ed[e[0]].append(e[1])
    ed[e[1]].append(e[0])
    wt[(e[0],e[1])]=e[2]
    wt[(e[1],e[0])]=e[2]
  stack=deque([k])
  cv=stack[0]
  dist=defaultdict(int)
  while stack:
    while ed[cv]:
      if cv!=k:
        if ed[cv][-1]==stack[-1]:
          ed[cv].pop()
          if not ed[cv]:
            break
      stack.append(cv)
      cv=ed[cv].pop()
      dist[cv]=dist[stack[-1]]+wt[(stack[-1],cv)]
    cv=stack.pop()
  for que in xy:
    print(dist[que[0]]+dist[que[1]])

if __name__=='__main__':
    main()

Solution (Python):

from collections import defaultdict,deque
import sys
finput=lambda: sys.stdin.readline().strip()

def main():
  n=int(finput())
  edges=[tuple(map(int,finput().split())) for _ in range(n-1)]
  q,k=map(int,finput().split())
  xy=[tuple(map(int,finput().split())) for _ in range(q)]
  
  stack=[-1]*(n+1)
  stack[k]=0
  ed=defaultdict(list)
  wt=defaultdict(int)
  for e in edges:
    ed[e[0]].append(e[1])
    ed[e[1]].append(e[0])
    wt[(e[0],e[1])]=e[2]
    wt[(e[1],e[0])]=e[2]
  ce=deque([(k,x) for x in ed[k]])
  ne=deque()
  while True:
    while ce:
      e=ce.pop()
      stack[e[1]]=stack[e[0]]+wt[e]
      for v in ed[e[1]]:
        if stack[v]<0:
          ne.append((e[1],v))
    if not ne:
      break
    ce.extend(ne)
    ne.clear()
  
  for que in xy:
    print(stack[que[0]]+stack[que[1]])

if __name__=='__main__':
    main()

Solution (Python):
from collections import defaultdict,deque
n=int(input())
edges=[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)]

stack=[-1]*(n+1)
stack[k]=0
ed=defaultdict(list)
wt=defaultdict(int)
for e in edges:
  ed[e[0]].append(e[1])
  ed[e[1]].append(e[0])
  wt[(e[0],e[1])]=e[2]
  wt[(e[1],e[0])]=e[2]
ce=deque([(k,x) for x in ed[k]])
ne=deque()
while True:
  while ce:
    e=ce.pop()
    stack[e[1]]=stack[e[0]]+wt[e]
    for v in ed[e[1]]:
      if stack[v]<0:
        ne.append((e[1],v))
  if not ne:
    break
  ce.extend(ne)
  ne.clear()

for que in xy:
  print(stack[que[0]]+stack[que[1]])

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    Q, K, *XY = map(int, read().split())
    K -= 1

    stack = deque([K])
    dist = [INF] * N
    dist[K] = 0
    while stack:
        v = stack.pop()
        for nv, cost in G[v]:
            if dist[nv] == INF:
                dist[nv] = dist[v] + cost
                stack.append(nv)

    ans = [0] * Q
    for i, (x, y) in enumerate(zip(*[iter(XY)] * 2)):
        ans[i] = dist[x - 1] + dist[y - 1]

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


if __name__ == '__main__':
    main()

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

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    Q, K, *XY = map(int, read().split())
    K -= 1

    hq = [(0, K)]
    dist = [INF] * N
    dist[K] = 0
    while hq:
        d, v = heappop(hq)
        if dist[v] < d:
            continue
        for nv, cost in G[v]:
            if dist[nv] > d + cost:
                dist[nv] = d + cost
                heappush(hq, (dist[nv], nv))

    ans = [0] * Q
    for i, (x, y) in enumerate(zip(*[iter(XY)] * 2)):
        ans[i] = dist[x - 1] + dist[y - 1]

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


if __name__ == '__main__':
    main()

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

q, k = map(int, input().split())
ds = [-1]*n
hq = [(0,k-1)]
while hq:
    c,idx = heapq.heappop(hq)
    if ds[idx] != -1:
        continue
    ds[idx] = c
    for i in g[idx]:
        if ds[i[0]] == -1:
            heapq.heappush(hq,(i[1]+c,i[0]))

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

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

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

check = [False for _ in range(n)]
dist = [0 for _ in range(n)]
def dfs(pos, b_pos):
    for n_pos, c in edges[pos]:
        if n_pos == b_pos:
            continue
        check[n_pos] = True
        dist[n_pos] = c + dist[pos]
        dfs(n_pos, pos)

check[k - 1] = True
dfs(k - 1, -1)

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

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

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

dist = [-1] * N
def dfs(v, total_cost):
    
    dist[v] = total_cost
    for v_next, cost in tree[v]:
        if dist[v_next] >= 0:
            continue
            
        dfs(v_next, total_cost+cost)

dfs(K-1, 0)

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

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

def dfs(now_node,parent_node,dist):
  depth[now_node]=dist
  for next_node,w in graph[now_node]:
    if next_node==parent_node:
      continue
    dfs(next_node,now_node,dist+w)

n=int(input())
graph=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b,c=map(int,input().split())
  graph[a].append((b,c))
  graph[b].append((a,c))
  
q,k=map(int,input().split())
depth=[-1]*(n+1)
dfs(k,0,0)
for _ in range(q):
  x,y=map(int,input().split())
  print(depth[x]+depth[y])

Solution (Python):
def abc070_d():
    import sys
    sys.setrecursionlimit(10010010)
    read = sys.stdin.buffer.read
    inp = iter(map(int, read().split()))

    n = next(inp)
    adjlist = [[] for _ in range(n)]
    for _ in range(n-1):
        a = next(inp) - 1
        b = next(inp) - 1
        c = next(inp)
        adjlist[a].append((b, c))
        adjlist[b].append((a, c))

    q = next(inp)
    k = next(inp) - 1

    dist = [-1] * n

    def dfs(x:int, d:int):
        dist[x] = d
        for nx, nd in adjlist[x]:
            if dist[nx] != -1: continue
            dfs(nx, d + nd)

    dfs(k, 0)

    for _ in range(q):
        x = next(inp) - 1
        y = next(inp) - 1
        ans = dist[x] + dist[y]
        print(ans)

if __name__ == '__main__':
    abc070_d()

Solution (Python):
import sys
sys.setrecursionlimit(pow(10,6))
readline = sys.stdin.readline

def dfs(nw, d):
    V[nw] = d
    for nx in G[nw]:
        if V[nx[0]]==-1:
            dfs(nx[0], d+nx[1])

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

V = [-1]*n
dfs(k-1, 0)

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

Solution (Python):
from heapq import heappush, heappop

def dijkstra(s):
    '''
    始点sから各頂点への最短距離を求める
    '''
    d = [float("inf")] * n
    d[s] = 0
    used = [False] * n
    used[s] = True
    edgelist = []

    for e in edge[s]:
        heappush(edgelist, e)

    while edgelist:
        cost, v = heappop(edgelist)
        if used[v]:
            continue
        d[v] = cost
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heappush(edgelist, [e[0] + d[v], e[1]])

    return d


n = int(input())

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

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

dist = dijkstra(k-1)

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

for v in res:
    print(v)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
N=int(input())
T=[[] for _ in range(N)]
for i in range(N-1):
  a,b,c=map(int, input().split())
  T[a-1].append((b-1,c))
  T[b-1].append((a-1,c))
Q,K=map(int, input().split())

dist=[-1]*N
dist[K-1]=0

def dfs(start, nown):
  to=T[start]
  for t in to:
    next_node,c=t
    if dist[next_node]!=-1:
      continue
    nextn=nown+c
    dist[next_node]=nextn
    dfs(next_node, nextn)

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

Solution (Python):
n=int(input())
es=[[] for _ in range(n)]

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

q,k=map(int,input().split())
k-=1
dist=[float('inf')]*n

dist[k]=0
stack=[k]
while stack:
    now=stack.pop()
    for e,w in es[now]:
        if dist[e]==float('inf'):
            dist[e]=dist[now]+w
            stack.append(e)

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

Solution (Python):
n=int(input())
es=[[] for _ in range(n)]

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

from heapq import heappush, heappop
def dijkstra(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance


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

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter

from fractions  import gcd

import bisect
n=int(input())
v=tuple(tuple(map(lambda x: int(x)-1,input().split())) for _ in range(n-1))

node=[{} for _ in range(n)]
d=deque()
ans=[None]*n
for pair in v:
    node[pair[0]][pair[1]]=pair[2]+1
    node[pair[1]][pair[0]]=pair[2]+1
q,k=map(int,input().split())
d.append(k-1)
res=[-1]*n
res[k-1]=0
while True:
    if not d:
        break
    a=d.pop()
    for x in node[a]:
        if res[x]==-1:
            res[x]=node[a][x]+res[a]
            d.append(x)
for i in range(q):
  x,y=map(int,input().split())
  print(res[x-1]+res[y-1])

Solution (Python):
from collections import defaultdict,deque
from sys import stdin,setrecursionlimit
import heapq,bisect,math,itertools,string,queue,copy
setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, stdin.readline().split()))

N= int(input())


dlines = defaultdict(set)
for i in range(N-1):
    x,y,cost = inpl()
    dlines[x].add((cost,y))
    dlines[y].add((cost,x))

Q,K = inpl()
query = []
for _ in range(Q):
    x2,y2 = inpl()
    query.append((x2,y2))


def dijkstra_heap(n,s,dlines):
    d = [10**20]*(n+1)
    used = [True]*(n+1)
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in dlines[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 dlines[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

res = dijkstra_heap(N,K,dlines)
for order in query:
    print(res[order[0]]+res[order[1]])

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

def dfs(st, depth=0):
    dist[st] = depth
    for to, c in tree[st]:
        if dist[to]>=0:
            continue
        dfs(to, depth+c)


N = int(input())
tree = [[] for _ in range(N)]
dist = [-1]*N

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

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


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

Solution (Python):
from heapq import heapify,heappush,heappop
n = int(input())
INF = float("inf")
adj = [[] for _ in range(n)]
for _ in range(n-1):
    a,b,c = map(int,input().split())
    a,b = a-1,b-1
    adj[a].append((b,c))
    adj[b].append((a,c))
H = []
heapify(H)
searched = [0]*n
q,k = map(int,input().split())
k-=1
d = [INF]*n
d[k] = 0
heappush(H, (0,k))
while H:
    f = heappop(H)
    u = f[-1]
    searched[u] = 1
    if d[u] < f[0]:
        continue
    for j in range(len(adj[u])):
        v = adj[u][j][0]
        if searched[v]:
            continue
        if d[v] > d[u]+adj[u][j][-1]:
            d[v] = d[u]+adj[u][j][-1]
            heappush(H,(d[v],v))
for _ in range(q):
    x,y = map(int,input().split())
    x,y = x-1,y-1
    print(d[x]+d[y])

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

d = [float('inf')] * (N + 1)
d[K] = 0
q = [K]
while q:
    i = q.pop()
    for j, c in links[i]:
        if d[i] + c < d[j]:
            d[j] = d[i] + c
            q.append(j)

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

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

Solution (Python):
def solve():
    import heapq
    n = int(input())
    g = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b, c = map(int, input().split())
        a, b = a - 1, b - 1
        g[a].append((b, c))
        g[b].append((a, c))
    inf = 10**15
    dist = [inf] * n

    def dijkstra(s):
        q = []
        dist[s] = 0
        heapq.heappush(q, [0, s])
        while q:
            p, v = heapq.heappop(q)
            if dist[v] < p:
                continue
            for i, x in g[v]:
                if dist[i] > dist[v] + x:
                    dist[i] = dist[v] + x
                    heapq.heappush(q, [dist[i], i])

    m, k = map(int, input().split())
    k = k - 1
    dijkstra(k)
    for _ in range(m):
        e, f = map(int, input().split())
        res = dist[e - 1] + dist[f - 1]
        print(res)


solve()

Solution (Python):
def solve():
    from collections import deque
    n = int(input())
    g = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b, c = map(int, input().split())
        a, b = a - 1, b - 1
        g[a].append((b, c))
        g[b].append((a, c))
    dist = [0] * n

    def dfs(v, p=-1, d=0):
        q = deque()
        q.append((v, p, d))
        while q:
            v, p, d = q.pop()
            dist[v] = d
            for i, x in g[v]:
                if i == p:
                    continue
                q.append((i, v, d + x))

    m, k = map(int, input().split())
    k = k - 1
    dfs(k)
    for _ in range(m):
        e, f = map(int, input().split())
        res = dist[e - 1] + dist[f - 1]
        print(res)


solve()

Solution (Python):
import queue
n=int(input())
INF=10**18
e=[[] for _ in range(n+1)]
d=[INF]*(n+1)
for i in range(n-1):
  a,b,c=map(int,input().split())
  e[a].append((b,c))
  e[b].append((a,c))
q,k=map(int,input().split())
que=queue.Queue()
que.put(k)
d[k]=0
while not que.empty():
  x=que.get()
  for i,c in e[x]:
    if d[i]==INF:
      que.put(i)
      d[i]=d[x]+c
for _ in range(q):
  x,y=map(int,input().split())
  print(d[x]+d[y])

Solution (Python):


import copy
import random
import bisect 
import fractions 
import math
import sys
import collections
from decimal import Decimal 

mod = 10**9+7
sys.setrecursionlimit(mod) 

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
weights = {}

roots = [[] for i in range(N)]
for i in range(N - 1):
    a, b, c = LI()
    a -= 1
    b -= 1
    roots[a].append(b)
    roots[b].append(a)
    weights[(a,b)] = c
    weights[(b,a)] = c

Q, K = LI()
K -= 1
xy = [0 for i in range(Q)]
for i in range(Q):
    x, y = LI()
    x -= 1
    y -= 1
    xy[i] = [x, y]
"""
xyzで全部の通りを見つけるとN ** 3で無理
なので今回は木構造に注目してBFS or DFSで解いたらいいのでは？
重みを単純にグラフに持つと10**5 ** 2になってしまうので注意
"""

visited = [-1 for i in range(N)]
queue = collections.deque()
queue.append(K)
visited[K] = 0

while len(queue)> 0:
    node = queue.popleft()
    cnt = visited[node]
    for n_node in roots[node]:
        if visited[n_node] == -1:
            visited[n_node] = cnt + weights[(node, n_node)]
            queue.append(n_node)

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

Solution (Python):
import sys
from collections import deque

N = int(sys.stdin.readline())

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

Q, K = map(int, sys.stdin.readline().split())


dist = [-1 for _ in range(N)]

visited = set()
q = deque([(K-1, 0)])
while q:
    p, c = q.popleft()
    if p in visited:
        continue
    dist[p] = c

    visited.add(p)
    for (next_p, next_c) in edges[p]:
        q.append((next_p, c + next_c))


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

Solution (Python):
import sys
import queue

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007



def main():
	n = int(input())
	graph = [[] for _ in range(n)]
	for _ in range(n-1):
		a, b, d = tin()
		graph[a-1].append((b-1, d))
		graph[b-1].append((a-1, d))
	
	q, k = tin()
	dist = [-1]*n
	dist[k-1] = 0
	qu=queue.Queue()
	qu.put(k-1)
	while not qu.empty():
		pos = qu.get()
		for v, d in graph[pos]:
			if dist[v] == -1:
				dist[v] = dist[pos] + d
				qu.put(v)
	
	for _ in range(q):
		f, t = tin()
		print(dist[f-1] + dist[t-1])
	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
d = [-1 for i in range(n)]
e = [[] for i in range(n)]
for i in range(n - 1):
    a, b, c = map(int, input().split())
    e[a - 1].append([b - 1, c])
    e[b - 1].append([a - 1, c])
q, k = map(int, input().split())
def dfs(cur, par, di):
    d[cur] = di
    for i in e[cur]:
        if d[i[0]] == -1:
            if i == par:
                continue
            dfs(i[0], cur, di + i[1])
dfs(k - 1, -1, 0)
for i in range(q):
    x, y = map(int, input().split())
    print(d[x - 1] + d[y - 1])

Solution (Python):

import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

N = int(input())
adj = [[] for _ in range(N)]
rtree = [None] * N

def dfs(v,parent,dist):
    rtree[v] = dist
    for u, c in adj[v]:
        if u == parent:
            continue
        dfs(u,v,dist+c)

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

    
    dfs(K-1,-1,0)

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

if __name__ == "__main__":
    main()

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


















N = int(input())

ARR = [list(map(int,input().split())) for i in range(N-1)]

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

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



def prepare(arr, n):
    links = [[] for i in range(n)]
    depth = [0 for i in range(n)]
    for i in range(n - 1):
        startNode = arr[i][0] - 1
        endNode = arr[i][1] - 1
        dist = arr[i][2]

        links[startNode].append((endNode, dist))
        links[endNode].append((startNode, dist))

    return links, depth


def dfs(currentNode, parrentNode=-1, dist=0):
    childNodes = links[currentNode]
    depths[currentNode] = dist
    for (childNode, childDistance) in childNodes:
        if childNode == parrentNode:
            continue

        dfs(childNode, currentNode, dist + childDistance)


links, depths = prepare(ARR, N)

dfs(K - 1)

for i in range(Q):
    p1 = BRR[i][0] - 1
    p2 = BRR[i][1] - 1

    d1 = depths[p1]
    d2 = depths[p2]

    print(d1 + d2)

Solution (Python):
from collections import deque

























































N = int(input())

ARR = [list(map(int,input().split())) for i in range(N-1)]

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

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


def prepare(n, arr):
    links = {}
    nodeStatus = {}
    distances = {}
    finalDistance = {}
    for i in range(1, N + 1):
        nodeStatus.__setitem__(i, False)
        finalDistance.__setitem__(i, 0)

    for i in range(len(arr)):
        tmp = arr[i]
        startNode = tmp[0]
        endNode = tmp[1]
        distance = tmp[2]
        distances.__setitem__((startNode, endNode), distance)
        distances.__setitem__((endNode, startNode), distance)
        if links.get(startNode) == None:
            links.__setitem__(startNode, [endNode])
        else:
            tmpChild = links.get(startNode)
            tmpChild.append(endNode)
            links.__setitem__(startNode, tmpChild)

        if links.get(endNode) == None:
            links.__setitem__(endNode, [startNode])
        else:
            tmpChild = links.get(endNode)
            tmpChild.append(startNode)
            links.setdefault(endNode, tmpChild)
    return links, nodeStatus, distances, finalDistance


def bfs(startNode):
    q = deque()

    q.append((startNode, 0))

    while len(q):
        currentNode, dist = q.popleft()
        finalDistance.__setitem__(currentNode, dist)
        nodeStatus.__setitem__(currentNode, True)

        childNodes = links.get(currentNode)

        for childNode in childNodes:
            if nodeStatus.get(childNode) == False:
                q.append((childNode, dist + distances.get((currentNode, childNode))))


links, nodeStatus, distances, finalDistance = prepare(N, ARR)







bfs(K)
for i in range(Q):
    dist1 = finalDistance[BRR[i][0]]
    dist2 = finalDistance[BRR[i][1]]
    print(dist1 + dist2)

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10**7)
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())


dist = [-1] * n

def dfs(st, depth=0):
    dist[st] = depth
    for to, c in g[st]:
        if dist[to] >= 0: continue
        dfs(to, depth+c)

dfs(k-1, 0)

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

Solution (Python):
import heapq

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

Q, K = map(int, input().split())
memo = [float('inf')]*(N+1)
memo[K] = 0
h = [(0,K)]
while h:
  t = heapq.heappop(h)
  if t[0] > memo[t[1]]:
    continue
  for k in dic[t[1]]:
    if memo[k[0]] > t[0] + k[1]:
      memo[k[0]] = t[0] + k[1]
      heapq.heappush(h, (memo[k[0]], k[0]))
      
for _ in range(Q):
  x, y = map(int, input().split())
  print(memo[x]+memo[y])

Solution (Python):
from collections import deque
n=int(input())
e=[[] for _ in range(n+1)]
dist=[-1]*(n+1)
for i in range(n-1):
    a,b,c=map(int,input().split())
    e[a].append((b,c))
    e[b].append((a,c))
q,k=map(int,input().split())
a=deque()
a.append((k,0))
while a:
    x,d=a.popleft()
    dist[x]=d
    for j,nc in e[x]:
        if dist[j]!=-1:
            continue
        else:
            a.append((j,d+nc))
ans=[]
for i in range(q):
    x,y=map(int,input().split())
    ans.append(dist[x]+dist[y])
print(*ans,sep="\n")

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

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

r = 0
dist = [0]*N

prv = [None]*N
depth = [0]*N

def dfs(v):
    for u in G[v]:
        if dist[u] > 0 or u ==r: continue
        dist[u] = dist[v] + length[(v, u)]
        depth[u] = depth[v] + 1
        prv[u] = v
        dfs(u)

dfs(r)










LV = (N-1).bit_length()
def construct(prv):
    kprv = [prv]
    S = prv
    for k in range(LV):
        T = [0]*N
        for i in range(N):
            if S[i] is None:
                continue
            T[i] = S[S[i]]
        kprv.append(T)
        S = T
    return kprv

def lca(u, v, kprv, depth):
    dd = depth[v] - depth[u]
    if dd < 0:
        u, v = v, u
        dd = -dd

    
    for k in range(LV+1):
        if dd & 1:
            v = kprv[k][v]
        dd >>= 1

    
    if u == v:
        return u

    for k in range(LV-1, -1, -1):
        pu = kprv[k][u]; pv = kprv[k][v]
        if pu != pv:
            u = pu; v = pv

    
    return kprv[0][u]

kprv = construct(prv)

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

ans = []
for _ in range(Q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    xr = lca(x, K, kprv, depth)
    yr = lca(y, K, kprv, depth)
    a = dist[x] + dist[K] - dist[xr]*2 + dist[y] + dist[K] - dist[yr]*2
    ans.append(a)

print('\n'.join(map(str, ans)))