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())
visitedlist=[-1 for  i in range(n)]
kilist=[[] for i in range(n)]
anslist=[0 for i in range(n)]
searchedlist=[-1 for i in range(n)]
for i in range(n-1):
        a,b,c=map(int,input().split())
        kilist[a-1].append((b,c))
        kilist[b-1].append((a,c))        
def search(i):
        searchedlist[i-1]=1
        visitedlist[i-1]=1
        flag=0
        for j in kilist[i-1]:
            if visitedlist[j[0]-1]<0:
                visitedlist[j[0]-1]=1
                flag+=1
                anslist[j[0]-1]=anslist[i-1]+j[1]
        else:
            pass

        if flag>0:    
            for k in kilist[i-1]:
                if searchedlist[k[0]-1]==-1:
                    search(k[0])
q,k=map(int,input().split())
List=[0 for i in range(q)]
search(k)
for i in range(q):
    x,y=map(int,input().split())
    List[i]=anslist[x-1]+anslist[y-1]
for j in List:
    print(j)

Solution (Python):
n=int(input())
abc=[list(map(int,input().split())) for i in range(n-1)]
q,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(q)]
lst=[0]*(n+1)
data=[[] for i in range(n+1)]
flag=[0]*(n+1)
for u in abc:
    a,b,c=u
    data[a].append([b,c])
    data[b].append([a,c])
que=[k]
flag[k]=1
while que:
    h=que.pop()
    for u in data[h]:
        d,c=u
        if flag[d]==0:
            lst[d]=lst[h]+c
            que.append(d)
            flag[d]=1
for u in xy:
    x,y=u
    print(lst[x]+lst[y])

Solution (Python):
N = int(input())
E ={i:[] for i in range(N+1)}
for i in range(N-1):
  a,b,c = [int(x) for x in input().split()]
  E[a].append([b,c])
  E[b].append([a,c])
Q,K = [int(x) for x in input().split()]
cost= [0]*(N+1)
stk=[[K,-1,0]]
while stk:
  v,p,c = stk.pop()
  if cost[v]!=0:
    continue
  cost[v]=c
  for i,j in E[v]:
    if i!=p:
      stk.append([i,v,c+j])
for i in range(Q):
  a,b = [int(x) for x in input().split()]
  print(cost[a]+cost[b])

Solution (Python):
def BFS(N,start,roots):
    dist = [-1] * N
    stack = []
    stack.append(start)
    dist[start] = 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

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

N = I()
v = [[] for i in range(N)]
for i in range(N-1):
    a, b, c = LI()
    v[a-1].append([b-1,c])
    v[b-1].append([a-1,c])
Q, K =LI()


W = BFS(N,K-1,v)
ansC = []
for i in range(Q):
    x, y = LI()
    ansC.append(W[x-1]+W[y-1])

for v in ansC:
    print(v)

Solution (Python):
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    tmd = collections.defaultdict(list)
    tmdc = collections.defaultdict(int)
    for i in range(n-1):
        tma, tmb, tmc = list(map(int, input().rstrip('\n').split()))
        tmd[tma-1] += [tmb-1]
        tmd[tmb-1] += [tma-1]
        tmdc[tma-1, tmb-1] = tmc
        tmdc[tmb-1, tma-1] = tmc

    q, k = list(map(int, input().rstrip('\n').split()))
    ql = [[0, k-1]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(int)
    fq[k-1]
    while True:
        if len(ql) != 0:
            cost, tmp = ql.popleft()
            for tmv in tmd[tmp]:
                if tmv not in fq or cost + tmdc[tmp, tmv] < fq[tmv]:
                    ql.append([cost + tmdc[tmp, tmv], tmv])
                    fq[tmv] = cost + tmdc[tmp, tmv]
        else:
            break
    for i in range(q):
        x, y = list(map(int, input().rstrip('\n').split()))
        print(fq[x-1] + fq[y-1])


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 6)


def main():
    N = int(readline())
    edge = [[] for _ in range(N + 1)]

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

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

    distance = [None] * (N + 1)


    def measure_distance(v, d):
        distance[v] = d
        for vv, dd in edge[v]:
            if distance[vv] is not None:
                continue
            measure_distance(vv, d + dd)


    measure_distance(K, 0)

    xy = map(int, read().split())
    for x, y in zip(xy, xy):
        print(distance[x] + distance[y])


