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



Sample input:
5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5


Sample output:
3
2
4

Submission status: Accepted

Solution code:
N = int(input())
T = {i: [] for i in range(N)}
for _ 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())
S, D = [(-1, K - 1)], [0] * N
while len(S) > 0:
    p, c = S.pop()
    for g, d in T[c]:
        if g != p:
            D[g] = D[c] + d
            S.append((c, g))

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
e = dd(list)
for _ in range(N - 1):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
  e[v].append((u, c))
Q, K = map(int, input().split())
import heapq
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 6)
      v0 = v // (10 ** 6)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 6) + p[0])
    return d
dij = dijkstra(N, e)
p = dij.path(K, 0)

for _ in range(Q):
  u, v = map(int, input().split())
  print(p[u] + p[v])

Submission status: Accepted

Solution code:
from collections import deque
from collections import defaultdict
import sys
input = sys.stdin.readline

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

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

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

d = deque()
d.append(K)

while d:
    node = d.popleft()
    for bc in T[node]:
        b, c = bc
        if distance[b] == -1:
            distance[b] = distance[node] + c
            d.append(b)

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

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.buffer.readline

N = int(input())

edges = [[] for _ in range(N)]
for _ in range(N - 1):
    fr, to, cost = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append((to, cost))
    edges[to].append((fr, cost))

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

que = deque([(K, -1, 0)])
dist = [10**18] * N
while que:
    now, pr, d = que.popleft()
    dist[now] = d
    for to, c in edges[now]:
        if to == pr:
            continue
        que.append((to, now, d + c))

ans = [dist[x - 1] + dist[y - 1] for x, y in XY]
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
def main():
    readline=stdin.readline
    N=int(readline())
    G=[[] for _ in range(N)]
    a=[0]*(N-1)
    b=[0]*(N-1)
    c=[0]*(N-1)
    for i in range(N-1):
        a[i],b[i],c[i]=map(int,readline().split())
        a[i]-=1
        b[i]-=1
        G[a[i]].append([b[i],c[i]])
        G[b[i]].append([a[i],c[i]])
    Q,K=map(int,readline().split())
    K-=1
    x=[0]*Q
    y=[0]*Q
    for i in range(Q):
        x[i],y[i]=map(int,readline().split())
        x[i]-=1
        y[i]-=1

    que=deque([[K,0]])
    l=[0]*N
    is_searched=[False]*N
    is_searched[K]=True
    while len(que)>=1:
        now=que.popleft()
        l[now[0]]=now[1]
        for nex in G[now[0]]:
            if is_searched[nex[0]]==False:
                is_searched[nex[0]]=True
                que.append([nex[0],l[now[0]]+nex[1]])

    for i in range(Q):
        print(l[x[i]]+l[y[i]])

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

def dijkstra(s):
    used = [1] * N
    dp = [INF] * N
    dp[s] = 0
    hq = []
    used[s] = 0
    for i in cost[s]:
        heappush(hq, i)

    while hq:
        minv = heappop(hq)
        if used[minv[1]] == 0:
            continue
        v = minv[1]
        dp[v] = minv[0]
        used[v] = 0
        for i in cost[v]:
            if used[i[1]]:
                heappush(hq, [i[0] + dp[v], i[1]])
    return dp

INF = 10 ** 18
N = int(input())
cost = [[] for _ in range(N)]
for i in range(N - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    cost[a].append([c, b])
    cost[b].append([c, a])

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

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
G=[[] for i in range(n)]
dist=[-1]*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())
k-=1
q=deque()
q.append(k)
dist[k]=0
while q:
    cur=q.popleft()
    for nx,nx_d in G[cur]:
        if dist[nx]!=-1:continue
        dist[nx]=dist[cur]+nx_d
        q.append(nx)

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

Submission status: Accepted

Solution code:
# V: 頂点数
# g[v] = {(w, cost)}:
#     頂点vから遷移可能な頂点(w)とそのコスト(cost)
# r: 始点の頂点

