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

from collections import deque
def inpl(): return map(int, input().split())
N = int(input())

G = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, c = inpl()
    G[a].append([b, c])
    G[b].append([a, c])

Q, K = inpl()

def BFS(G, K):
    DQ = deque([K])
    D = [-1] * (N+1)
    D[K] = 0
    while DQ:
        p = DQ.popleft()
        for q, c in G[p]:
            if D[q] == -1:
                D[q] = D[p] + c
                DQ.append(q)
    return D

D = BFS(G, K)
for _ in range(Q):
    x, y = inpl()
    print(D[x] + D[y])

Solution (Python):

from collections import deque
def inpl(): return map(int, input().split())
N = int(input())

G = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, c = inpl()
    G[a].append((b, c))
    G[b].append((a, c))

Q, K = inpl()

def BFS(G, K):
    DQ = deque([K])
    D = [0] * (N+1)
    visited = [False]*(N+1)
    while DQ:
        p = DQ.popleft()
        visited[p] = True
        for q, c in G[p]:
            if not visited[q]:
                D[q] = D[p] + c
                DQ.append(q)
    return D

D = BFS(G, K)
for _ in range(Q):
    x, y = inpl()
    print(D[x] + D[y])

Solution (Python):

from collections import deque
def inpl(): return map(int, input().split())
N = int(input())

G = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, c = inpl()
    G[a].append((b, c))
    G[b].append((a, c))

D = [0] * (N+1)
Q, K = inpl()
DQ = deque([K])
visited = [False]*(N+1)

while DQ:
    p = DQ.popleft()
    visited[p] = True
    for q, c in G[p]:
        if not visited[q]:
            D[q] = D[p] + c
            DQ.append(q)

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

Solution (Python):

from collections import deque
def inpl(): return map(int, input().split())
N = int(input())

G = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, c = inpl()
    G[a].append((b, c))
    G[b].append((a, c))

D = [0] * (N+1)
Q, K = inpl()
DQ = deque([[K, 0]])
visited = [False]*(N+1)

while DQ:
    p, c = DQ.popleft()
    D[p] = c
    visited[p] = True
    for q, d in G[p]:
        if not visited[q]:
            DQ.append([q, c+d])

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

Solution (Python):
def d_transit_tree_path(N, E, Q, K, V):
    

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

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

    while queue:
        u = queue.pop()
        for v, c in edge[u]:
            if not is_visit[v]:
                is_visit[v] = True
                dist[v] = dist[u] + c
                queue.append(v)

    ans = ''
    for q1, q2 in V:
        ans += '{}\n'.format(dist[q1 - 1] + dist[q2 - 1])
    ans = ans[:-1]
    return ans

N = int(input())
E = [[int(i) for i in input().split()] for j in range(N-1)]
Q,K = [int(i) for i in input().split()]
V = [[int(i) for i in input().split()] for j in range(Q)]
print(d_transit_tree_path(N, E, Q, K, V))

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

N = int(input())
edges = []
connected = [[] for i in range(100010)]
for i in range(N-1):
    x=list(map(int, input().split()))
    x[0] -= 1
    x[1] -= 1
    edges.append(x)
    connected[x[0]].append([x[1], x[2]])
    connected[x[1]].append([x[0], x[2]])

Q,K = map(int, input().split())
K -= 1
depth = [0]*100010
def DFS(v, p, d):
    depth[v] = d
    for child in connected[v]:
        if child[0] == p:
            continue
        DFS(child[0], v, d+child[1])

DFS(K,-1,0)
for i in range(Q):
    xi, yi = map(int, input().split())
    print(depth[xi-1]+depth[yi-1])

Solution (Python):
import heapq
from collections import defaultdict

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

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

def dijkstra(n,v):
  d=[float('inf')]*n
  d[v]=0
  
  hq=[(0,v)]
  
  while hq:
    u = heapq.heappop(hq)[1]
    for nv,c in V[u]:
      if d[nv]>d[u]+c:
        d[nv]=d[u]+c
        heapq.heappush(hq,(d[u]+c,nv))
        
  return d

ans=dijkstra(N,K-1)

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

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

def dfs(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)]
dis = dfs(k-1, path, n)
for i in range(q):
    print(dis[xy[i][0] - 1] + dis[xy[i][1] - 1])

Solution (Python):
def dfs(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)]
dis = dfs(k-1, path, n)
for i in range(q):
    print(dis[xy[i][0] - 1] + dis[xy[i][1] - 1])