if __name__ == '__main__':
    main()

Solution (Python):





from collections import deque
import sys

input = sys.stdin.readline


def solve():
    inf = 10 ** 14 + 10

    n = int(input())
    e = tuple(set() for _ in range(n))
    for _ in range(n - 1):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        e[a].add((c, b))
        e[b].add((c, a))

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

    d = [inf] * n
    d[v] = 0

    dq = deque()
    for cost, to in e[v]:
        dq.append((cost, to, v))
        

    while dq:
        c, v, p = dq.popleft()
        if d[v] != inf:
            continue
        d[v] = d[p] + c
        for cost, to in e[v]:
            if to == p:
                continue
            dq.append((cost, to, v))
            
    for _ in range(q):
        x, y = map(int, input().split())
        x -= 1
        y -= 1
        print(d[x] + d[y])


if __name__ == '__main__':
    solve()

Solution (Python):




import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


def solve():
    inf = 10 ** 14 + 10

    def dfs(v: 'vertex_index, 0-indexed') -> None:
        for c, t in e[v]:
            if d[t] != inf:
                continue
            d[t] = d[v] + c
            dfs(t)

    n = int(input())
    e = tuple(set() for _ in range(n))
    for _ in range(n - 1):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        e[a].add((c, b))
        e[b].add((c, a))

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

    d = [inf] * n
    d[v] = 0

    dfs(v)

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


if __name__ == '__main__':
    solve()

Solution (Python):




from collections import namedtuple
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


def solve():
    inf = 10 ** 14 + 10

    Edge = namedtuple('Edge', 'cost to')

    def dfs(v: 'vertex_index, 0-indexed') -> None:
        for e_ in e[v]:
            if d[e_.to] != inf:
                continue
            d[e_.to] = d[v] + e_.cost
            dfs(e_.to)

    n = int(input())
    e = tuple(set() for _ in range(n))
    for _ in range(n - 1):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        e[a].add(Edge(cost=c, to=b))
        e[b].add(Edge(cost=c, to=a))

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

    d = [inf] * n
    d[v] = 0

    dfs(v)

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


if __name__ == '__main__':
    solve()

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

input = sys.stdin.readline


def solve():
    inf = 10 ** 14 + 10

    Edge = namedtuple('Edge', ('cost', 'to'))

    def dijkstra(s):
        used = [False] * n
        used[s] = True

        dist = [inf] * n
        dist[s] = 0

        h = []
        for e_ in e[s]:
            heappush(h, e_)

        while h:
            c, v = heappop(h)
            if used[v]:
                continue
            used[v] = True
            dist[v] = c
            for e_ in map(lambda x: (x.cost + dist[v], x.to), e[v]):
                heappush(h, e_)
        return dist

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

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

    g = dijkstra(v)

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


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
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))


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

dist=[float("inf")]*n
dist[k]=0
def dfs(s):
    for v,c in g[s]:
        if dist[v]==float("inf"):
            dist[v]=dist[s]+c
            dfs(v)


dfs(k)

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

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
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))


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

dist=[float("inf")]*n
dist[k]=0
def dfs(s):
    for v,c in g[s]:
        if dist[v]==float("inf"):
            dist[v]=dist[s]+c
            dfs(v)