from heapq import heappush, heappop
INF = 10**30
def dijkstra(N, G, s):
    dist = [INF] * N
    que = [(0, s)]
    dist[s] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for t, cost in G[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                heappush(que, (dist[t], t))
    return dist

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

Q, K = [int(i) for i in input().split()]
K -= 1

d = dijkstra(N, G, K)
# print(d)
for _ in range(Q):
    x, y = [int(i)-1 for i in input().split()]
    print(d[x]+d[y])

Submission status: Accepted

Solution code:
def main():
    from heapq import heappop, heappush
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b, c = (int(i) for i in input().split())
        edge[a-1].append((c, b-1))
        edge[b-1].append((c, a-1))
    Q, K = (int(i) for i in input().split())

    def dijkstra(s, G):
        d = [10**12]*N
        used = [True] * N  # True:未確定
        d[s] = 0
        used[s] = False
        edges = []
        for e in G[s]:
            heappush(edges, e)
        while len(edges):
            c, v = heappop(edges)
            if not used[v]:
                continue
            d[v] = c
            used[v] = False
            for nexc, nexv in G[v]:
                if used[nexv]:
                    heappush(edges, (nexc+c, nexv))
        return d

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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

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

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
def dijkstra(s,n,edge):
  inf=10**20
  ans=[inf]*n
  ans[s]=0
  h=[[0,s]]
  while h:
    c,v=heappop(h)
    if ans[v]<c:continue
    for u,t in edge[v]:
      if c+t<ans[u]:
        ans[u]=c+t
        heappush(h,[c+t,u])
  return ans
n=int(input())
edge=[[]for _ in range(n)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  a-=1;b-=1
  edge[a].append([b,c])
  edge[b].append([a,c])
q,k=map(int,input().split())
k-=1
xy=[list(map(int,input().split()))for _ in range(q)]
for i in range(q):xy[i][0]-=1;xy[i][1]-=1
edge=dijkstra(k,n,edge)
for x,y in xy:print(edge[x]+edge[y])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
INF = 10**9+1
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())
dist = [INF]*(n+1)


def dfs(v1, parent, add):
    dist[v1] = add
    for v2, d in graph[v1]:
        if v2 == parent:
            continue
        dfs(v2, v1, add + d)

dfs(k, -1, 0)

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

Que=deque([[k-1,0]])

while Que:
    b,c=Que.popleft()
    distance[b]=c
    for pb,pc in X[b]:
        if distance[pb]==-1:
            Que.append([pb,c+pc])

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

Submission status: Accepted

Solution code:
from collections import deque

n=int(input())
X=[[] for _ in range(n)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    X[a-1].append([b-1,c])
    X[b-1].append([a-1,c])
    
visited=[0]*n
distance=[0]*n

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

Que=deque([[k-1,0]])

while Que:
    b,c=Que.popleft()
    if visited[b]==1:
        continue
    visited[b]=1
    distance[b]=c
    for pb,pc in X[b]:
        Que.append([pb,c+pc])

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

Submission status: Accepted

Solution code:
# Author: cr4zjh0bp
# Created: Sat Mar 28 15:38:17 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import deque

n = ni()
abc = nan(n - 1)
q, k = na()
k -= 1
xy = nan(q)
tree = [[] for _ in range(n)]
for i in range(n - 1):
    a, b, c = abc[i]
    a -= 1
    b -= 1
    tree[a].append((b, c))
    tree[b].append((a, c))

def bfs():
    q = deque()
    q.append(k)
    dist = [-1] * n
    dist[k] = 0
    while len(q):
        p = q.popleft()
        for i, w in tree[p]:
            if dist[i] != -1:
                continue
            dist[i] = dist[p] + w
            q.append(i)
    return dist

dist = bfs()
for i in range(q):
    x, y = xy[i]
    x -= 1
    y -= 1
    print(dist[x] + dist[y])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
N = int(input())
T = [[]for i in range(N+1)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    T[a].append((b,c))
    T[b].append((a,c))
Q,K = map(int,input().split())
D = [0]*(N+1)
def f(v,p,cost):
    global T,K,D
    for C in T[v]:
        if C[0]!=p:
            D[C[0]] = cost+C[1]
            f(C[0],v,cost+C[1])
f(K,0,0)
for i in range(Q):
    x,y = map(int,input().split())
    print(D[x]+D[y])

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
tree = dict()
graph = defaultdict(list)

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

q, k = (int(x) for x in input().split())

dist = dict()
stack = [k,]
visited = [False for _ in range(n+1)]
dist[k] = 0
visited[k] = True

while stack:
    new_stack = []
    for node in stack:
        for next_node in graph[node]:
            if not visited[next_node]:
                visited[next_node]  = True
                dist[next_node] = dist[node] + tree[node, next_node]
                new_stack.append(next_node)
    stack = new_stack

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

Submission status: Accepted

Solution code:
N = int(input())

#高速化dijkstra
import heapq
def dijkstra_heap(s,edge):
  #始点sから各頂点への最短距離
  d = [float("inf")] * (N+1)
  used = [False] * (N+1)
  d[s] = 0
  used[s] = True
  edgelist = []
  #edgelist : (sからの暫定(未確定)最短距離,頂点)のリスト
  #edge[s] : sから出る枝の(重み,終点)の配列
  for w,v in edge[s]:
    heapq.heappush(edgelist,w*10**6+v) #sの隣の点は枝の重さがそのまま暫定最短距離となる
  while len(edgelist):
    #まだ使われてない頂点の中から最小の距離のものを探す→確定させる
    minedge = heapq.heappop(edgelist)
    #minedge : (sからの(確定)最短距離,頂点)
    v = minedge%10**6
    if used[v]:
      continue
    d[v] = minedge//10**6
    used[v] = True
    for w,u in edge[v]:
      if not used[u]:
        heapq.heappush(edgelist,(d[v]+w)*10**6+u)
  return d

################################

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

for _ in range(N-1):
  A, B, C = map(int, input().split())
  edge[A].append((C,B))
  edge[B].append((C,A))

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

d = dijkstra_heap(K,edge)

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

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

Submission status: Accepted

Solution code:
import heapq
import sys

N = int(input())
d = [[] for i in range(N)]
for i in range(N - 1):
	a, b, c = map(int, input().split())
	d[a - 1].append([b - 1, c])
	d[b - 1].append([a - 1, c])
Q, K = map(int, input().split())
e = [[0, K - 1]]
f = [False] * N
g = [sys.maxsize] * N
g[K - 1] = 0
while len(e):
	h = heapq.heappop(e)
	f[h[1]] = True
	for i in d[h[1]]:
		if not f[i[0]]:
			if g[h[1]] + i[1] < g[i[0]]:
				g[i[0]] = g[h[1]] + i[1]
				heapq.heappush(e, [g[i[0]], i[0]])
for i in range(Q):
	x, y = map(int, input().split())
	print(g[x - 1] + g[y - 1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
def dfs_rec(start,prev,c):
    cost[start] = cost[prev] + c
    for node,c in tr[start]:
        if node!=prev:
            dfs_rec(node,start,c)
    return


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

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

Submission status: Accepted

Solution code:
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
import copy
input=lambda :sys.stdin.readline().rstrip()

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)]
data=[[] for i in range(N+1)]
for a,b,c in ABC:
    data[a].append([b,c])
    data[b].append([a,c])

visited=set()
stack=deque([[K,0]])
lst=[0 for i in range(N+1)]
while stack:
    a,m=stack.popleft()
    lst[a]=m
    for p,c in data[a]:
        if not p in visited:
            visited.add(p)
            stack.append([p,m+c])

for x,y in XY:
    print(lst[x]+lst[y])

Submission status: Accepted

Solution code:
#070_D
from heapq import heappop, heappush
import sys
sys.setrecursionlimit(100000)
inf = 10 ** 15

def dijkstra(s):
    que = []
    d[s] = 0
    heappush(que, (0,s))
    
    while len(que):
        dist, node = heappop(que)
        
        if d[node] < dist:
            continue
        for to, cost in edges[node]:
            if d[to] > dist + cost:
                d[to] = dist + cost
                heappush(que, (d[to], to))
                
n = int(input())
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    edges[a-1].append((b-1, c))
    edges[b-1].append((a-1, c))
    
q, k = map(int, input().split())
d = [inf for _ in range(n)]
dijkstra(k-1)

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

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
G=[[] for i in range(n)]
dist=[-1]*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())
k-=1

dist[k]=0
q=deque()
q.append(k)
while q:
    cur=q.popleft()
    for nx,nx_dist in G[cur]:
        if dist[nx]==-1:
            dist[nx]=dist[cur]+nx_dist
            q.append(nx)

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

Submission status: Accepted

Solution code:
import heapq
def dijkstra_heap(s):
    d = [float("inf")] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d
import sys
input = sys.stdin.readline
n =int(input())
 
edge = [[] for i in range(n)]
#edge[i] : [weght,to]
for i in range(n-1):
    a, b, c = map(int,input().split())
    a, b = a-1, b-1
    edge[a].append([c,b])
    edge[b].append([c,a]) 
q, k = map(int, input().split())
k = k-1
d = dijkstra_heap(k)
for i in range(q):
  x, y = map(int, input().split())
  x, y = x-1, y-1
  print(d[x]+d[y])

Submission status: Accepted

Solution code:
from collections import deque
def main():
    n = int(input())
    tree = [[] for _ in range(n+1)]

    for i in range(n-1):
        a, b, c = map(int, input().split())
        tree[a].append([b, c])
        tree[b].append([a, c])
    q, k = map(int, input().split())
    que = deque([k])
    visit = [-1 for _ in range(n+1)]
    visit[k] = 0
    while que:
        pos = que.popleft()
        for i, j in tree[pos]:
            if visit[i] < 0:
                visit[i] = visit[pos]+j
                que.append(i)
    for i in range(q):
        x, y = map(int, input().split())
        print(visit[x]+visit[y])

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    tree = [[] for _ in range(n+1)]

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

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

    from collections import deque
    que = deque([k])
    visit = [-1 for _ in range(n+1)]
    visit[k] = 0
    while que:
        pos = que.popleft()
        for i, j in tree[pos]:
            if visit[i] < 0:
                visit[i] = visit[pos]+j
                que.append(i)
    for i in range(q):
        x, y = map(int, input().split())
        print(visit[x]+visit[y])

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
tree = [[] for _ in range(n+1)]

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

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

from collections import deque
que = deque([k])
visit = [-1 for _ in range(n+1)]
visit[k] = 0
while que:
    pos = que.popleft()
    for i, j in tree[pos]:
        if visit[i] < 0:
            visit[i] = visit[pos]+j
            que.append(i)
for i in range(q):
    x, y = map(int, input().split())
    print(visit[x]+visit[y])

Submission status: Accepted

Solution code:
import sys
rline = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(rline())
graph = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b, c = map(int, rline().split())
    a -= 1
    b -= 1
    graph[a].append([b, c])
    graph[b].append([a, c])
to_k = [0] * N


def dfs(node, parent, dist):
    to_k[node] = dist
    
    for child, d in graph[node]:
        if child != parent:
            dfs(child, node, dist + d)


def solve():
    Q, K = map(int, rline().split())
    K -= 1
    dfs(K, -1, 0)
    for _ in range(Q):
        x, y = map(lambda z: int(z) - 1, rline().split())
        print(to_k[x] + to_k[y])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N=int(input())
G=[[] for _ in range(N)]
for i in range(N-1):
  x,y,d=map(int,input().split())
  x-=1
  y-=1
  G[x].append((y,d))
  G[y].append((x,d))
Q,K=map(int,input().split())
stack=[K-1]
unseen=[1]*N
dist=[float('inf')]*N
dist[K-1]=0
while stack:
  u=stack.pop()
  unseen[u]=0
  for v,d in G[u]:
    if unseen[v]:
      dist[v]=min(dist[v],dist[u]+d)
      stack.append(v)
for q in range(Q):
  x,y=map(int,input().split())
  print(dist[x-1]+dist[y-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5 + 5)

N = int(input())

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

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

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

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


def dfs(s: int):
    for v, c in g[s]:
        if d[v] == -1:
            d[v] = d[s] + c
            dfs(v)


d[K] = 0
dfs(K)

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

Submission status: Accepted

Solution code:
import heapq as h
import sys

input=sys.stdin.readline

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

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

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

q=[]
q.append(K-1)
h.heapify(q)
sub=[]
h.heapify(sub)
while q!=[]:
    while q!=[]:
        x=h.heappop(q)
        for p in hen[x]:
            if distance[p[0]]==-1:
                h.heappush(sub,p[0])
            else:
                distance[x]=distance[p[0]]+p[1]
        if q==[]:
            q=sub
            sub=[]
            h.heapify(sub)
            break

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

for i in range(0,Q):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100005)

N = int(input())

edges = {n: [] for n in range(N+1)}

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

    edges[a].append((b, c))
    edges[b].append((a, c))

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


d = [-1] * (N+1)
d[K] = 0


def dfs(n: int):
    for m, c in edges[n]:
        if d[m] == -1:
            d[m] = d[n] + c
            dfs(m)


dfs(K)

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

Submission status: Accepted

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

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

not_yet = deque(dist[k-1])
already = [False]*n
already[k-1] = True
for a, b, c in dist[k-1]:
  already[b] = True

while not_yet:
  key = not_yet.popleft()
  a, b, c = key[0], key[1], key[2]
  dist_k[b] = dist_k[a]+c
  
  for value in dist[b]:
    if already[value[1]]:
      continue
    not_yet.append(value)
    already[value[1]] = True

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]", Q: int,
          K: int, x: "List[int]", y: "List[int]"):
    G = [[] for _ in range(N)]
    for ai, bi, ci in zip(a, b, c):
        ai -= 1
        bi -= 1
        G[ai].append((bi, ci))
        G[bi].append((ai, ci))

    m = [-1] * N
    q = deque()
    K -= 1
    m[K] = 0
    q.append(K)
    while q:
        i = q.popleft()
        for j, cj in G[i]:
            if m[j] >= 0:
                continue
            m[j] = m[i] + cj
            q.append(j)

    for xi, yi in zip(x, y):
        xi -= 1
        yi -= 1
        print(m[xi] + m[yi])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    c = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    Q = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (Q)  # type: "List[int]"
    y = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, a, b, c, Q, K, x, y)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