Solution (Python):
n = int(input())
E = {}

for i in range(n-1):
    a, b, c = map(int, input().split()) 
    found = E.get(a, None)
    if found is None:
        found = []
    found.append((b, c))
    E[a] = found
    found = E.get(b, None)
    if found is None:
        found = []
    found.append((a, c))
    E[b] = found

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


def make_distance_from_k(k, E):
    d = {}
    d[k] = 0
    queue = [k]
    while queue:
        i = queue.pop()
        for j, c in E[i]:
            if j not in d:
                d[j] = d[i] + c
                queue.append(j)
    return d

d = make_distance_from_k(k, E)

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

Solution (Python):


N = int(input())
tree = [[]for x in range(N)]
depth = [0 for x in range(N)]
for _ in range(N-1):
    line = input().split(" ")
    a = int(line[0])-1
    b = int(line[1])-1
    c = int(line[2])
    tree[a].append((b, c))
    tree[b].append((a, c))

line = input().split(" ")
Q = int(line[0])
K = int(line[1])-1









s = [(K, -1, 0)]
while len(s)>0:
    (v, p, d) = s.pop()
    depth[v] = d
    for e in tree[v]:
        if e[0]==p:
            continue
        s.append((e[0], v, d+e[1]))


for _ in range(Q):
    line = input(" ").split(" ")
    x = int(line[0])-1
    y = int(line[1])-1
    print(str(depth[x]+depth[y]))

Solution (Python):
import heapq

n = int(input())
g = [[] for i 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())

dist = [float('inf') for i in range(n)]
dist[k-1] = 0
visited = [False for i in range(n)]
hq = [(0, k-1)]
while hq:
    d, v = heapq.heappop(hq)
    if visited[v]:
        continue
    visited[v] = True
    for nv, c in g[v]:
        if visited[nv]:
            continue
        if d+c < dist[nv]:
            heapq.heappush(hq, (d+c, nv))
            dist[nv] = d+c


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

Solution (Python):



import Queue

N = int(raw_input())
tree = [[] for _ in xrange(N)]

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

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

depth = [0 for _ in xrange(N)]

def bfs(v, p = -1, d = 0):
    q = Queue.Queue()
    q.put([v, p, d])
    while not q.empty():
        cur = q.get()
        depth[cur[0]] = cur[2]
        for i, j in tree[cur[0]]:
            if i == cur[1]:
                continue
            q.put([i, cur[0], cur[2] + j])

bfs(K)

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

Solution (Python):



N = int(raw_input())
tree = [[] for _ in xrange(N)]

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

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

depth = [0 for _ in xrange(N)]

def dfs(v, p = -1, d = 0):
    St = []
    St.append([v, p, d])
    
    while St:
        cur = St.pop()
        depth[cur[0]] = cur[2]
        for i, j in tree[cur[0]]:
            if i == cur[1]:
                continue
            St.append([i, cur[0], cur[2] + j])

dfs(K)

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

Solution (Python):



import Queue

N = int(raw_input())
tree = [[] for _ in xrange(N)]

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

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

d = [float("inf") for _ in xrange(N)]

def dijkstra(s):
    que = Queue.PriorityQueue()
    d[s] = 0
    que.put([0, s])

    while not que.empty():
        p = que.get()
        v = p[1]
        if d[v] < p[0]:
            continue
        for i, j in tree[v]:
            if d[i] > d[v] + j:
                d[i] = d[v] + j
                que.put([d[i], i])

dijkstra(K)

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

Solution (Python):



N = int(raw_input())
tree = [[] for _ in xrange(N)]

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

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

depth = [0 for _ in xrange(N)]

def dfs(v, p = -1, d = 0):
    St = []
    St.append([v, p, d])
    while len(St) != 0:
        cur = St.pop()
        depth[cur[0]] = cur[2]
        for i, j in tree[cur[0]]:
            if i == cur[1]:
                continue
            St.append([i, cur[0], cur[2] + j])

dfs(K)

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

Solution (Python):



import sys

sys.setrecursionlimit(200000)

N = int(raw_input())
tree = [[] for _ in xrange(N)]

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

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

depth = [0 for _ in xrange(N)]

def dfs(v, p = -1, d = 0):
    depth[v] = d
    for i, j in tree[v]:
        if i == p:
            continue
        dfs(i, v, d + j)

dfs(K)

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

Solution (Python):
import Queue