dfs(k)

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

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())
cost = [10**10]*n
edge = [dict() for _ in range(n)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    edge[a-1].update({b-1: c})
    edge[b-1].update({a-1: c})

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


def dfs(i, prev, d):
    cost[i] = d
    for j in edge[i].keys():
        if j == prev:
            continue
        dfs(j, i, d+edge[i][j])


dfs(K-1, -1, 0)

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

Solution (Python):
from collections import*
from heapq import*
import sys
input=sys.stdin.readline
 
def BFS(point,d):
    cost=[1e18]*(n+1)
    cost[point]=0
    Q=deque()
    Q.appendleft((0,point))
    
    while Q:
        c,p=Q.pop()
        for np,co in d[p]:
            if cost[np]==1e18:
                cost[np]=c+co
                Q.appendleft((c+co,np))
    return cost

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

q,k=map(int,input().split())
y=BFS(k,d)
 
for i in range(q):
    a,b=map(int,input().split())
    print(y[a]+y[b])

Solution (Python):
from collections import*
from heapq import*
import sys
input=sys.stdin.readline
 
def BFS(point,d):
    cost=[1e18]*(n+1)
    cost[point]=0
    Q=deque()
    Q.appendleft((0,point))
    
    while Q:
        c,p=Q.pop()
        for np,co in d[p]:
            if cost[np]==1e18:
                cost[np]=c+co
                Q.appendleft((c+co,np))
    return cost

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

q,k=map(int,input().split())
y=BFS(k,d)
 
for i in range(q):
    a,b=map(int,input().split())
    print(y[a]+y[b])

Solution (Python):

from heapq import*
import sys
input=sys.stdin.readline
 
def DIJKSTRA(point,d):
    cost      = [1e18]*(n+1)
    Q         = []  
    cost[point]=0  
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

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

q,k=map(int,input().split())
y=DIJKSTRA(k,d)
 
for i in range(q):
    a,b=map(int,input().split())
    print(y[a]+y[b])

Solution (Python):

from heapq import*
import sys
input=sys.stdin.readline
 
def DIJKSTRA(point,d):
    cost      = [1e18]*(n+1)
    Q         = []  
    cost[point]=0  
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

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

q,k=map(int,input().split())
y=DIJKSTRA(k,d)
 
for i in range(q):
    a,b=map(int,input().split())
    print(y[a]+y[b])

Solution (Python):
from collections import deque

def f(k,edge,n):
    root = [[] for _ in range(n)]
    for i in range(n-1):
        a,b,c = edge[i][0],edge[i][1],edge[i][2]
        root[a-1].append([b-1,c])
        root[b-1].append([a-1,c])
    
    que = deque()
    for l in root[k]:
        que.append(l)
    
    dist = [float("inf")]*n
    dist[k] = 0
    visited = [False]*n
    que = deque([k])

    while que:
        pos = que.popleft()
        if not visited[pos]:
            visited[pos] = True
        for x,y in root[pos]:
            if not visited[x]:
                dist[x] = dist[pos] + y
                visited[x] = True
                que.append(x)
    return dist

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

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

ans = []
d = f(k-1,edge,n)
for i in range(q):
    x,y = map(int,input().split())
    ans.append(d[x-1] + d[y-1])

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

Solution (Python):
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    ts = collections.defaultdict(list)
    tc = collections.defaultdict(int)
    for i in range(n-1):
        ta, te, ttc = list(map(int, input().rstrip('\n').split()))
        ts[ta - 1] += [te - 1]
        ts[te - 1] += [ta - 1]
        tc[ta - 1, te - 1] = ttc
        tc[te - 1, ta - 1] = ttc

    q, k = list(map(int, input().rstrip('\n').split()))
    ql = [[0, k-1]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(int)
    while True:
        if len(ql) != 0:
            cost, p = ql.popleft()
            for v in ts[p]:
                if v not in fq:
                    n_cost = tc[p, v]
                    ql.append([cost + n_cost, v])
                    fq[v] = cost + n_cost
                else:
                    n_cost = tc[p, v]
                    if n_cost + cost < fq[v]:
                        ql.append([cost + n_cost, v])
                        fq[v] = cost + n_cost
        else:
            break
    for i in range(q):
        x, y = list(map(int, input().rstrip('\n').split()))
        print(fq[x-1] + fq[y-1])


if __name__ == '__main__':
    solve()

Solution (Python):
n=int(input())
from collections import defaultdict 
d=defaultdict(list)
for i in range(n-1):
    a,b,c=map(int,input().split())
    a-=1 
    b-=1 
    d[a].append([b,c])
    d[b].append([a,c])
qry,k=map(int,input().split())
k-=1 
dist=[0]*n 
dist[k]=-0 
vis=[0]*n 
vis[k]=1 
from collections import deque
q=deque() 
q.append(k)
while q: 
    t=q.popleft() 
    for node,weight in d[t]: 
        if not vis[node]:
            vis[node]=1 
            q.append(node)
            dist[node]=dist[t]+weight
while qry:
    qry-=1 
    a,b=map(int,input().split())
    a-=1 
    b-=1 
    print(dist[a]+dist[b])

Solution (Python):
import sys


import heapq


n = int(input())
graph = {j:[] for j in range(n)}
for j in range(n-1):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append([b,c])
    graph[b].append([a,c])
q, k = [int(i) for i in sys.stdin.readline().split()]
k -= 1

candidates = [(k,0)]
res = [-1 for i in range(n)]
res[k] = 0
already = set()
while len(candidates) > 0 or len(already) < n:
    candidate, cost = heapq.heappop(candidates)
    already.add(candidate)
    res[candidate] = cost
    for goal, distance in graph[candidate]:
        if res[goal] < 0:
            heapq.heappush(candidates, (goal, cost + distance))

for i in range(q):
    x, y = [int(i) for i in sys.stdin.readline().split()]
    x -= 1
    y -= 1
    print(int(res[x] + res[y]))

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10**7)
n=int(input())
d=[10**20 for i in range(n)] 
g=[[] for i 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())
k-=1
f=[False for i in range(n)]
d[k]=0

def dfs(s,c):
    f[s]=True
    d[s]=c
    for sg in g[s]:
        if not f[sg[0]]:
            dfs(sg[0],c+sg[1])
dfs(k,0)

lq=[]
for _ in range(q):
    lq.append(list(map(int,input().split())))
for sq in lq:
    print(d[sq[0]-1]+d[sq[1]-1])

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
l=[list() for i in range(N)]
for i in range(N-1):
    a,b,c=map(int,input().split())
    l[a-1].append((b-1,c))
    l[b-1].append((a-1,c))
Q,K=map(int,input().split())
L=[None]*N
L[K-1]=0
t=1
s={K-1}
while t<N:
    g=set()
    for i in s:
        for j in l[i]:
            if L[j[0]]==None:
                L[j[0]]=L[i]+j[1]
                g.add(j[0])
                t+=1
    s=g
for _ in range(Q):
    x,y=map(int,input().split())
    print(L[x-1]+L[y-1])

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
l=[list() for i in range(N)]
for i in range(N-1):
    a,b,c=map(int,input().split())
    l[a-1].append((b-1,c))
    l[b-1].append((a-1,c))
Q,K=map(int,input().split())
L=[None]*N
L[K-1]=0
t=1
s={K-1}
while t<N:
    g=set()
    for i in s:
        for j in l[i]:
            if L[j[0]]==None:
                L[j[0]]=L[i]+j[1]
                g.add(j[0])
                t+=1
    s=g
for _ in range(Q):
    x,y=map(int,input().split())
    print(L[x-1]+L[y-1])

Solution (Python):
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
q,k=map(int,input().split())
ql=[list(map(int,input().split())) for i in range(q)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append([l[i][1]-1,l[i][2]])
  connection[l[i][1]-1].append([l[i][0]-1,l[i][2]])

def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=[v]
  next2=set()
  visited=[-1]*n
  visitct=0
  while len(next)!=0 and visitct!=n:
    for i in range(len(next)):
      if visited[next[i]]==-1:
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j][0]]==-1:
            distance[connection[next[i]][j][0]]=distance[next[i]]+connection[next[i]][j][1]
            next2.add(connection[next[i]][j][0])
    next=list(next2)
    next2=set()
  return distance