### dfs ###
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
N = int(input())
G = [[] for _ in range(N)]
dis = [-1]*N
for _ 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())
K -= 1
dis[K] = 0

def dfs(pos):
    for n_pos, n_cost in G[pos]:
        if dis[n_pos] != -1:
            continue
        dis[n_pos] = dis[pos]+n_cost
        dfs(n_pos)
dfs(K)

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

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
def main():
    N = int(input())
    depth = [-1 for _ in range(N)]
    tree = defaultdict(list)
    for _ in range(N-1):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        tree[a] += [[b,c]]
        tree[b] += [[a,c]]
    Q,K = map(int,input().split())
    K -= 1
    stack = deque([K])
    depth[K] = 0
    while stack:
        v = stack.popleft()
        for e in tree[v]:
            u,c = e
            if u == K:
                continue
            if depth[u] == -1:
                stack.appendleft(u)
                depth[u] = depth[v] + c

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
edge = [tuple(map(int, input().split())) for _ in range(n-1)]

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

inf = 10 ** 18
connect = [{} for _ in range(n)]
for a, b, c in edge:
    connect[a-1][b-1] = c
    connect[b-1][a-1] = c

k -= 1

dis = [inf] * n
dis[k] = 0
search = {k}
ng = set()
while search:
    v = search.pop()
    for w, c in connect[v].items():
        if w not in ng:
            dis[w] = c + dis[v]
            search.add(w)
    ng.add(v)

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

Submission status: Accepted

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

def d(tree, array, v):
  next_v = tree.get(v)
  
  for nv, nd in next_v:
    if array[nv] == -1:
      array[nv] = array[v] + nd
      d(tree, array, nv)
  

n = int(input())
tree = {}

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

array = [-1] * n
array[k] = 0

d(tree, array, k)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)


n = int(input())

GRAPH = [[] for _ in range(n + 1)]
EDGE = {}
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    a, b = min(a, b), max(a, b)
    GRAPH[a].append(b); GRAPH[b].append(a)
    EDGE[(a, b)] = c

def dfs(now, prev):
    for v in GRAPH[now]:
        if v == prev:
            continue
        next = v
        a, b = min(now, next), max(now, next)
        LENGTH[next] = LENGTH[now] + EDGE[(a, b)]
        dfs(next, now)

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

LENGTH = [0] * (n + 1)
dfs(k, 0)

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