from sys import stdin
input = stdin.readline

N = int(raw_input())
tree = [[] for _ in xrange(N)]

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

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

d = [float("inf") for _ in xrange(N)]

def dijkstra(s):
    que = Queue.PriorityQueue()
    d[s] = 0
    que.put([0, s])

    while not que.empty():
        p = que.get()
        v = p[1]
        if d[v] < p[0]:
            continue
        for i, j in tree[v]:
            if d[i] > d[v] + j:
                d[i] = d[v] + j
                que.put([d[i], i])

dijkstra(K)

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

Solution (Python):
import Queue

N = int(raw_input())
tree = [[] for _ in xrange(N)]

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

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

d = [float("inf") for _ in xrange(N)]

def dijkstra(s):
    que = Queue.PriorityQueue()
    d[s] = 0
    que.put([0, s])

    while not que.empty():
        p = que.get()
        v = p[1]
        if d[v] < p[0]:
            continue
        for i, j in tree[v]:
            if d[i] > d[v] + j:
                d[i] = d[v] + j
                que.put([d[i], i])

dijkstra(K)

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

Solution (Python):







import sys

sys.setrecursionlimit(200000)

N = int(raw_input())
tree = [[] for _ in xrange(N)]

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

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

depth = [0 for _ in xrange(N)]

def dfs(v, p = -1, d = 0):
    St = []
    St.append([v, p, d])
    while len(St) != 0:
        cur = St.pop()
        depth[cur[0]] = cur[2]
        for i, j in tree[cur[0]]:
            if i == cur[1]:
                continue
            St.append([i, cur[0], cur[2] + j])

dfs(K)

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

Solution (Python):
import sys

sys.setrecursionlimit(200000)

N = int(raw_input())
tree = [[] for _ in xrange(N)]

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

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

depth = [0 for _ in xrange(N)]

def dfs(v, p = -1, d = 0):
    depth[v] = d
    for i, j in tree[v]:
        if i == p:
            continue
        dfs(i, v, d + j)

dfs(K)

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

Solution (Python):
class Node:
    def __init__(self):
        pass
 
class Edge:
    def __init__(self,edge,cost=1):
        self.node_from=edge[0]
        self.node_to=edge[1]
        self.cost=cost
 
    def add_node(self,node):
        self.nodes.append(node)
 
class myGraph:
 
    def __init__(self):
        self.adj={}
        self.nodes={}
 
    def add_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)
 
        u,v=edge[0],edge[1]
 
        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}
 
        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}
 
        
        self.adj[u][v] = cost
        self.adj[v][u] = cost
 
    def add_directed_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)
 
 
        u,v=edge[0],edge[1]
 
        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}
 
        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}
 
        self.adj[u][v] = cost
 
    def get_edges_from(self,node):
        return [(self.adj[node][nn],node,nn) for nn in self.adj[node]]
 
 
    def makeEdgeobj(self):
        edges=[]
        for sn in self.nodes:
            for e in self.get_edges_from(sn):
                edges.append(Edge([e[1],e[2]],e[0]))
 
        return edges
 
    def _add(self,edges,add_edges):
        for e in add_edges:
            hq.heappush(edges,e)
        return edges
 
    def bermn_ford(self,start,init=0):
 
        nodes=self.nodes
        dists={}
        for n in nodes:
            dists[n]=float("inf")
 
        dists[start]=init
        edges=self.makeEdgeobj()
 
        for i in range(len(nodes)):
            update=False
            for k in range(len(edges)):
                e=edges[k]
                if  dists[e.node_from]!=float("inf") and dists[e.node_to]>dists[e.node_from]+e.cost:
                    dists[e.node_to]=dists[e.node_from]+e.cost
                    update=True
 
            if i==len(nodes)-1:
                return False
 
            if not update:
                break
 
        return dists
 
 
    def dijkstra(self,start, goal=None):
        import heapq
        '''
            get minimum cost
        '''
 
        N = len(self.adj)          
        
        dist = {k:float('inf') for k in self.nodes}
        
 
        dist[start] = 0
        visited = []
 
        koho=[]
        heapq.heappush(koho,(0,start))
 
        vtx=list(self.nodes)
        vtx.remove(start)
 
        while len(koho)!=0:
            d,mini=heapq.heappop(koho)
            if dist[mini]<d:
                continue
 
 
            for k in list(self.adj[mini]):
                cost=self.adj[mini][k]
                if cost != float('inf') and dist[k]>dist[mini]+cost:
                    dist[k]=dist[mini]+cost
                    heapq.heappush(koho,(dist[k],k))
                    
 
        return dist
 
    def prim(self):
 
        import heapq
 
        nodes=list(self.nodes.keys())
        N=len(nodes)
 
        X=[nodes[0]]
        unused=[]
        for u in self.adj[X[0]]:
            heapq.heappush(unused,(self.adj[X[0]][u],X[0],u))
 
        total_cost=0
        used={n:False for n in nodes}
        used[X[0]]=True
        while True:
            
            
            cost,u,v=heapq.heappop(unused)
            if used[v]:
                continue
            X.append(v)
            used[v]=True
            total_cost+=cost
            if len(X)==N:
                break
 
            for u in self.adj[v]:
                if used[u]:
                    continue
                heapq.heappush(unused,(self.adj[u][v],v,u))
 
        return total_cost
 
 
 
 
    def show(self):
 
        import networkx as nx
        import matplotlib.pyplot as plt
        G=nx.Graph()
 
        for u in self.adj:
            for v in self.adj[u]:
 
                
                G.add_edge(u,v,weight=self.adj[u][v])
                
 
        pos=nx.spring_layout(G)
        
        edge_weight=dict([((u,v,),int(d['weight'])) for u,v,d in G.edges(data=True)])
 
        nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_weight)
        
        nx.draw_networkx_nodes(G,pos)
        nx.draw_networkx_edges(G,pos)
        nx.draw_networkx_labels(G,pos)
        
        
        plt.show()
 
 
 
