Rerooting Technique (Tree DP for All Roots)

Quick Revisit

• USE WHEN: tree DP answer needed for every node as root (sum of distances, max depth from each node)
• INVARIANT: ans[v] = ans[u] adjusted by one edge — subtree nodes get closer, rest get farther
• TIME: O(n) two DFS passes | SPACE: O(n)
• CLASSIC BUG: non-invertible merge function — if combine(a,b) can't undo b, need the second-max trick
• PRACTICE: 08-ladder-mixed

Compute a tree DP answer for every node as root in $O(n)$ total, by shifting contributions when the root moves along an edge.

This file is the deeper second pass on the technique. The first pass — plain subtree DP, rooted at one node — lives in DP on Trees (Ch 4). Read that first if you have not.

Difficulty: [Intermediate]  ·  CF rating: 1600–2000 Prerequisites: DP on Trees, DFS and Tree DFS

---

The Problem That Starts It All

You have a tree on $n$ nodes. For each node $v$, compute the sum of distances from $v$ to every other node. Call this $\text{ans}[v]$.

Your first instinct: root the tree at $v$, run a DFS, accumulate depths. That gives $\text{ans}[v]$ in $O(n)$. But you need it for all $n$ nodes, so the naive plan is $n$ separate DFS calls -- $O(n^2)$.

For $n\le 2\times {10}^5$, that's dead on arrival.

The key insight: when you "move the root" from node $u$ to an adjacent node $v$, most of the answer stays the same. The nodes inside $v$'s subtree each get 1 closer, and the nodes outside get 1 farther. If $\text{sz}[v]$ is the subtree size of $v$ (when rooted at $u$), then:

$$\text{ans}[v]=\text{ans}[u]-\text{sz}[v]+(n-\text{sz}[v])$$

That simplifies to:

$$\text{ans}[v]=\text{ans}[u]+n-2\cdot \text{sz}[v]$$

One formula, one edge traversal, $O(1)$ per move. Compute $\text{ans}[0]$ once with a single DFS, then propagate to all neighbors in a second DFS. Total: $O(n)$.

This is rerooting.

The General Framework

Rerooting applies whenever your tree DP has this shape:

1. Root at node 0.
2. DFS 1 (bottom-up): compute $\text{dp\_down}[v]$ — the answer using only $v$'s subtree.
3. DFS 2 (top-down): compute $\text{dp\_up}[v]$ — the contribution from everything outside $v$'s subtree.
4. Combine: $\text{ans}[v]=\text{combine}(\text{dp\_down}[v],\text{dp\_up}[v])$.

Whether it actually works depends on a single property of the combine operation: can you remove one child's contribution from the parent's aggregate? Three buckets:

Combine type	Examples	How to remove a child	Cost per node
Invertible	sum, XOR, product (no zero), count	algebraic inverse: subtract / XOR back / divide	$O(1)$
Non-invertible but decomposable	max, min, gcd	prefix/suffix arrays over children, or best1/best2 trick	$O(\mathrm{deg})$ preprocessing, $O(1)$ exclusion
Not rerootable as-is	median, distinct count, pairwise interactions	rerooting fails — enlarge the state, or switch to centroid decomposition / HLD / small-to-large	—

The middle row is the most common contest case. Plain max looks like it "can't be undone", but you can always compute "max of all children except $c_i$" via prefix/suffix arrays in $O(\mathrm{deg})$ — or, for max specifically, keep the best and second-best child values plus the index that achieved the best. When you need to exclude the best child, fall back to second-best. The best1/best2 trick is just the max-specific specialization of the prefix/suffix idea.

The bottom row is real: if removing a child genuinely changes the structure of what's left (median quantile, distinct-value count, joint contributions across pairs of children), rerooting cannot factor through. Reach for centroid decomposition or small-to-large instead.

---

Seeing It in Action

Consider this tree with 6 nodes (0-indexed), unweighted edges:

            0
           / \
          1   2
         /   / \
        3   4   5

Step 1: Compute subtree sizes (rooted at 0).

    sz[3] = 1    sz[4] = 1    sz[5] = 1
    sz[1] = 2    sz[2] = 3
    sz[0] = 6

Step 2: Compute ans[0] via DFS -- sum of depths.

    Node:  0  1  2  3  4  5
    Depth: 0  1  1  2  2  2
    ans[0] = 0+1+1+2+2+2 = 8

Step 3: Reroot along each edge.

