Centroid Pair Travel Sum Problem

Centroid Pair Travel Sum Problem — ExecCode Hard DSA Practice

Solve the Centroid Pair Travel Sum 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

Sum the weighted distances between every unordered pair of nodes in a tree. Centroid decomposition counts, for each centroid, pairs whose path crosses it, often with a Fenwick on depth. Reroot DP is the linear alternative: for each edge, pairs that cross it contribute weight leftsize rightsize. Edges [u, v, weight]. Return that total sum. You are given: n — nodes edges — weighted tree Return sum of all pairwise distances. Each pair counted once.

Examples

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

Constraints

Unordered pairs n = 1 → 0

Practice Centroid Pair Travel Sum free on ExecCode. Browse DSA problems, topic map, and placement guides.