Embassy Virtual Tree Problem

Embassy Virtual Tree Problem — ExecCode Hard DSA Practice

Solve the Embassy Virtual Tree problem on ExecCode. Free online hard DSA practice in Graph. Write and run code in Java, C++, Python — no signup required to run.

Problem description

A country is a weighted tree of cities. Only a handful of cities host embassies. The ministry wants the sum of pairwise distances among those embassy cities. Building the virtual tree on the key nodes (LCAs of consecutive keys in Euler order) compresses the huge tree down to O(|keys|) vertices, then a DFS sums the pairs. Treat edges as [u, v, weight]. Return the sum of distances between every unordered pair of nodes listed in keys. Duplicate keys are ignored. You are given: n — cities edges — weighted tree edges keys — embassy city indices Return sum of pairwise embassy distances. If fewer than two unique keys remain, the sum is 0. Distance uses edge weights, not hop counts.

Examples

Input {'n': 4, 'edges': [[0, 1, 2], [0, 2, 3], [2, 3, 4]], 'keys': [1, 3]}; Output 9. Input {'n': 3, 'edges': [[0, 1, 1], [0, 2, 1]], 'keys': [0, 0, 1]}; Output 1. Input {'n': 2, 'edges': [[0, 1, 5]], 'keys': [0]}; Output 0

Constraints

Weights are positive Keys may repeat

Practice Embassy Virtual Tree free on ExecCode. Browse DSA problems, topic map, and placement guides.