Edge Contribution & Rerooting — Tree Distance Patterns

A comprehensive walkthrough of the edge contribution technique and rerooting DP, from the core insight to 5 LeetCode problems that use it.

Pattern Overview

Trigger: “Sum of distances / costs between pairs in a tree”

All problems share:

• Edge-centric thinking: don’t iterate over pairs, iterate over edges
• Subtree sizes via DFS: one post-order DFS gives sub[v] for every node
• Rerooting (optional): compute answer for root, then derive all others in O(1) per edge

Three main flavors:

Edge Contribution            Rerooting DP               Edge Contribution + Groups
(single aggregate)           (per-node answer)           (grouped pairs)

answer = Σ f(sub[v])         answer[v] = adjust(u→v)    answer = Σ_g left[g]×right[g]

979 Coins                    834 Sum of Distances        Same-Color Distances
2049 Highest Score           2858 Edge Reversals

Quick Navigation: I need to…

★ Insight ───────────────────────────────────── Every problem in this guide is one DFS with a different payload. The universal skeleton — root the tree, post-order DFS to compute a subtree quantity sub[v], then read each edge’s contribution as f(sub[v], n - sub[v]) — never changes. What changes is only what sub[v] measures (count / excess / per-group tally / cost) and how you combine (sum / product / abs). Master the skeleton once and five “different” problems collapse into parameter swaps. ─────────────────────────────────────────────────

Table of Contents

1. Core Insight: Think Per Edge, Not Per Pair
2. The Bridge Analogy
3. Computing Subtree Sizes
4. Rerooting Template
5. Problem 834 — Sum of Distances in Tree
6. Problem 979 — Distribute Coins in Binary Tree
7. Problem 2049 — Count Nodes With the Highest Score
8. Problem 2858 — Minimum Edge Reversals
9. Grouped Edge Contribution — Same-Color Distances
10. Master Comparison Table
11. How to Identify This Pattern

1. Core Insight: Think Per Edge, Not Per Pair

The naive way to compute “sum of distances between all pairs” is O(n²) — BFS from every node. The edge contribution technique does it in O(n).

The key mental flip

Instead of asking “for each pair, what is their distance?”, ask “for each edge, how many pairs cross it?”

Sum of distances = Σ         dist(u, v)
                  (u,v) pairs

                = Σ         (number of edges on path u→v)
                  (u,v)

Swap summation order:

                = Σ         (number of pairs whose path crosses this edge)
                  edges e

Every edge in a tree is a bridge — removing it splits the tree into exactly two parts. A pair crosses an edge if and only if the two nodes are in different parts.

★ Insight ───────────────────────────────────── The whole technique is one algebraic move: swap the order of a double summation. Σ_pairs dist(u,v) is O(n²) to evaluate directly, but dist(u,v) = Σ_edges [edge on path u→v], so swapping the two sums turns it into Σ_edges (pairs crossing e) — and “pairs crossing edge e” is trivial because a tree edge is a bridge: it’s exactly sub[v] × (n − sub[v]). This “count the contribution of each part instead of each whole” reframing is the same trick behind counting inversions per-element, subarray-sum per-boundary, and “sum over all subarrays” problems. When a pairwise sum looks quadratic, ask what each edge / element / boundary contributes across all pairs. ─────────────────────────────────────────────────

2. The Bridge Analogy

         0(A)
        / \
      1(A)  2(B)        Each edge is a toll bridge.
      / \     \         Every pair on opposite sides
    3(B) 4(A)  5(B)     must pay $1 to cross.

Cut edge 0-1:

Left:  {1, 3, 4}    3 nodes
Right: {0, 2, 5}    3 nodes

ALL-pairs crossing:  3 × 3 = 9 pairs
Same-group pairs:
  Group A: 2 left × 1 right = 2
  Group B: 1 left × 2 right = 2

The bridge’s contribution depends on what you’re counting (all pairs, same-group pairs, coin flow, etc.).

3. Computing Subtree Sizes

The foundation of every problem in this family: root the tree, compute subtree sizes bottom-up.

adj = [[] for _ in range(n)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)

sub = [1] * n  # each node counts as 1

def dfs(u, parent):
    for v in adj[u]:
        if v == parent:
            continue
        dfs(v, u)
        sub[u] += sub[v]