x=bfs(k-1)
for i in range(q):
  print(x[ql[i][0]-1]+x[ql[i][1]-1])

Solution (Python):
from collections import deque
INFTY = 10**14
N = int(input())
G = {}
for _ in range(N-1):
    a,b,c = map(int,input().split())
    if a not in G:
        G[a] = []
    G[a].append((b,c))
    if b not in G:
        G[b] = []
    G[b].append((a,c))
Q,K = map(int,input().split())
d = [INFTY for _ in range(N+1)]
d[K] = 0
hist = [0 for _ in range(N+1)]
heap = deque([K])
hist[K] = 1
while heap:
    cur = heap.popleft()
    for x in G[cur]:
        if hist[x[0]]==0:
            d[x[0]] = d[cur]+x[1]
            heap.append(x[0])
            hist[x[0]] = 1
for _ in range(Q):
    x,y = map(int,input().split())
    print(d[x]+d[y])

Solution (Python):
N=int(input())
edges=[list(map(int,input().split())) for i in range(N-1)]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
root=[[] for _ in range(N)]
for a,b,c in edges:
        root[a-1].append((b-1,c))
        root[b-1].append((a-1,c))
d=[-1]*N
s=[K-1]
d[K-1]=0
while s:
        l=s.pop()

        for i,c in root[l]:
                if d[i]==-1:
                        d[i]=d[l]+c
                        s.append(i)