Move root from 0 to 1: $\text{ans}[1]=\text{ans}[0]+n-2\cdot \text{sz}[1]=8+6-4=10$.

Check by hand -- distances from node 1: to 0 is 1, to 2 is 2, to 3 is 1, to 4 is 3, to 5 is 3. Sum = 10. Correct.

Move root from 0 to 2: $\text{ans}[2]=8+6-2\cdot 3=8$. Distances from 2: 1+2+1+3+1 = 8. Matches.

Move root from 1 to 3: $\text{ans}[3]=10+6-2\cdot 1=14$. Distances from 3: 2+1+3+4+4 = 14. Correct.

Move root from 2 to 4: $\text{ans}[4]=8+6-2=12$. From 4: 2+3+1+4+2 = 12. Correct.

Move root from 2 to 5: $\text{ans}[5]=8+6-2=12$. From 5: 2+3+1+4+2 = 12. Correct.

Visualizing the Root Move

When the root shifts from $u$ to $v$ along edge $(u,v)$:

    BEFORE (rooted at u):              AFTER (rooted at v):

         u  <-- root                        v  <-- root
         |                                  |
         v                                  u
        / \                                / \
      (subtree of v)                  (rest of tree)
      sz[v] nodes get                 (n - sz[v]) nodes
      1 closer                        get 1 closer

    Net change = -(sz[v]) + (n - sz[v]) = n - 2*sz[v]

A Weighted Example (Maximum Distance)

Now a different problem: for each node, find the maximum distance to any other node (Tree Distances I). Same tree, but with edge weights:

        0
       / \
      3   7
     /     \
    1       2
   /       / \
  2       1   4
 /       /     \
3       4       5

  Edge weights:  0-1: 3,  0-2: 7,  1-3: 2,  2-4: 1,  2-5: 4

Here "sum" won't work -- we need max. Bottom-up DFS gives the farthest node in each subtree. But when rerooting, removing the max-child needs the second-max trick.

For node 2, the farthest node downward is 5 at distance 4. The farthest upward goes through 0 then to 3 (distance $7+3+2=12$). So $\text{ans}[2]=12$.

For node 0, farthest down-left is 3 at distance 5, farthest down-right is 5 at distance 11. So $\text{ans}[0]=11$.

The second-max trick ensures that when we exclude the child contributing the maximum, we still know the runner-up.

---

C++ STL Building Blocks

Rerooting implementations lean on basic structures:

Tool	Usage
vector<vector<int>>	Adjacency list (unweighted)
vector<vector<pair<int,int>>>	Adjacency list (weighted: {neighbor, weight})
vector<long long>	DP arrays (dp_down, dp_up, ans)
vector<int>	Subtree sizes
pair<long long, long long>	Best and second-best values for the second-max trick

Nothing exotic. The technique is about the algorithm, not the data structures.

---

Implementation: Sum of Distances (CSES Tree Distances II)

This is the cleanest rerooting problem. Unweighted tree, compute sum of distances from each node.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> adj(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> sz(n, 1);
    vector<long long> ans(n, 0);

    // DFS 1: compute subtree sizes and ans[0] (sum of depths from root 0)
    vector<int> order, par(n, -1);
    vector<bool> visited(n, false);
    order.reserve(n);
    order.push_back(0);
    visited[0] = true;
    for (int i = 0; i < n; i++) {
        int u = order[i];
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                par[v] = u;
                order.push_back(v);
            }
        }
    }

    // Bottom-up: reverse BFS order
    for (int i = n - 1; i >= 1; i--) {
        int v = order[i];
        sz[par[v]] += sz[v];
        ans[0] += sz[v];  // each node in subtree(v) contributes 1 to depth
        // Equivalently: ans[0] = sum of depths from node 0
        // Adding sz[v] accounts for the edge par[v]->v adding 1
        // to the depth of all sz[v] nodes in v's subtree.
    }

    // DFS 2: reroot -- propagate ans from parent to child
    for (int i = 1; i < n; i++) {
        int v = order[i];
        ans[v] = ans[par[v]] + n - 2 * sz[v];
    }

    for (int i = 0; i < n; i++) {
        cout << ans[i] << " \n"[i == n - 1];
    }
}

Why it works:

• The BFS-order trick replaces recursion. Process nodes in reverse BFS order for bottom-up, forward BFS order for top-down. No stack overflow risk.
• ans[0] accumulates as we process edges bottom-up: each edge $(par[v],v)$ is crossed by all $\text{sz}[v]$ nodes in $v$'s subtree.
• The rerooting formula $\text{ans}[v]=\text{ans}[par[v]]+n-2\cdot \text{sz}[v]$ follows because $\text{sz}[v]$ nodes get closer and $n-\text{sz}[v]$ nodes get farther.

---

Invertible vs Non-Invertible Merge Functions

Invertible (e.g., addition, XOR): To compute dp_up[v] (contribution from parent's side), subtract child v's contribution from parent's total: dp_up[v] = combine(dp_down[parent] - dp_down[v], dp_up[parent])

Non-invertible (e.g., max, min, gcd): You CAN'T subtract. Use the prefix-suffix trick:

For parent p with children c1, c2, ..., ck:

• prefix[i] = merge of dp_down[c1], ..., dp_down[ci]
• suffix[i] = merge of dp_down[ci], ..., dp_down[ck]
• Contribution excluding ci = merge(prefix[i-1], suffix[i+1], dp_up[p])

vector<T> pre(k), suf(k);
pre[0] = dp[children[0]]; 
for (int i = 1; i < k; i++) pre[i] = merge(pre[i-1], dp[children[i]]);
suf[k-1] = dp[children[k-1]];
for (int i = k-2; i >= 0; i--) suf[i] = merge(suf[i+1], dp[children[i]]);

dp_up[root] must be the identity element (0 for sum, -INF for max, INF for min), NOT uninitialized. Garbage here propagates to the entire tree.

---

Implementation: General Rerooting with Second-Max Trick

For problems where the combination is max (like Tree Distances I), we need to track which child gave the best value, and keep a backup.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<pair<int,int>>> adj(n);  // {neighbor, weight}
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    // For unweighted version, set all weights to 1.

    vector<int> order, par(n, -1);
    vector<long long> par_w(n, 0);  // weight of edge to parent
    vector<bool> visited(n, false);
    order.reserve(n);
    order.push_back(0);
    visited[0] = true;
    for (int i = 0; i < n; i++) {
        int u = order[i];
        for (auto [v, w] : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                par[v] = u;
                par_w[v] = w;
                order.push_back(v);
            }
        }
    }

    // dp_down[v] = max distance to any node in subtree of v
    vector<long long> dp_down(n, 0);

    // For each node, store best and second-best (down) values
    // best1[v] = max over children c of (dp_down[c] + w(v,c))
    // best2[v] = second max
    // best_child[v] = which child achieved best1
    vector<long long> best1(n, 0), best2(n, 0);
    vector<int> best_child(n, -1);

    // Bottom-up
    for (int i = n - 1; i >= 1; i--) {
        int v = order[i];
        int p = par[v];
        long long val = dp_down[v] + par_w[v];
        if (val >= best1[p]) {
            best2[p] = best1[p];
            best1[p] = val;
            best_child[p] = v;
        } else if (val > best2[p]) {
            best2[p] = val;
        }
        dp_down[p] = best1[p];
    }

    // dp_up[v] = max distance going "up" through parent and beyond
    vector<long long> dp_up(n, 0);

    // Top-down
    for (int i = 1; i < n; i++) {
        int v = order[i];
        int p = par[v];
        // What's the best the parent can offer, excluding v's subtree?
        long long from_parent;
        if (best_child[p] == v) {
            from_parent = best2[p];  // v was the best child, use second-best
        } else {
            from_parent = best1[p];  // some other child was best
        }
        dp_up[v] = max(from_parent, dp_up[p]) + par_w[v];
    }

    // Answer for each node
    for (int i = 0; i < n; i++) {
        // best1[i] = farthest going down, dp_up[i] = farthest going up
        cout << max(best1[i], dp_up[i]) << " \n"[i == n - 1];
    }
}

The second-max logic, unpacked:

When computing dp_up[v], we need the best distance the parent $p$ can reach without going through $v$. The parent's options are:

1. Go through a different child of $p$ -- that's best1[p] if $v$ wasn't the best child, or best2[p] if $v$ was.
2. Go upward through $p$'s own parent -- that's dp_up[p].

Take the max, add the edge weight $w(p,v)$, and you have dp_up[v].

This pattern handles any "max over children" rerooting. The best1/best2 bookkeeping is the entire trick.

---

Complexity