def spaceinput():
    s=input()
    if len(s)==0:
        return False
 
    return list(map(int,s.split(" ")))
 
if __name__=="__main__":
 
    N=int(input())
 
    g=myGraph()
 
 
    for i in range(N-1):
        try:
            ss=spaceinput()
            if not ss:
                break
        except:
            break
        g.add_edge((ss[0],ss[1]),ss[2])
        
 
    Q,K=spaceinput()
 
    res=g.dijkstra(K)
    xx=[]
    for k in range(Q):
        xx.append(spaceinput())
 
 
 
    for x,y in xx:
        print(int(res[x]+res[y]))

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
N = int(raw_input())
dict = {}
for i in range(1,N+1):
    dict[i]={}
for i in range(1,N):
    a = map(int,raw_input().split())
    dict[a[0]].update({a[1]:a[2]})
    dict[a[1]].update({a[0]:a[2]})
leng = {}
q,K = map(int,raw_input().split())
def rec(bef,now):
    leng[now]=leng[bef]+dict[bef][now]
    for i in dict[now]:
        if i in leng:
            continue
        rec(now,i)
leng[K] = 0
for j in dict[K]:
    rec(K,j)
for i in range(0,q):
    a,b = map(int, raw_input().split())
    print leng[a]+leng[b]

Solution (Python):
from collections import deque

n = int(input())
preroots = []
for i in range(n-1):    
    preroots.append(list(map(int,input().split())))

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

for i in range(n-1):
    roots[preroots[i][0]].append([preroots[i][1],preroots[i][2]])
    roots[preroots[i][1]].append([preroots[i][0],preroots[i][2]])



QK = list(map(int,input().split()))
dist  = [-1 for i in range(n+1)]
dist[QK[1]] = 0
query = []
for i in range(QK[0]):
    query.append(list(map(int,input().split())))

q = deque()
q.append(QK[1])

while(len(q)):
    curr = q.popleft()
    for i in roots[curr]:
        if dist[i[0]] != -1:continue
        dist[i[0]] = dist[curr] + i[1]
        q.append(i[0])
        
for i in query:
    print(dist[i[0]] + dist[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)]
 
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):

"""
http://abc070.contest.atcoder.jp/tasks/abc070_d
"""





from heapq import heappush, heappop



N = int(input())
adj = [[] for _ in range(N+1)]
for i in range(N-1):
    f, t, c = [int(x) for x in input().split(' ')]
    adj[f].append((t, c))
    adj[t].append((f, c))

queries = []
Q, K = [int(x) for x in input().split(' ')]
for _ in range(Q):
    queries.append([int(x) for x in input().split(' ')])


WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * (N+1)  
d = [float('inf')] * (N+1)  


d[K] = 0
pq = [(0, K)]