for i in range(Q):
        print(d[xy[i][0]-1]+d[xy[i][1]-1])

Solution (Python):
N=int(input())
edges=[list(map(int,input().split())) for i in range(N-1)]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
root=[[] for _ in range(N)]
for a,b,c in edges:
        root[a-1].append((b-1,c))
        root[b-1].append((a-1,c))
d=[-1]*N
s=[K-1]
d[K-1]=0
while s:
        l=s.pop()

        for i,c in root[l]:
                if d[i]==-1:
                        d[i]=d[l]+c
                        s.append(i)
for i in range(Q):
        print(d[xy[i][0]-1]+d[xy[i][1]-1])

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

n=int(input())

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

dis=[None]*(n+1)
def set_dist(x,d):
    dis[x]=d
    for y,f in edge[x]:
        if dis[y] is not None:
            continue
        set_dist(y,d+f)
set_dist(k,0)

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

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

Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(Q)]

dist = [0] * N

def dfs(v, pv, dis):
    for i in to[v]:
        if i[0] != pv:
            dfs(i[0], v, dis+i[1])
    dist[v] = dis

dfs(K-1, -1, 0)

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

Solution (Python):
N = int(input())
Edge = [list(map(int,input().split())) for i in range(N-1)]
Q,K = map(int,input().split())
Query = [list(map(int,input().split())) for i in range(Q)]

Graph = [[] for i in range(N)]
for edge in Edge:
    Graph[edge[0]-1].append([edge[1]-1,edge[2]])
    Graph[edge[1]-1].append([edge[0]-1,edge[2]])

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

stack = [K-1]
while stack:
    node = stack.pop()
    for adj in Graph[node]:
        if Distance[adj[0]] == -1:
            Distance[adj[0]] = Distance[node] + adj[1]
            stack.append(adj[0])

for query in Query:
    print(Distance[query[0]-1]+Distance[query[1]-1])

Solution (Python):
from collections import *
from heapq import*
import sys
input=sys.stdin.readline
d=defaultdict(list)
n=int(input())
 
for s in range(n-1):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])

 
def DIJKSTRA(point,d):
    cost      = {node:1e18 for node in d.keys()}
    Q         = []  
    cost[point]=0  
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost
 
q,k=map(int,input().split())
y=DIJKSTRA(k,d)
 
for i in range(q):
    a,b=map(int,input().split())
    print(y[a]+y[b])

Solution (Python):
from collections import *
from heapq import*
import sys
input=sys.stdin.readline
d=defaultdict(list)
n=int(input())
 
for s in range(n-1):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])

 
def DIJKSTRA(point,d):
    cost      = {node:float("inf") for node in d.keys()}
    Q         = []  
    cost[point]=0  
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost
 
q,k=map(int,input().split())
y=DIJKSTRA(k,d)
 
for i in range(q):
    a,b=map(int,input().split())
    print(y[a]+y[b])

Solution (Python):
from collections import *
from heapq import*
import sys
input=sys.stdin.readline
d=defaultdict(list)
n=int(input())
 
for s in range(n-1):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])

 
def DIJKSTRA(point,d):
    cost      = {node:1e18 for node in d.keys()}
    Q         = []  
    cost[point]=0  
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost
 
q,k=map(int,input().split())
y=DIJKSTRA(k,d)
 
for i in range(q):
    a,b=map(int,input().split())
    print(y[a]+y[b])

Solution (Python):
from collections import *
from heapq import*
import sys
input=sys.stdin.readline
d=defaultdict(list)
n=int(input())
 
for s in range(n-1):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])

 
def DIJKSTRA(point,d):
    cost      = {node:1e18 for node in d.keys()}
    Q         = []  
    cost[point]=0  
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost
 
q,k=map(int,input().split())
y=DIJKSTRA(k,d)
 
for i in range(q):
    a,b=map(int,input().split())
    print(y[a]+y[b])

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

def dfs(v,d):
    memo[v] = d
    for i in graph[v]:
        if memo[i[0]] != -1:continue
        dfs(i[0],d+i[1])