Operation	Time	Space
Build adjacency list	$O(n)$	$O(n)$
DFS 1 (bottom-up)	$O(n)$	$O(n)$
DFS 2 (top-down)	$O(n)$	$O(n)$
Total	$O(n)$	$O(n)$

Both passes visit each node exactly once. No sorting, no logarithmic factors. This is as good as it gets for answering $n$ root-dependent queries on a tree.

---

Problem Patterns and Tricks

Pattern 1: Sum of Distances (The Classic)

Compute $\sum _u\text{dist}(v,u)$ for each $v$. Rerooting formula is additive, no second-max needed. The flagship example (CSES Tree Distances II).

Weighted variant: store $\text{wt\_sum}[v]$ = sum of weighted distances in subtree. Rerooting adjusts by edge weight times node counts on each side.

Pattern 2: Maximum Distance (Tree Distances I)

Find the farthest node from each $v$. Needs the second-max trick. The answer for each node is always one endpoint of the tree's diameter -- but rerooting gives you a clean $O(n)$ without finding the diameter explicitly.

Pattern 3: Counting Nodes at Distance $\le k$

Root the tree. Bottom-up: for each node, merge sorted distance lists from children (or use centroid decomposition if $k$ varies per query). Rerooting can help when $k$ is fixed and you want the count for all nodes.

This is a case where rerooting works but is tricky -- the "DP state" is a histogram, and you need prefix sums to efficiently reroot. Often centroid decomposition is cleaner.

Pattern 4: Subtree Aggregates Becoming Global

Any problem of the form "compute $f(\text{subtree}(v))$ for each root $v$" where $f$ decomposes over children. Examples:

• Sum of subtree XORs
• Product of subtree sizes (with modular inverse for "removing" a child)
• Number of distinct values in subtree (hard -- rerooting rarely helps here)

Pattern 5: Diameter-Related Queries

"For each node, what is the diameter of the tree if this node is removed?" or "What is the diameter passing through this node?" These are solvable by maintaining best/second-best/third-best longest paths through children, then rerooting.

Pattern 6: When Rerooting Fails

Rerooting fundamentally requires decomposability: the answer at a node must split cleanly into per-child contributions that can be individually removed.

It fails for:

• Median/quantile queries -- no clean way to remove a child's contribution.
• Distinct count -- removing a subtree doesn't easily update the count of distinct values.
• Heavy interaction between subtrees -- if the DP at a node depends on pairs of children jointly, rerooting doesn't factorize.

Alternatives when rerooting fails: centroid decomposition, heavy-light decomposition, small-to-large merging, or Euler tour + offline queries.

---

What the code won't teach you

Why rerooting works at all. The tree DP value at any root $r$ depends on the values for adjacent roots in a structured way. Rerooting exploits that structure to pass information bidirectionally with two DFS passes instead of $n$ independent DFS computations.

Identifying when to reach for it. The signal: the problem asks for some quantity "for each possible root" or "for each node, what is X if this node is the root." Common examples: sum of distances from each node, diameter from each node, subtree size relative to each root.

The contribution view. Instead of tracking the DP value for each root, track the contribution of each vertex to every other vertex's answer. For sum-of-distances, the contribution of $v$ to $u$'s answer is just the distance from $u$ to $v$ — which changes by one when you move the root along an edge. That single observation collapses into the rerooting formula.

---

Gotchas and Debugging

1. Forgetting dp_up entirely. You computed the bottom-up DP and thought you were done. But dp_down[v] only knows about $v$'s subtree -- the rest of the tree is invisible. The top-down pass is not optional.

2. Wrong direction in DFS 2. The top-down pass processes nodes from root toward leaves (forward BFS order). If you accidentally process in reverse, parents won't have their dp_up computed yet when children need them.

3. Off-by-one in the rerooting formula. For sum-of-distances: $\text{ans}[v]=\text{ans}[par]+n-2\cdot \text{sz}[v]$. A common mistake is writing $n-2\cdot \text{sz}[v]+1$ or forgetting the factor of 2. Derive it from scratch if unsure: $\text{sz}[v]$ nodes get 1 closer ($-\text{sz}[v]$) and $n-\text{sz}[v]$ nodes get 1 farther ($+n-\text{sz}[v]$). Total change: $n-2\text{sz}[v]$.

4. Not initializing best_child to $-1$. If best_child[p] isn't set (leaf node $p$ with no children processed yet), comparing against an uninitialized value causes silent wrong answers. Initialize to $-1$ and handle the "no child" case.