while pq:
    cost, u = heappop(pq)
    color[u] = BLACK
    if d[u] < cost:
        continue

    for v, c in adj[u]:
        if color[v] == BLACK:
            continue
        if d[v] > d[u] + c:
            d[v] = d[u] + c
            heappush(pq, (d[v], v))
            color[v] = GRAY


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

Solution (Python):
def BFS(K,edges,N):
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a-1]+=[(b-1,c)]
    roots[b-1]+=[(a-1,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist
 
N=int(input())
edges=[]
for i in range(N-1):
  edges+=[list(map(int,input().split()))]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,edges,N)
for i in range(Q):
  print(distance[xy[i][0]-1]+distance[xy[i][1]-1])

Solution (Python):
def BFS(K,edges,N):
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in edges[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist
 
N=int(input())
edges=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  edges[a-1]+=[(b-1,c)]
  edges[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,edges,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,edges,N):
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in edges[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist
 
N=int(input())
edges=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  edges[a-1]+=[(b-1,c)]
  edges[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,edges,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=[]
  que.append(K)
  while que:
    label=que.pop(-1)
    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())

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

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


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


from collections import deque
queue = deque()
queue.append(K)

while queue:
    v = queue.popleft()
    for nxt, c in adj[-v]:
        if dist[-nxt] == -1:
            dist[-nxt] = dist[-v] + c
            queue.append(nxt)

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

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

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

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


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


from collections import deque
stack = deque()
stack.append(K)

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

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

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

N = int(input())

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

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


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


def dfs(v):
    for nxt, c in adj[-v]:
        if dist[-nxt] == -1:
            dist[-nxt] = dist[-v] + c
            dfs(nxt)

dfs(K)

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

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

N = int(input())

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

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


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

def dfs(v, prv, ds):
    dist[-v] = ds
    for nxt, c in adj[-v]:
        if nxt != prv:
            dfs(nxt, v, ds + c)

dfs(K, None, 0)

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

Solution (Python):
from collections import deque 

n = int(input())

preroots = []
preroots_appd = preroots.append

for i in range(n-1):
    preroots_appd(list(map(int,input().split())))
    
roots = [[] for x in range(n+1)]

for i in preroots:
    roots[i[0]].append((i[1],i[2]))         
    roots[i[1]].append((i[0],i[2]))     
         
QK = list(map(int,input().split()))         
query = []

query_appd = query.append
for i in range(QK[0]):
    query_appd(list(map(int,input().split())))
        
    
distfrom_K = [-1 for x in range(n+1)]
distfrom_K[QK[1]] = 0          

q = deque()
q.append(QK[1])

while(len(q)):
    currentNode = q.popleft()
    for i in roots[currentNode]:
        if distfrom_K[i[0]] != -1:continue
        distfrom_K[i[0]] = distfrom_K[currentNode] + i[1]
        q.append(i[0])

for i in query:
    print(distfrom_K[i[0]]+distfrom_K[i[1]])

Solution (Python):
import heapq
from collections import defaultdict

INF = 1e21

N = int(input())
Adj_list = defaultdict(set)

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

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

def dijkstra(x, vertex):
    d = [INF] * x
    d[vertex] = 0
    hq = [(0, vertex)] 
    
    while hq:
        u = heapq.heappop(hq)[1]
        for (v, c) in Adj_list[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heapq.heappush(hq, (d[u] + c, v))
                
    return d

distance = dijkstra(N, K-1)

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

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

tree = [[] for i 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 x,y in XY:
    print(depth[x] + depth[y])

Solution (Python):
from collections import deque 


n = int(input())
preroots = [[] for i in range(n-1)]
for i in range(len(preroots)):
    preroots[i] = list(map(int,input().split()))

roots = [[] for i in range(n+1)]
for i in preroots:
    roots[i[0]].append((i[1],i[2]))
    roots[i[1]].append((i[0],i[2]))
         
    
QK = list(map(int,input().split()))
query = [[] for i in range(QK[0])]
         
for i in range(QK[0]):
    query[i] = list(map(int,input().split()))
    
    
waylen = [-1 for i in range(n+1)]
waylen[QK[1]] = 0

q = deque()
q.append(QK[1])

while len(q):
    p = q.popleft()
    for i in roots[p]:
        if waylen[i[0]] != -1:continue
        waylen[i[0]] = i[1] + waylen[p]
        q.append(i[0])
        
for i in range(QK[0]):
    print(waylen[query[i][0]]+waylen[query[i][1]])