dfs(0, -1)

After this DFS:

• sub[v] = number of nodes in v’s subtree (including v)
• Removing edge (parent, v) splits tree into sub[v] and n - sub[v]

This guide uses one running example throughout — the tree from LeetCode 834’s first example, n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]] — so that every sub[] array and every answer below refers to the same picture:

       0
      / \
     1   2         sub = [6, 1, 4, 1, 1, 1]
        /|\
       3 4 5       Removing edge 0-2:
                     Below = {2, 3, 4, 5} → sub[2] = 4
                     Above = {0, 1}       → n - sub[2] = 2

4. Rerooting Template

When you need answer[i] for every node as root:

Pass 1 (bottom-up): compute answer[root] using edge contribution
Pass 2 (top-down):  for each edge (u → child v), derive answer[v] from answer[u]

# Pass 1: compute answer[0]
def dfs1(u, parent):
    for v in adj[u]:
        if v == parent:
            continue
        dfs1(v, u)
        sub[u] += sub[v]
        answer[0] += contribution(v)  # problem-specific

dfs1(0, -1)

# Pass 2: reroot
def dfs2(u, parent):
    for v in adj[u]:
        if v == parent:
            continue
        answer[v] = adjust(answer[u], v)  # problem-specific
        dfs2(v, u)

dfs2(0, -1)

The only thing that changes between problems is contribution() and adjust().

5. Problem 834 — Sum of Distances in Tree

Difficulty: Hard

Return array where answer[i] = sum of distances from node i to all other nodes.

Key Idea

Pass 1: answer[0] = Σ sub[v] for all non-root v. Each node in v’s subtree crosses edge (parent, v) to reach root 0, adding 1 to distance.

       0           answer[0] = sub[1] + sub[2] + sub[3] + sub[4] + sub[5]
      / \                    = 1 + 4 + 1 + 1 + 1 = 8
     1   2
        /|\        Each node contributes 1 per edge on its path to root
       3 4 5       = its depth. So Σ sub[v] = Σ depth(node).

Check the second reading directly: depths are 1, 1, 2, 2, 2 for nodes 1–5, summing to 8. Both routes give the same number because they are the same count grouped differently — by edge on the left, by node on the right.

Pass 2: Moving root from u to child v:

Nodes in sub[v]:     distance decreases by 1 → subtract sub[v]
Nodes NOT in sub[v]: distance increases by 1 → add (n - sub[v])

answer[v] = answer[u] - sub[v] + (n - sub[v])

Solution

class Solution:
    def sumOfDistancesInTree(self, n: int, edges: list[list[int]]) -> list[int]:
        adj = [[] for _ in range(n)]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)

        sub = [1] * n
        answer = [0] * n

        # Pass 1: root at 0
        def dfs1(u, parent):
            for v in adj[u]:
                if v == parent:
                    continue
                dfs1(v, u)
                sub[u] += sub[v]
                answer[0] += sub[v]

        dfs1(0, -1)

        # Pass 2: reroot
        def dfs2(u, parent):
            for v in adj[u]:
                if v == parent:
                    continue
                answer[v] = answer[u] - sub[v] + (n - sub[v])
                dfs2(v, u)

        dfs2(0, -1)

        return answer

Trace

       0
      / \
     1   2
        /|\
       3 4 5

Pass 1: sub = [6, 1, 4, 1, 1, 1], answer[0] = 8

Pass 2, sliding one edge at a time with answer[v] = answer[u] - sub[v] + (n - sub[v]):
  answer[1] = 8 - 1 + 5 = 12   (from node 0)
  answer[2] = 8 - 4 + 2 = 6    (from node 0)
  answer[3] = 6 - 1 + 5 = 10   (from node 2)
  answer[4] = 6 - 1 + 5 = 10   (from node 2)
  answer[5] = 6 - 1 + 5 = 10   (from node 2)

answer = [8, 12, 6, 10, 10, 10]

Notice answer[2] = 6 is the minimum — node 2 is the tree’s centre of gravity, with four of the six nodes one step away. Moving the root from 0 to 2 trades 4 nodes getting closer for only 2 getting farther, which is exactly what - sub[v] + (n - sub[v]) measures. Whenever sub[v] > n/2, the slide is a net improvement; that inequality is the whole reason a centroid minimises total distance.