5. Edge case: $n=1$. Single node, all answers are 0. Make sure your BFS loop and DFS 2 loop handle empty adjacency lists gracefully.

6. Edge case: $n=2$. Two nodes connected by one edge. sz of the non-root is 1. $\text{ans}[\text{root}]=1$, $\text{ans}[\text{child}]=1$ (unweighted). Simple but worth checking.

7. Integer overflow. Sum of distances can reach $O(n^2)$ for a path graph (approximately $n^2/2$). With $n=2\times {10}^5$, that's $\sim 2\times {10}^{10}$ -- use long long. For weighted trees, the bound is $O(n\cdot W_{max})$ per edge summed over path lengths, which can be even larger.

8. Weighted vs. unweighted confusion. The clean formula $\text{ans}[v]=\text{ans}[par]+n-2\cdot \text{sz}[v]$ is for unweighted trees. For weighted trees, you need to track the sum of weighted distances and adjust by the edge weight:

$$\text{ans}[v]=\text{ans}[par[v]]+w(par[v],v)\cdot (n-2\cdot \text{sz}[v])$$

Missing the weight multiplier is a frequent bug.

9. Second-max tie-breaking. When two children have equal best values, best2 should still be set. The condition should be >= for updating best1 (or track indices carefully). If you use strict >, you'll miss the case where two children tie for the maximum.

Mental Traps

Trap: "I'll just root the tree at node 1 and it'll be fine." For some problems this is correct -- when the answer doesn't depend on the root. But for problems asking "for each node, compute X if that node is the root," you must reroot. The trap: not reading the problem statement carefully enough to notice that the root matters.

Trap: "Rerooting is complicated -- I'll just do O(n²)." For $n=5000$, $O(n^2)$ is 25 million operations -- fine. For $n=2\times {10}^5$, $O(n^2)$ is $4\times {10}^{10}$ -- not fine. Check the constraints before deciding.

Trap: "The second DFS is just the first DFS in reverse." It's not. The first DFS computes dp_down[v] by combining children's values. The second DFS computes dp_up[c] by combining the parent's dp_up value with the "everything except c" part of the parent's dp_down. These are structurally different computations.

Trap: "If combination is max/min, I can't do rerooting." You can — use prefix-suffix products. For each parent, precompute prefix and suffix over its children. "Max of all except one child" is always computable in $O(1)$ with $O(\mathrm{deg})$ preprocessing.

Never guess the rerooting recurrence

Solving "Sum of Distances in Tree" (LeetCode 834), a tempting one-liner is:

up[v] = up[parent] + down[parent] - down[v] - sz[v] + (n - sz[v])

On the sample tree 0-1-2, answers come out off by exactly 2 for every non-root node. The issue: down[parent] includes the edge parent->v counted once for each node in v's subtree -- that's sz[v] edges, which down[v] alone doesn't capture. The fix requires drawing the two contributions on paper:

• Nodes outside v's subtree, previously at distance d from parent, are now at distance d + 1 from v -> contributes up[parent] + (n - sz[v]).
• Nodes in parent's subtree but not in v's subtree -> contributes down[parent] - down[v] - sz[v].

Never guess the rerooting recurrence -- derive it by drawing which distances increase by 1 and which decrease by 1 when the root shifts.

Debug Drills

Drill 1: Rerooting for sum of distances -- but all non-root answers are wrong.

void dfs_down(int v, int p) {
    sz[v] = 1;
    down[v] = 0;
    for (int u : adj[v]) {
        if (u == p) continue;
        dfs_down(u, v);
        sz[v] += sz[u];
        down[v] += down[u] + sz[u];
    }
}

void dfs_up(int v, int p) {
    for (int u : adj[v]) {
        if (u == p) continue;
        up[u] = up[v] + down[v] - down[u] + n - sz[u];  // <-- look here
        dfs_up(u, v);
    }
}

What's wrong?

When removing child u's contribution from down[v], you need to subtract down[u] + sz[u] (the subtree distances plus the edge from v to u counted once per node in u's subtree). The formula should be: up[u] = up[v] + (down[v] - down[u] - sz[u]) + (n - sz[u]); The missing - sz[u] causes all non-root answers to be inflated.

Drill 2: Rerooting for max-depth -- but some nodes report depth 0.

