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:
# -*- coding: utf-8 -*-

import sys
def input(): return sys.stdin.readline().strip()
    
from heapq import heappop, heappush

# 今回はダイクストラするので、データの持ち方は隣接リスト
N = int(input())
nodes = [[] for _ in range(N+1)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    # nodes[出発ノード](到着ノード, コスト))
    nodes[a].append((b, c))
    # 無向グラフなのでこっちも入れる
    nodes[b].append((a, c))

def dijkstra(nodes, start):
    # 最短距離メモ
    memo = [float('inf')] * (len(nodes))
    # スタート位置
    que = [(0, start)]
    memo[start] = 0
    # キューが空になるまで
    while len(que) != 0:
        # startからの距離, 現在のノード
        dist, cur = heappop(que)
        # 出発ノードcurの到着ノードでループ
        for nxt, cost in nodes[cur]:
            # 今回の経路のが短い時
            if memo[cur] + cost < memo[nxt]:
                memo[nxt] = memo[cur] + cost
                # 現在の移動距離をキューの優先度として、早い方から先に処理するようにする
                heappush(que, (memo[nxt], nxt))
    # ノードstartからの最短距離リストを返却
    return memo

Q, K = map(int, input().split())
# 引数：(ノードの隣接リスト, 出発ノード)
memo = dijkstra(nodes, K)

for i in range(Q):
    x, y = map(int, input().split())
    # 今回は全てKを経由するので、Kからの距離さえ分かれば全部出る
    print(memo[x] + memo[y])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/abc070/editorial.pdf
・公式解が再帰だったのでやってみる
"""

import sys

# 再帰呼び出しの回数制限(デフォルト1000)
sys.setrecursionlimit(10 ** 9)

N = int(input())
nodes = [[] for _ in range(N+1)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    # nodes[出発ノード](到着ノード, コスト))
    nodes[a].append((b, c))
    # 無向グラフなのでこっちも入れる
    nodes[b].append((a, c))

memo = [0] * (N+1)
def dfs(cur, prev, dist):
    memo[cur] = dist
    for nxt, cost in nodes[cur]:
        if nxt == prev:
            continue
        dfs(nxt, cur, dist+cost)

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

for i in range(Q):
    x, y = map(int, input().split())
    # 今回は全てKを経由するので、Kからの距離さえ分かれば全部出る
    print(memo[x] + memo[y])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
・ダイクストラ(優先度付きキュー)
"""

from heapq import heappop, heappush

# 今回はダイクストラするので、データの持ち方は隣接リスト
N = int(input())
nodes = [[] for _ in range(N+1)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    # nodes[出発ノード](到着ノード, コスト))
    nodes[a].append((b, c))
    # 無向グラフなのでこっちも入れる
    nodes[b].append((a, c))

def dijkstra(nodes, start):
    # 最短距離メモ
    memo = [float('inf')] * (len(nodes))
    # スタート位置
    que = [(0, start)]
    memo[start] = 0
    # キューが空になるまで
    while len(que) != 0:
        # startからの距離, 現在のノード
        dist, cur = heappop(que)
        # 出発ノードcurの到着ノードでループ
        for nxt, cost in nodes[cur]:
            # 今回の経路のが短い時
            if memo[cur] + cost < memo[nxt]:
                memo[nxt] = memo[cur] + cost
                # 現在の移動距離をキューの優先度として、早い方から先に処理するようにする
                heappush(que, (memo[nxt], nxt))
    # ノードstartからの最短距離リストを返却
    return memo

Q, K = map(int, input().split())
# 引数：(ノードの隣接リスト, 出発ノード)
memo = dijkstra(nodes, K)

for i in range(Q):
    x, y = map(int, input().split())
    # 今回は全てKを経由するので、Kからの距離さえ分かれば全部出る
    print(memo[x] + memo[y])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
・ダイクストラ(優先度付きキュー)
"""

from heapq import heappop, heappush

# 今回はダイクストラするので、データの持ち方は隣接リスト
N = int(input())
nodes = [[] for _ in range(N+1)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    # nodes[出発ノード](到着ノード, コスト))
    nodes[a].append((b, c))
    # 無向グラフなのでこっちも入れる
    nodes[b].append((a, c))

def dijkstra(nodes, start):
    # 最短距離メモ
    memo = [float('inf')] * (len(nodes))
    # スタート位置
    que = [(0, start)]
    memo[start] = 0
    # キューが空になるまで
    while len(que) != 0:
        # startからの距離, 現在のノード
        dist, cur = heappop(que)
        # 出発ノードcurの到着ノードでループ
        for i in range(len(nodes[cur])):
            nxt, cost = nodes[cur][i]
            # 今回の経路のが短い時
            if memo[cur] + cost < memo[nxt]:
                memo[nxt] = memo[cur] + cost
                # 現在の移動距離をキューの優先度として、早い方から先に処理するようにする
                heappush(que, (memo[nxt], nxt))
    # ノードstartからの最短距離リストを返却
    return memo

Q, K = map(int, input().split())
# 引数：(ノードの隣接リスト, 出発ノード)
memo = dijkstra(nodes, K)

for i in range(Q):
    x, y = map(int, input().split())
    # 今回は全てKを経由するので、Kからの距離さえ分かれば全部出る
    print(memo[x] + memo[y])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
・ダイクストラ(優先度付きキュー)
"""

from heapq import heappop, heappush

# 今回はダイクストラするので、データの持ち方は隣接リスト
N = int(input())
nodes = [[] for _ in range(N+1)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    # nodes[出発ノード](到着ノード, コスト))
    nodes[a].append((b, c))
    # 無向グラフなのでこっちも入れる
    nodes[b].append((a, c))

def dijkstra(nodes, start):
    # 最短距離メモ
    memo = [float('inf')] * (len(nodes))
    # 訪問済メモ
    visited = [False] * (len(nodes))
    # スタート位置
    que = [(0, start)]
    memo[start] = 0
    # キューが空になるまで
    while len(que) != 0:
        # startからの距離, 現在のノード
        dist, cur = heappop(que)
        # 訪問済にする
        visited[cur] = True
        # 出発ノードcurの到着ノードでループ
        for i in range(len(nodes[cur])):
            nxt, cost = nodes[cur][i]
            # 訪問済ではないかつ今回の経路のが短い時
            if not visited[nxt] and memo[cur] + cost < memo[nxt]:
                memo[nxt] = memo[cur] + cost
                # 現在の移動距離をキューの優先度として、早い方から先に処理するようにする
                heappush(que, (memo[nxt], nxt))
    # ノードstartからの最短距離リストを返却
    return memo

Q, K = map(int, input().split())
# 引数：(ノードの隣接リスト, 出発ノード)
memo = dijkstra(nodes, K)

for i in range(Q):
    x, y = map(int, input().split())
    # 今回は全てKを経由するので、Kからの距離さえ分かれば全部出る
    print(memo[x] + memo[y])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
・ダイクストラ(優先度付きキュー)
"""

from heapq import heappop, heappush

# 今回はダイクストラするので、データの持ち方は隣接リスト
N = int(input())
nodes = [[] for _ in range(N+1)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    # nodes[出発ノード](到着ノード, コスト))
    nodes[a].append((b, c))
    nodes[b].append((a, c))

def dijkstra(nodes, start):
    # 最短距離メモ
    memo = [float('inf')] * (len(nodes))
    # 訪問済メモ
    visited = [False] * (len(nodes))
    # スタート位置
    que = [(0, start)]
    memo[start] = 0
    # キューが空になるまで
    while len(que) != 0:
        # startからの距離, 現在のノード
        dist, cur = heappop(que)
        # 訪問済にする
        visited[cur] = True
        # 出発ノードcurの到着ノードでループ
        for i in range(len(nodes[cur])):
            nxt, cost = nodes[cur][i]
            # 訪問済ではない時だけ
            if not visited[nxt]:
                memo[nxt] = min(memo[cur] + cost, memo[nxt])
                # 現在の移動距離をキューの優先度として、早い方から先に処理するようにする
                heappush(que, (memo[nxt], nxt))
    # ノードstartからの最短距離リストを返却
    return memo

Q, K = map(int, input().split())
# 引数：(ノードの隣接リスト, 出発ノード)
memo = dijkstra(nodes, K)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
・ダイクストラ(優先度付きキュー)
"""

from heapq import heappop, heappush
from collections import deque

# 今回はダイクストラするので、データの持ち方は隣接リスト
N = int(input())
nodes = [deque() for _ in range(N+1)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    # nodes[出発ノード](到着ノード, コスト))
    nodes[a].append((b, c))
    nodes[b].append((a, c))

def dijkstra(nodes, start):
    # 最短距離メモ
    memo = [float('inf')] * (len(nodes))
    # 訪問済メモ
    visited = [False] * (len(nodes))
    # スタート位置
    que = [(0, start)]
    memo[start] = 0
    # キューが空になるまで
    while len(que) != 0:
        # startからの距離, 現在のノード
        dist, cur = heappop(que)
        # 訪問済にする
        visited[cur] = True
        # 出発ノードcurの到着ノードでループ
        while len(nodes[cur]) != 0:
            nxt, cost = nodes[cur].popleft()
            # 訪問済ではない時だけ
            if not visited[nxt]:
                memo[nxt] = min(memo[cur] + cost, memo[nxt])
                # 現在の移動距離をキューの優先度として、早い方から先に処理するようにする
                heappush(que, (memo[nxt], nxt))
    # ノードstartからの最短距離リストを返却
    return memo

Q, K = map(int, input().split())
# 引数：(ノードの隣接リスト, 出発ノード)
memo = dijkstra(nodes, K)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
N = int(input())
G = [[] for i in range(N)]
for i 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 = [-1] * N
dist[K] = 0


def dfs(n):
    for v, c in G[n]:
        if dist[v] < 0:
            dist[v] = dist[n] + c
            dfs(v)


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

Submission status: Accepted

Solution code:
V = int(input())
E = V - 1
G = {}
for i in range(V):
    G[i] = {}

for _ in range(E):
    s, t, c = [int(_) for _ in input().split()]
    s -= 1  # 0-indexed
    t -= 1  # 0-indexed
    G[s][t] = c
    G[t][s] = c
Q, K = [int(_) for _ in input().split()]
K -= 1  # 0-indexed
XY = [[int(_) for _ in input().split()] for _ in range(Q)]

INF = float('inf')
D = [INF] * V
D[K] = 0
cand = []
for j in G[K].keys():
    cand += [(K, j)]
while True:
    if cand:
        x, y = cand.pop()
        if D[y] == INF:
            D[y] = D[x] + G[x][y]
            for z in G[y].keys():
                cand += [(y, z)]
    else:
        break
for x, y in XY:
    x -= 1
    y -= 1
    print(D[x] + D[y])

Submission status: Accepted

Solution code:
import heapq

V = int(input())
E = V - 1
G = {}
for i in range(V):
    G[i] = {}

for _ in range(E):
    s, t, c = [int(_) for _ in input().split()]
    s -= 1  # 0-indexed
    t -= 1  # 0-indexed
    G[s][t] = c
    G[t][s] = c
Q, K = [int(_) for _ in input().split()]
K -= 1  # 0-indexed
XY = [[int(_) for _ in input().split()] for _ in range(Q)]

INF = float('inf')

que = []
i = K
d = 0
D = [INF] * V
D[i] = 0
used = [False] * V
used[i] = True

while True:
    for j in G[i].keys():
        heapq.heappush(que, (d + G[i][j], j))
    v = -1
    while que:
        d, j = heapq.heappop(que)
        if not used[j]:
            v = j
            break
    if v == -1:
        break
    else:
        used[v] = True
        D[v] = d
        i = v
for x, y in XY:
    x -= 1  # 0-indexed
    y -= 1  # 0-indexed
    print(D[x] + D[y])

Submission status: Accepted

Solution code:
n = int(input())
graph = [dict() for _ in range(n)]

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

q, k = map(int, input().split())
xy = []
for i in range(q):
    x, y = map(int, input().split())
    xy.append([x - 1, y - 1])
depth = [0 for _ in range(n)]
prev = [False for _ in range(n)]
depth[k - 1] = 0

import sys

sys.setrecursionlimit(10 ** 6)


def dfs(now, prev, cost, graph, depth):
    depth[now] = cost
    for k, v in graph[now].items():
        if k == prev:
            continue
        dfs(k, now, cost + v,  graph, depth)
    return depth


depth = dfs(k - 1, -1, 0, graph, depth)
for x, y in xy:
    print(depth[x] + depth[y])

Submission status: Accepted

Solution code:
n = int(input())
graph = [dict() for _ in range(n)]

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

q, k = map(int, input().split())
xy = []
for i in range(q):
    x, y = map(int, input().split())
    xy.append([x-1, y-1])
depth = [0 for _ in range(n)]
prev = [False for _ in range(n)]
depth[k-1] = 0

import sys
sys.setrecursionlimit(10 ** 6)


def dfs(now, graph, depth, prev):
    if len(graph[now]) == 0 or prev[now]:
        return
    prev[now] = True
    for k, v in graph[now].items():
        if not prev[k]:
            depth[k] += depth[now] + v
            dfs(k, graph, depth, prev)
    return depth


depth = dfs(k-1, graph, depth, prev)
for x, y in xy:
    print(depth[x] + depth[y])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict,deque
N = int(input())
abc = [list(map(int, input().split())) for _ in range(N-1)]
Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(Q)]

# graph = defaultdict(lambda: defaultdict(int))
graph = [defaultdict(int) for _ in range(N)]

for a,b,c in abc:
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

def xfs(v):
    dist = [-1 for _ in range(N)]
    dist[v] = 0
    que = deque()
    que.append(v)
    while len(que) > 0:
        i = que.pop()  # 深さ優先探索        
        # i = que.popleft() #幅優先探索
        for n, val in graph[i].items():
            if dist[n] == -1:
                dist[n] = dist[i] + val
                que.append(n)
    return dist

dist = xfs(K-1)

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

Submission status: Accepted

Solution code:
n = int(input())
d = []
for i in range(n - 1):#h:高さ
    d.append([int(m) for m in input().split()])
q, k = map(int, input().split())
z = []
for i in range(q):#h:高さ
    z.append([int(m) for m in input().split()])

for i in range(n - 1):
    d[i][0] -= 1
    d[i][1] -= 1
for i in range(q):
    z[i][0] -= 1
    z[i][1] -= 1
def BFS(k, edges, N):
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a]+=[(b,c)]
    roots[b]+=[(a,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

root = BFS(k - 1, d, n)

for i in range(q):
    print(root[z[i][0]] + root[z[i][1]])

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict

N = int(input())

graph = defaultdict(list)

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


dist_node = [float("inf") for i in range(N)]
ques, s = list(map(int, input().split()))
s = s - 1
dist_node[s] = 0


Q = []
heapq.heappush(Q, (dist_node[s], s)) 

while Q: 
	dis, v = heapq.heappop(Q)
	if dist_node[v] < dis:
		continue
	for u, w in graph[v]:
		alt = dis + w
		if dist_node[u] > alt:
			dist_node[u] = alt
			heapq.heappush(Q, (alt, u))


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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
inf = 10**16
n = int(input())
edge = [[] for _ in range(n)]
for _ 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

d = [inf for _ in range(n)]
d[k] = 0
stack = [k]
while len(stack)>0:
    v = stack.pop()
    for u,c in edge[v]:
        if d[u]==inf:
            d[u] = d[v]+c
            stack.append(u)

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

for c in res:
    print(c)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

n=int(input())
m=[[] for i in range(n)]
for i in range(n-1):
    a,b,c=map(int, input().split())
    m[a-1].append([b-1,c])
    m[b-1].append([a-1,c])
q,k=map(int, input().split())
    
def reach(m,d,k):
    for i in m[k]:
        if d[i[0]]==-1:
            d[i[0]]=d[k]+i[1]
            reach(m,d,i[0])
d=[-1]*n
d[k-1]=0
reach(m,d,k-1)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def make_Graph(N, edges):#頂点の名前はi - 1で受け付ける
    graph = [ [] for i in range(N)]
    for edge in edges:
        a, b, c = edge
        graph[a].append((b,c))
        graph[b].append((a,c))
    return graph

def BFS(N, graph, start):
    Q = []
    V = []
    prev = [None] * N
    dd = [float("inf")] * N
    Q.append(start)
    dd[start] = 0
    while len(V) < N:
        a = Q.pop(0)
        V.append(a)
        for b, c in graph[a]:
            if b != prev[a]:
                Q.append(b)
                prev[b] = a
                dd[b] = dd[a] + c
    return dd

def DFS(N, graph, a, p, d):
    dd[a] = d
    for b, c in graph[a]:
        if b == p or dd[b] != 0:
            continue
        else:
            DFS(N, graph, b, a, d + c)

N = int(input())

sys.setrecursionlimit(100)

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

Q, K =(int(i) for i in input().split())
dd = [0] * N

try:
    DFS(N, graph, K-1, -1, 0)
except:
    dd = BFS(N, graph, K-1)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def make_Graph(N, edges):#頂点の名前はi - 1で受け付ける
    graph = [ [] for i in range(N)]
    for edge in edges:
        a, b, c = edge
        graph[a].append((b,c))
        graph[b].append((a,c))
    return graph

def BFS(N, graph, start):
    Q = []
    V = []
    prev = [None] * N
    dd = [float("inf")] * N
    Q.append(start)
    dd[start] = 0
    while len(V) < N:
        a = Q.pop(0)
        V.append(a)
        for b, c in graph[a]:
            if b != prev[a]:
                Q.append(b)
                prev[b] = a
                dd[b] = dd[a] + c
    return dd

def DFS(N, graph, a, p, d):
    dd[a] = d
    for b, c in graph[a]:
        if b == p or dd[b] != 0:
            continue
        else:
            DFS(N, graph, b, a, d + c)

N = int(input())

sys.setrecursionlimit(1000000)

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

Q, K =(int(i) for i in input().split())
dd = [0] * N

DFS(N, graph, K-1, -1, 0)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def make_Graph(N, edges):#頂点の名前はi - 1で受け付ける
    graph = [ [] for i in range(N)]
    for edge in edges:
        a, b, c = edge
        graph[a].append((b,c))
        graph[b].append((a,c))
    return graph

def BFS(N, graph, start):
    Q = []
    V = []
    prev = [None] * N
    dd = [float("inf")] * N
    Q.append(start)
    dd[start] = 0
    while len(V) < N:
        a = Q.pop(0)
        V.append(a)
        for b, c in graph[a]:
            if b != prev[a]:
                Q.append(b)
                prev[b] = a
                dd[b] = dd[a] + c
    return dd

def DFS(N, graph, a, p, d):
    dd[a] = d
    for b, c in graph[a]:
        if b == p or dd[b] != 0:
            continue
        else:
            DFS(N, graph, b, a, d + c)

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

Q, K =(int(i) for i in input().split())
dd = [0] * N

try:
    DFS(N, graph, K-1, -1, 0)
except:
    dd = BFS(N, graph, K-1)

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

Submission status: Accepted

Solution code:
n=int(input())
ro=[{}for i in range(n)]
dis=[-1]*n
for i in range(n-1):
    a,b,c=map(int,input().split())
    ro[a-1][b-1]=c
    ro[b-1][a-1]=c
q,k=map(int,input().split())
dis[k-1]=0
stack=[k-1]
while stack:
    s=stack.pop()
    for i,j in ro[s].items():
        if dis[i] == -1:
            dis[i]=dis[s]+j
            stack.append(i)
for i in range(q):
    x,y=map(int,input().split())
    x,y=x-1,y-1
    print(dis[x]+dis[y])

Submission status: Accepted

Solution code:
N=int(input())
Tree=[{} for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  Tree[a-1][b-1]=c
  Tree[b-1][a-1]=c
Q,K=map(int,input().split())
depth=[-1]*N
depth[K-1]=0
dfs_stack=[K-1]
while dfs_stack:
  s=dfs_stack.pop()
  for t,t_depth in Tree[s].items():
    if depth[t]==-1:
      depth[t]=depth[s]+t_depth
      dfs_stack.append(t)
      
for q in range(Q):
  x,y=map(int,input().split())
  print(depth[x-1]+depth[y-1])

Submission status: Accepted

Solution code:
import sys
#limit=sys.getrecursionlimit()
sys.setrecursionlimit(10000000)
#sys.setrecursionlimit(1000000000)

V=int(input().strip())
E=V-1
inf=3*10**15
G=[]
dist=[inf]*V

for i in range(V):
    G.append([])
for i in range(E):
    at,bt,ct=map(int,input().strip().split(' '))
    G[at-1].append([ct,bt-1])
    G[bt-1].append([ct,at-1])

visited=[False]*V
def dfs(v,p,d):
    #global d
    dist[v]=d
    for q in G[v]:
        if q[1]==p:
            continue
        dfs(q[1],v,d+q[0])

Q, K=map(int,input().strip().split(' '))
K-=1 #0-indexedに直す

dfs(K,-1,0)

x=[]
y=[]

for i in range(Q):
    xt, yt=map(int,input().strip().split(' '))
    x.append(xt-1)#0-indexedに直して入れる
    y.append(yt-1)#0-indexedに直して入れる
for i in range(Q):
    print(dist[x[i]]+dist[y[i]])

Submission status: Accepted

Solution code:
import sys
def dfs(L,start):
    stack = [start]

    path =[-1]*len(L)
    path[start] = 0
    while stack:
        node = stack.pop()
        for n in L[node]:
            if path[n[0]] < 0:
                path[n[0]] = path[node]  + n[1]
                stack.append(n[0])

    return path

#input
input = sys.stdin.readline
N = int(input())
p = []
for i in range(N-1):
    l = list(map(int,input().split()))
    p.append(l)

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

#neigher list
L = [ [] for i in range(N+1)]
for l in p:
    L[l[0]].append([l[1],l[2]])
    L[l[1]].append([l[0],l[2]])

d = dfs(L,K)

for i in range(Q):
    print(d[xy[i][0]]+ d[xy[i][1]])

Submission status: Accepted

Solution code:
import heapq
N = int(input())
src = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for i in range(N)]
for a,b,c in src:
    es[a-1].append((b-1,c))
    es[b-1].append((a-1,c))

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

INF = float('inf')
dists = [INF]*N
dists[K] = 0
hq = [(0,K)]
heapq.heapify(hq)

while hq:
    d,v = heapq.heappop(hq)
    for to,c in es[v]:
        if d+c >= dists[to]: continue
        dists[to] = d+c
        heapq.heappush(hq, (d+c, to))

for a,b in qs:
    print(dists[a-1] + dists[b-1])

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from heapq import heappush, heappop

def dijkstra(graph:list, node:int, start:int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのpriority queを作成
    dist[start] = 0
    heap = [(0,start)]
    
    # 未探索のノードをpriority queueに入れる
    while heap:
        cost, cur_node = heappop(heap)
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
    return dist

n = ni()
graph = [[] for _ in range(n)]
for _ in range(n-1):
    a,b,c = li()
    a -= 1
    b -= 1
    graph[a].append((c,b))
    graph[b].append((c,a))
    
q,k = li()

dist = dijkstra(graph,n,k-1)

xy = [tuple(li_()) for _ in range(q)]

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

N = int(input())
X, Y = [], []

tree = {key+1: [] for key in range(N)}  # 木構造はノードをキーにする辞書にしておく
# 必要なのは、あるノードを指定したときに、隣り合うノードと、コスト
#[(隣のノード, コスト)]の順で格納する

for n in range(N - 1):
    a, b, c = list(map(int, input().split()))
    tree[a].append((b, c))
    tree[b].append((a, c))  # 方向に依存しない格納

# for n in tree.keys():
#     tree[n] = list(set(tree[n]))  # 重複を削除
# こいつが原因ではない

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

cost = {}  # Kがkeyに行くまでにかかるコストの辞書


def dfs(v, p, d):
    """
    深さ優先探索
    再帰的に処理する
    args:
        v: 現在の頂点
        p: vの親(訪問元)
        d: 現在の距離
    """
    cost[v] = d
    for i, co in tree[v]:
        if i == p:
            continue
        dfs(i, v, d + co)


dfs(K, -1, 0)

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

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
path = {}
for i in range(n-1):
    a, b, c = list(map(int, input().split()))
    if not a in path.keys():
        path[a] = [(b, c)]
    else:
        path[a].append((b, c))
    if not b in path.keys():
        path[b] = [(a, c)]
    else:
        path[b].append((a, c))
q, k = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(q)]

dist = [None]*(n+1)
dist[k] = 0
que = deque([(k, 0)])
while len(que) > 0:
    node, d = que.popleft()
    dist[node] = d
    for node_next, d_next in path[node]:
        if dist[node_next] is None:
            que.append((node_next, d+d_next))
# print(dist)

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

Submission status: Accepted

Solution code:
from collections import deque
 
n = int(input())
path = {}
for i in range(n-1):
    a, b, c = list(map(int, input().split()))
    if not a in path.keys():
        path[a] = [(b, c)]
    else:
        path[a].append((b, c))
        
    if not b in path.keys():
        path[b] = [(a, c)]
    else:
        path[b].append((a, c))
q, k = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(q)]

dist = [None]*(n+1)
dist[k] = 0
que = deque([(k, 0)])
while len(que) > 0:
    node, d = que.popleft()
    dist[node] = d
    for node_next, d_next in path[node]:
        if dist[node_next] is None:
            que.append((node_next, d+d_next))
# print(dist)
 
for x, y in xy:
    print(dist[x]+dist[y])

Submission status: Accepted

Solution code:
N = int(input())
route = [{} for _ in range(N)]
dist = [-1] * N
for i in range(N - 1):
    a, b, d = map(int, input().split())
    route[a-1][b-1] = d
    route[b-1][a-1] = d

Q, K = map(int, input().split())
dist[K-1] = 0
dfs_stack = [K-1]
while dfs_stack:
    s = dfs_stack.pop()
    for t, t_dist in route[s].items():
        if dist[t] == -1:
            dist[t] = dist[s] + t_dist
            dfs_stack.append(t)
for i in range(Q):
    x, y = map(int, input().split())
    x, y = x - 1, y - 1
    print(dist[x] + dist[y])

Submission status: Accepted

Solution code:
import heapq
N = int(input())
G = [[] for i in range(N)]
for i 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


def dijkstra(x):
    d = [float('inf')] * N
    d[x] = 0
    visited = {x}

    # d, u
    hq = [(0, x)]

    while hq:
        u = heapq.heappop(hq)[1]
        visited.add(u)

        for node, cost in G[u]:
            if (node not in visited) and d[node] > d[u] + cost:
                d[node] = d[u] + cost
                heapq.heappush(hq, (d[u]+cost, node))
    return d


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

Submission status: Accepted

Solution code:
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]

path = defaultdict(lambda: [])
N = int(input())
for _ in range(N-1):
    a, b, c = inpl()
    path[a].append((b,c))
    path[b].append((a,c))

ctr = 1
Q, K = inpl()
now = {K}
dist = [0 for _ in range(N+1)]
while True:
    for na in now.copy():
        na = now.pop()
        for nb, nc in path[na]:
            dist[nb] = dist[na] + nc
            path[nb].remove((na,nc))
            now.add(nb)
            ctr += 1
    if ctr >=  N:
        break
for i in range(Q):
    x, y = inpl()
    print(dist[x]+dist[y])

Submission status: Accepted

Solution code:
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]

path = defaultdict(lambda: [])
N = int(input())
for _ in range(N-1):
    a, b, c = inpl()
    path[a].append((b,c))
    path[b].append((a,c))

ctr = 1
Q, K = inpl()
now = [K]
dist = [0 for _ in range(N+1)]
while True:
    for na in now.copy():
        na = now.pop()
        for nb, nc in path[na]:
            dist[nb] = dist[na] + nc
            path[nb].remove((na,nc))
            now.append(nb)
            ctr += 1
    if ctr >=  N:
        break
for i in range(Q):
    x, y = inpl()
    print(dist[x]+dist[y])

Submission status: Accepted

Solution code:
n=int(input())
abc=[list(map(int,input().split())) for _ in range(n-1)]
q,k=map(int,input().split())
xy=[list(map(int,input().split())) for _ in range(q)]

z=[[] for _ in range(n)]
for a,b,c in abc:
    z[a-1].append([b-1,c])
    z[b-1].append([a-1,c])

depth=[0 for _ in range(n)]
from collections import deque
que=deque([])
v,p,d=k-1,-1,0
que.append((v,p,d))
while que:
    v,p,d=que.pop()
    depth[v]=d
    for t in z[v]:
        if t[0]==p:
            continue
        que.append((t[0],v,d+t[1]))
for x,y in xy:
    print(depth[x-1]+depth[y-1])