Complexity: O(n) time, O(n) space

6. Problem 979 — Distribute Coins in Binary Tree

Difficulty: Medium

Binary tree, each node has some coins, total = n. Move coins so each node has exactly 1. Minimize total moves (1 move = 1 coin across 1 edge).

Key Idea

For each edge, compute excess of the child’s subtree:

excess = (coins in subtree) - (nodes in subtree)

excess > 0 → subtree has extra, must export
excess < 0 → subtree needs coins, must import
excess = 0 → self-sufficient

Moves across edge = |excess|. Because the tree has only one edge connecting each subtree to the rest, all surplus/deficit must flow through it.

       0(0)           Node 1: excess = 3-1 = +2 (2 extra)
      / \             Node 2: excess = 0-1 = -1 (needs 1)
    1(3)  2(0)
                      Edge 0-1: |+2| = 2 moves
                      Edge 0-2: |-1| = 1 move
                      Total = 3

Solution

class Solution:
    def distributeCoins(self, root: TreeNode) -> int:
        self.moves = 0

        def dfs(node):
            if not node:
                return 0

            left_excess = dfs(node.left)
            right_excess = dfs(node.right)

            self.moves += abs(left_excess)
            self.moves += abs(right_excess)

            return node.val + left_excess + right_excess - 1

        dfs(root)
        return self.moves

Why return node.val + left_excess + right_excess - 1

excess of subtree = (coins in subtree) - (nodes in subtree)

For a leaf:       val - 1
For internal:     val + left_coins + right_coins - (1 + left_nodes + right_nodes)
                = val - 1 + (left_coins - left_nodes) + (right_coins - right_nodes)
                = val - 1 + left_excess + right_excess

No need to track coins and nodes separately — just propagate excess.

★ Insight ───────────────────────────────────── 979 is edge contribution in disguise. The edge above subtree v must carry |excess[v]| coins in whichever direction fixes the imbalance — and excess[v] = coins − nodes in that subtree is exactly a per-edge quantity. So the total answer is Σ_edges |excess[subtree below edge]|, the same “read one number per edge” move as 834, but the payload is net coin flow and the combine is abs. The abs matters: coins move both up and down across an edge, and either direction costs one move per coin, so magnitude — not sign — is the toll. ─────────────────────────────────────────────────

Complexity: O(n) time, O(h) space (h = tree height)

7. Problem 2049 — Count Nodes With the Highest Score

Difficulty: Medium

Binary tree given as parents[]. Remove node v → tree splits into up to 3 parts. Score = product of part sizes. Count how many nodes achieve the max score.

Key Idea

Removing node v creates:

Part 1: left subtree   → sub[left_child]     (0 if no left child)
Part 2: right subtree  → sub[right_child]    (0 if no right child)
Part 3: everything else → n - sub[v]          (0 if v is root)

Score = product of non-zero parts

One DFS for sub[], then O(1) per node to compute score.

Solution

class Solution:
    def countHighestScoreNodes(self, parents: list[int]) -> int:
        n = len(parents)

        children = [[] for _ in range(n)]
        for i in range(1, n):
            children[parents[i]].append(i)

        sub = [1] * n

        def dfs(u):
            for v in children[u]:
                dfs(v)
                sub[u] += sub[v]

        dfs(0)

        max_score = 0
        count = 0

        for v in range(n):
            score = 1
            for c in children[v]:
                score *= sub[c]
            rest = n - sub[v]
            if rest > 0:
                score *= rest

            if score > max_score:
                max_score = score
                count = 1
            elif score == max_score:
                count += 1

        return count

Trace

       0
      / \
     1   2       sub = [5, 3, 1, 1, 1]
    / \
   3   4

Scores:
  Node 0: sub[1]×sub[2]     = 3×1     = 3   (root, no "rest")
  Node 1: sub[3]×sub[4]×rest = 1×1×2  = 2
  Node 2: rest               = 4       = 4
  Node 3: rest               = 4       = 4
  Node 4: rest               = 4       = 4

Max = 4, count = 3