void dfs_down(int v, int p) {
    best1[v] = best2[v] = 0;  // top-2 max depths among children
    for (int u : adj[v]) {
        if (u == p) continue;
        dfs_down(u, v);
        int d = best1[u] + 1;
        if (d >= best1[v]) {
            best2[v] = best1[v];
            best1[v] = d;
        } else if (d > best2[v]) {
            best2[v] = d;
        }
    }
}

void dfs_up(int v, int p) {
    for (int u : adj[v]) {
        if (u == p) continue;
        int from_parent;
        if (best1[u] + 1 == best1[v])
            from_parent = best2[v] + 1;
        else
            from_parent = best1[v] + 1;
        up[u] = from_parent;  // <-- look here
        dfs_up(u, v);
    }
}

What's wrong?

up[u] should be the max of from_parent and up[v] + 1 -- the path can go through v and then upward through v's parent, not just downward into v's other children. The fix is: up[u] = max(from_parent, up[v] + 1); Without considering up[v], nodes deep in the tree never "see" paths that go through their ancestors toward the rest of the tree.

Drill 3: Rerooting for subtree XOR -- but the second DFS crashes or gives garbage.

void dfs_down(int v, int p) {
    down[v] = val[v];
    for (int u : adj[v]) {
        if (u == p) continue;
        dfs_down(u, v);
        down[v] ^= down[u];
    }
}

void dfs_up(int v, int p) {
    for (int u : adj[v]) {
        if (u == p) continue;
        // "Remove" u's contribution from v, then give remainder to u
        int remainder = down[v] ^ down[u];  // v's value without u's subtree
        up[u] = remainder;
        dfs_up(u, v);
    }
}
// Final answer: ans[v] = down[v] ^ up[v]

What's wrong?

The up[u] computation forgets to include up[v] -- the contribution from everything above v. Since XOR is its own inverse, the fix is: up[u] = remainder ^ up[v]; which equals down[v] ^ down[u] ^ up[v]. Without up[v], nodes at depth >= 2 lose all information about the tree above their grandparent, giving garbage answers.

---

Practice Problems

Problem	Source	Key Idea	Link
Tree Distances I	CSES 1132	Max distance, second-max trick	cses.fi/problemset/task/1132
Tree Distances II	CSES 1133	Sum of distances, classic rerooting	cses.fi/problemset/task/1133
Tree Painting	CF 1187E	Rerooting with subtree-size scoring	codeforces.com/contest/1187/problem/E
Distance in Tree	CF 161D	Count pairs at distance $k$ (DP on tree, centroid alt.)	codeforces.com/contest/161/problem/D
Choosing Capital	CF 219D	Rerooting with edge direction counting	codeforces.com/contest/219/problem/D
Accumulation Degree	POJ 3585	Max flow from each root (classic rerooting)	poj.org/problem?id=3585
SumOfDistancesInTree	LeetCode 834	Sum of distances, same as CSES 1133	leetcode.com/problems/sum-of-distances-in-tree

Suggested progression:

1. CSES Tree Distances II -- get the additive rerooting formula down.
2. CSES Tree Distances I -- learn the second-max trick.
3. CF 219D -- rerooting where you count "correct" vs "reversed" edges.
4. CF 1187E -- rerooting with a non-obvious scoring function.
5. POJ 3585 -- rerooting on a flow-like DP, good for generalization practice.

Rating progression:

CF Rating	What to Master
1200	Solid subtree DP: compute depth sums, subtree sizes, and max-depth with a single rooted DFS. Understand parent arrays and child iteration.
1500	Implement the two-pass pattern: first DFS computes down[v], second DFS propagates up[v] from parent. Solve "sum of distances to all nodes" (LC 834).
1800	Handle non-invertible combine functions using prefix/suffix arrays of children's DP values. Reroot DP where the transition involves max (not sum) -- you need the top-2 values trick.
2100	Combine rerooting with additional structures (rerooting + centroid decomposition, rerooting + HLD for queries). Handle edge-weighted rerooting where contribution formulas are asymmetric.

---

Further Reading

• DP on Trees -- prerequisite; covers basic subtree DP without rerooting.
• DFS and Tree DFS -- DFS ordering, parent arrays, subtree sizes.
• Centroid Decomposition -- the alternative when rerooting doesn't apply.
• Codeforces Blog: "Rerooting technique" by Elegia -- detailed theoretical treatment with more examples.
• CP-Algorithms: "Finding all tree distances" -- covers the sum-of-distances variant.