n = int(input())
graph = [[] for _ in range(n)]
memo = [-1]*n
for i in range(n-1):
    x,y,z = map(int,input().split())
    graph[x-1].append([y-1,z])
    graph[y-1].append([x-1,z])
q,k = map(int,input().split())
ary = [list(map(int,input().split())) for _ in range(q)]
dfs(k-1,0)
for x,y in ary:
    print(memo[x-1]+memo[y-1])

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

def dfs(prev, now, fromK, t, d):
  d[now] = fromK
  for nl in (t[now]):
    if nl[0] != prev:
      dfs(now, nl[0], fromK+nl[1], t, d)

N = int(input())
T  = [[] for _ in range(N+1)]
for _ in range(N-1):
  a, b, l = map(int, input().split())
  T[a].append([b,l])
  T[b].append([a, l])
Q, K = map(int, input().split())
D = [0] * (N+1)
dfs(-1, K, 0, T, D)
for _ in range(Q):
  x, y = map(int, input().split())
  print(D[x]+D[y])

Solution (Python):
n=int(input())
abc=[list(map(int,input().split())) for _ in [0]*(n-1)]
q,k=map(int,input().split())
xy=[list(map(int,input().split())) for _ in [0]*q]
k-=1
tree=[[] for _ in [0]*n]
dist=[-1]*n
dist[k]=0
[tree[a-1].append([b-1,c]) for a,b,c in abc]
[tree[b-1].append([a-1,c]) for a,b,c in abc]

q=[k]

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

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

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

def dfs(v,d):
    memo[v] = d
    for i in graph[v]:
        if memo[i[0]] != -1:continue
        dfs(i[0],d+i[1])
        
n = int(input())
graph = [[] for _ in range(n)]
memo = [-1]*n
for i in range(n-1):
    x,y,z = map(int,input().split())
    graph[x-1].append([y-1,z])
    graph[y-1].append([x-1,z])
q,k = map(int,input().split())
ary = [list(map(int,input().split())) for _ in range(q)]
dfs(k-1,0)
print(*[memo[x-1]+memo[y-1] for x,y in ary],sep="\n")

Solution (Python):
n=int(input())
l=[[]for _ in range(n)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  l[a-1]+=[[b-1,c]]
  l[b-1]+=[[a-1,c]]
q,k=map(int,input().split())
k-=1
Q=[[k,0]]
c=[0]*n;c[k]=-1
while Q:
  p=[]
  for i,j in Q:
    for x,y in l[i]:
      if c[x]==0:
        c[x]=j+y
        p+=[[x,c[x]]]
  Q=p
c[k]=0
for i in range(q):
  x,y=map(int,input().split())
  print(c[x-1]+c[y-1])

Solution (Python):
from collections import deque

n=int(input())

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

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

dist=[-1 for i in range(n)]
dist[k]=0
que=deque()
que.append(k)
while que:
    x=que.popleft()
    for p in tree[x]:
        if dist[p[0]]==-1:
            que.append(p[0])
            dist[p[0]]=dist[x]+p[1]
ans=[]
for i in range(q):
    x,y=map(int,input().split())
    x-=1;y-=1
    ans.append(dist[x]+dist[y])

for i in ans:
    print(i)

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

ans = [-1 for _ in range(N + 1)]
stack = [(K, -1, 0)]  
while len(stack) > 0:
    v, p, c = stack.pop()
    ans[v] = c
    for next_v, next_c in nl[v]:
        if next_v == p:
            continue
        stack.append((next_v, v, c + next_c))
for x, y in [tuple(map(int, input().split())) for _ in range(Q)]:
    print(ans[x] + ans[y])

Solution (Python):
from collections import defaultdict as dd
from collections import deque as dq
N = int(input())
e = dd(list)
inf = 10 ** 15
for _ in range(N - 1):
  u, v, d = map(int, input().split())
  e[u].append((v, d))
  e[v].append((u, d))
Q, K = map(int, input().split())
d = [inf] * (N + 1)
d[K] = 0
q = dq([])
q.append(K)
while len(q):
  p = q.popleft()
  for t in e[p]:
    temp = d[p] + t[1]
    if d[t[0]] > temp:
      d[t[0]] = temp
      q.append(t[0])
for _ in range(Q):
  u, v = map(int, input().split())
  print(d[u] + d[v])