★ Insight ───────────────────────────────────── 2049 is the odd one out: it multiplies instead of sums. Deleting a node shatters the tree into pieces, and the pieces are exactly the child subtrees plus the “rest” part n - sub[v] — the same bridge decomposition, but now every incident edge of v cuts off one piece at once. The trick is that you never enumerate the pieces by walking edges; sub[] from a single DFS already sizes each child piece, and one subtraction gives the up-part. Same sub[] array, read differently: 834 sums sub × (n−sub) over edges, 2049 multiplies the pieces around a node. ─────────────────────────────────────────────────

Complexity: O(n) time, O(n) space

8. Problem 2858 — Minimum Edge Reversals

Difficulty: Hard

Directed tree. For each node i, find the minimum edge reversals needed so that starting from i you can reach every other node.

Key Idea

Get the direction straight first. The ask is outbound reachability: from the root, you must be able to walk to everyone. So every edge must end up pointing away from the root. An edge already pointing away is free; one pointing back toward the root must be reversed. (Reading this backwards is the single easiest way to get a wrong answer here — see the weight note below.)

Pass 1: Root at 0 and walk down. Each edge you traverse in the direction it already points costs 0; each edge you traverse against its arrow costs 1. Sum those for answer[0].

Pass 2: Reroot. Moving the root from u to its child v flips the orientation of exactly one edge relative to the root — the u–v edge itself. Every other edge keeps its cost:

w = what the u–v edge costs while u is the root

w=0  (points u→v, free for u)  → from v it points inward  → now costs 1
w=1  (points v→u, u must pay)  → from v it points outward → now free

answer[v] = answer[u] - w + (1 - w) = answer[u] - 2w + 1

  w=0: answer[v] = answer[u] + 1   (we now pay for an edge u got free)
  w=1: answer[v] = answer[u] - 1   (we stop paying for one u had to reverse)

Building the adjacency list

for u, v in edges:
    adj[u].append((v, 0))   # walking u→v follows the arrow → nothing to reverse
    adj[v].append((u, 1))   # walking v→u goes against the arrow → must reverse it

The weight means: “if I traverse this direction (parent → child), how much does this edge cost?” Reaching every node from the root means every edge must point away from the root. So an edge you traverse with the arrow costs 0, and one you traverse against it costs 1. Getting these two weights backwards is the classic bug here — it returns (total edges) − (correct answer), a plausible-looking array that is wrong at every index.

Solution

class Solution:
    def minEdgeReversals(self, n: int, edges: list[list[int]]) -> list[int]:
        adj = [[] for _ in range(n)]
        for u, v in edges:
            adj[u].append((v, 0))   # with the arrow: free
            adj[v].append((u, 1))   # against the arrow: one reversal

        answer = [0] * n

        # Pass 1: root at 0
        def dfs1(u, parent):
            for v, w in adj[u]:
                if v == parent:
                    continue
                answer[0] += w
                dfs1(v, u)

        dfs1(0, -1)

        # Pass 2: reroot
        def dfs2(u, parent):
            for v, w in adj[u]:
                if v == parent:
                    continue
                answer[v] = answer[u] - 2 * w + 1
                dfs2(v, u)

        dfs2(0, -1)

        return answer

Trace

Directed: 2→0, 2→1, 1→3

Rooted at 0, the tree shape is 0 — 2 — 1 — 3. Walking DOWN from root 0:

       0
       |  0 -> 2 : the arrow is 2→0, so we walk against it   w = 1
       2
       |  2 -> 1 : the arrow is 2→1, we walk with it         w = 0
       1
       |  1 -> 3 : the arrow is 1→3, we walk with it         w = 0
       3

Pass 1: answer[0] = 1 + 0 + 0 = 1
        (reverse 2→0 into 0→2, and 0 reaches 2, then 1, then 3)

Pass 2 (slide the root down one edge at a time, answer[v] = answer[u] - 2w + 1):
  answer[2] = answer[0] - 2(1) + 1 = 1 - 2 + 1 = 0
  answer[1] = answer[2] - 2(0) + 1 = 0 - 0 + 1 = 1
  answer[3] = answer[1] - 2(0) + 1 = 1 - 0 + 1 = 2

answer = [1, 1, 0, 2]

