Problem: 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.

Submission attempts (in order):
from collections import deque

N = int(input())
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
    ai, bi, ci = map(int, input().split())
    edges[ai].append((bi, ci))
    edges[bi].append((ai, ci))
Q, K = map(int, input().split())

distance = [-1]*(N+1)
# def add_weight(k, pre):
#     for v in edges[k]:
#         d, w = v

#             distance[d] = w + distance[k]
#             add_weight(d, k)

que = deque()
que.append(K); distance[K] = 0
while len(que):
    a = que.popleft()
    for b, c in edges[a]:
        if distance[b] == -1:
            distance[b] = c + distance[a]
            que.append(b)

print(distance)

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

from collections import deque

N = int(input())
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
    ai, bi, ci = map(int, input().split())
    edges[ai].append((bi, ci))
    edges[bi].append((ai, ci))
Q, K = map(int, input().split())

distance = [-1]*(N+1)
# def add_weight(k, pre):
#     for v in edges[k]:
#         d, w = v

#             distance[d] = w + distance[k]
#             add_weight(d, k)

que = deque()
que.append(edges[K]); distance[K] = 0
while len(que):
    a = que.popleft()
    for b, c in a:
        if distance[b] == -1:
            distance[b] = c
            que.append(edges[b])

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

N = int(input())
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
    ai, bi, ci = map(int, input().split())
    edges[ai].append((bi, ci))
    edges[bi].append((ai, ci))
Q, K = map(int, input().split())

distance = [-1]*(N+1)
# def add_weight(k, pre):
#     for v in edges[k]:
#         d, w = v

#             distance[d] = w + distance[k]
#             add_weight(d, k)

que = deque()
que.append(edges[K]); distance[K] = 0
while len(que):
    a = que.popleft()
    for b, c in a:
        if distance[b] == -1:
            distance[b] = c
            que.append(edges[b])

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

N = int(input())
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
    ai, bi, ci = map(int, input().split())
    edges[ai].append((bi, ci))
    edges[bi].append((ai, ci))
Q, K = map(int, input().split())

weighted_nodes = [0]*(N+1)
def add_weight(k, pre):
    for v in edges[k]:
        d, w = v
        if d != pre:
            weighted_nodes[d] = w + weighted_nodes[k]
            add_weight(d, k)
add_weight(K, -1)

for _ in range(Q):
    s, e = map(int, input().split()))
    print(weighted_nodes[s] + weighted_nodes[e])

from collections import deque

N = int(input())
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
    ai, bi, ci = map(int, input().split())
    edges[ai].append((bi, ci))
    edges[bi].append((ai, ci))
Q, K = map(int, input().split())

distance = [-1]*(N+1)
# def add_weight(k, pre):
#     for v in edges[k]:
#         d, w = v

#             distance[d] = w + distance[k]
#             add_weight(d, k)

que = deque()
que.append(K); distance[K] = 0
while len(que):
    a = que.popleft()
    for b, c in edges[a]:
        if distance[b] == -1:
            distance[b] = c + distance[a]
            que.append(b)

# print(distance)

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

Verdicts: Wrong Answer

Wrong Answer

Runtime Error

Runtime Error

Accepted