Sanity-check answer[2] = 0 by hand: from node 2 the arrows already run 2→0, 2→1, and 1→3, so node 2 reaches everyone with zero reversals. And answer[3] = 2 is the worst case — node 3 is a leaf at the far end, so it must reverse 1→3 and 2→1 to climb back out.

★ Insight ───────────────────────────────────── The reroot formula answer[v] = answer[u] - 2w + 1 is a single-edge accounting trick, not magic. When the root hops across one edge, only that one edge changes orientation relative to the root — every other edge keeps its cost. If it cost w for u, flipping makes it cost 1 - w, a delta of (1 - w) - w = 1 - 2w. That is the entire difference between the two answers, which is why rerooting is O(1) per node instead of a fresh O(n) DFS from each root. The directed-weight adjacency ((v,1) forward, (u,0) reverse) is what lets one traversal see both a “traverse this way” cost and its flip for free. ─────────────────────────────────────────────────

Complexity: O(n) time, O(n) space

9. Grouped Edge Contribution — Same-Color Distances

Tree with colored nodes. Find total distance between all same-color pairs.

Key Idea

For each edge (parent → child v), the edge splits the tree. For each color g:

left  = sub[v][g]           (nodes of color g in v's subtree)
right = total[g] - sub[v][g] (nodes of color g elsewhere)

contribution = left × right

Solution

def sumOfGroupDistances(n, edges, groups):
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    total = defaultdict(int)
    for g in groups:
        total[g] += 1

    sub = [None] * n
    answer = 0

    def dfs(u, parent):
        nonlocal answer
        sub[u] = defaultdict(int)
        sub[u][groups[u]] = 1

        for v in adj[u]:
            if v == parent:
                continue
            dfs(v, u)

            for g, cnt in sub[v].items():
                answer += cnt * (total[g] - cnt)

            for g, cnt in sub[v].items():
                sub[u][g] += cnt

    dfs(0, -1)
    return answer

Why no double counting

Each edge is processed exactly once. A pair that crosses 4 edges gets counted once at each of those 4 edges, contributing 4 total — which equals its distance.

Concretely, take this tree (rooted at 0):

          0
         / \
        1   2
        |   |
        3   5

edges: 0-1, 0-2, 1-3, 2-5
path 3 → 1 → 0 → 2 → 5  spans 4 edges

Pair (3, 5), distance = 4:
  Counted at edge 1→3: +1
  Counted at edge 0→1: +1
  Counted at edge 0→2: +1
  Counted at edge 2→5: +1
  Total contribution = 4 = dist(3, 5) ✓

★ Insight ───────────────────────────────────── The thing that looks like a bug — counting one pair at every edge on its path — is precisely what makes the algorithm correct. dist(u,v) is the number of edges on the u→v path, so a same-color pair separated by 4 edges should add 4 to the total, and it does: +1 at each of those 4 edges. You never form the pair explicitly. The one discipline that keeps it exact: count sub[v][g] × (total[g] − sub[v][g]) before merging child v’s tallies into parent u, so each edge sees the split as it was, once. ─────────────────────────────────────────────────

Complexity: O(n × G) time where G = distinct groups, O(n × G) space

10. Master Comparison Table

What stays the same

1. Root the tree
2. Post-order DFS to compute subtree info
3. Use subtree info to compute edge contributions
4. (Optional) Reroot to get per-node answers

What changes

11. How to Identify This Pattern

Trigger: Tree + distances/costs between nodes

See "tree" + any of these?
  └── "sum of distances"         → Edge contribution + rerooting (834)
  └── "move items to balance"    → Edge contribution with excess (979)
  └── "remove node, split tree"  → Subtree sizes, compute per part (2049)
  └── "reverse edges to reach"   → Directed edge cost + rerooting (2858)
  └── "distance between groups"  → Grouped edge contribution

The Universal Steps

1. Root the tree at any node

2. Post-order DFS to compute sub[v]
        │
        └── sub[v] = subtree size / excess / group counts / ...

3. For each edge (parent → child v):
        │
        └── contribution = f(sub[v], n - sub[v])
                           ──────   ──────────
                           v's side  other side

4. (If need per-node answer) Reroot:
        │
        └── answer[v] = adjust(answer[u], sub[v])
            Only the edge between u and v changes,
            everything else stays the same.

Common Pitfalls

Practice Order

Start here
    │
    ▼
  979 (Medium) ─── Edge contribution with "excess" flow (single answer, no reroot)
    │
    ▼
  2049 (Medium) ── Subtree sizes → per-node product
    │
    ▼
  834 (Hard)  ──── Core pattern: edge contribution + rerooting
    │
    ▼
  2858 (Hard)  ─── Directed edges + rerooting with cost
    │
    ▼
  Grouped      ─── Per-group edge contribution with merge
  Distances

Toolbox at a Glance

Tree + "distance / cost / balance across pairs"?
    │
    ├── One aggregate number over ALL pairs?
    │       ├── counting pairs      → Σ sub[v]×(n-sub[v])         (834-core, Grouped per g)
    │       ├── balancing items     → Σ |excess[v]|               (979)
    │       └── same-color / groups → Σ_g L[g]×R[g] per edge      (Grouped)
    │
    ├── Answer for EVERY node?
    │       ├── distances           → reroot ans[v]=ans[u]-sub[v]+(n-sub[v])   (834)
    │       └── directed reversals  → reroot ans[v]=ans[u]-2w+1                (2858)
    │
    └── Remove a node, combine the pieces?
            └── product of parts    → Π(sub[child]) × (n-sub[v])  (2049)

THREE MOVES BEHIND EVERY EDGE-CONTRIBUTION PROBLEM

1. FLIP THE SUM      Σ over pairs  →  Σ over edges. A tree edge is a bridge, so
                     "pairs crossing edge e" = sub[v] × (n - sub[v]). No pair loop.

2. ONE POST-ORDER    A single DFS fills sub[v] (size / excess / cost / per-group
                     tally). Every per-edge formula reads sub[v] and n - sub[v].

3. REROOT FOR FREE   Need every node's answer? Hopping the root across one edge
                     changes only that edge's term, so ans[v] = adjust(ans[u]) is
                     O(1). Skip it when one aggregate number is all you need.

When This Fails

Edge contribution rests on one fact: removing an edge from a tree splits it into exactly two components. Everything follows from that, and everything breaks without it:

• The graph is not a tree. With a cycle, removing an edge disconnects nothing, so size × (n − size) counts nothing meaningful.
• The per-pair quantity is not additive along the path. The technique decomposes a sum over pairs into a sum over edges, which requires each pair’s value to be the sum of its edges’ contributions. Distance qualifies. “Maximum edge weight on the path” does not — use LCA or a max-aggregating structure.
• You need one specific pair, not an aggregate. Computing all-pairs machinery to answer dist(u, v) once is backwards; that is a plain LCA query.
• The parent-to-child conversion is not O(1). Then rerooting is no cheaper than running the DFS from every root.

Self-Test

Answer these from memory, out loud or on paper, before looking. Recognition is not recall: rereading an explanation feels like knowing, and it is not. A question you cannot answer cold names the exact section to revisit — you do not need to reread the guide.

1. Why does edge (u, v) appear in exactly size[v] × (n − size[v]) paths?

2. What is the one-line formula for the sum of distances over all pairs?

3. What is the mental flip that defines this pattern?

4. In LC 834, why is the child’s answer ans[parent] − size[c] + (n − size[c])?

5. Why must a grouped contribution be counted before merging child data into the parent?

6. What signals this pattern rather than plain tree DP?

7. Distribute Coins (LC 979): what is the per-edge contribution?

See Also

• Tree Patterns — the traversal backbone (subtree sizes, post-order DFS) these formulas ride on, plus the farthest-node flavour of rerooting not covered here.
• Contribution Counting — the same mental flip on arrays: count each element’s contribution instead of enumerating subarrays.
• LCA — when you need the distance between two specific nodes repeatedly rather than an aggregate over all pairs.
• Dynamic Programming §10 — the general tree-DP framing; rerooting is tree DP with a second, downward pass.
• Pattern Decision Map — the router: which technique does a cold problem call for?
• Pattern Mastery Program — the spaced-repetition schedule, mastery checklist, and drill formats that turn reading into recall.

Pattern mastered — same DFS backbone, different per-edge formulas and optional rerooting.