Chapter 8.3: Tree DP & Rerooting

📝 Before You Continue: This chapter requires Chapter 5.3 (trees, tree traversals, DSU), Chapter 6.1–6.2 (DP fundamentals), and Chapter 8.2 (DAG DP). You must understand DFS post-order traversal before reading tree DP.

Tree DP runs dynamic programming on a rooted tree, using each subtree as a subproblem. It's one of the most important techniques at USACO Gold and appears in nearly every Gold/Platinum tree problem.

Rerooting (also called "re-rooting technique") extends tree DP to handle queries for every possible root in O(N) time — without running a full DFS for each root.

Learning objectives:

• Write tree DP templates for subtree-based problems
• Compute tree diameter, longest paths, subtree sums
• Apply the rerooting technique to answer "what if this were the root?" in O(N)
• Recognize tree DP patterns in USACO Gold problems

8.3.0 Why Trees Are Special for DP

A tree is a DAG (rooted tree with edges pointing away from root). This means:

• No cycles: DP transitions are always to children (no back-references)
• Natural subproblems: The subtree rooted at v is a complete, independent subproblem
• Clean recurrence: dp[v] depends only on dp[children of v]

The key pattern: Post-order DFS — process children before parent.

Tree:         DFS post-order:     DP order:
    1             4, 5, 2         compute dp[4], dp[5] first,
   / \            6, 3            then use them for dp[2]
  2   3           2, 3
 / \   \          1               dp[v] is computed after all children
4   5   6                         → parent can use children's dp values

8.3.1 Tree DP Template

The canonical tree DP template: DFS with parent tracking to avoid revisiting.

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

const int MAXN = 100001;
vector<int> adj[MAXN];
int dp[MAXN];  // define dp array based on problem

void dfs(int u, int parent) {
    // Initialize dp[u] (base case: leaf node)
    dp[u] = /* initial value */ 0;

    for (int v : adj[u]) {
        if (v == parent) continue;  // don't go back up the tree

        dfs(v, u);  // ← recurse on child first (post-order)

        // Now dp[v] is computed → use it to update dp[u]
        dp[u] = /* combine dp[u] and dp[v] */;
    }
}

int main() {
    int n;
    cin >> 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);
    }

    dfs(0, -1);  // root at vertex 0, no parent

    cout << /* answer using dp values */ "\n";
    return 0;
}

8.3.2 Classic Tree DP Problems

Problem 1: Subtree Size

sz[v] = number of nodes in the subtree rooted at v.

int sz[MAXN];

void dfs(int u, int par) {
    sz[u] = 1;  // count u itself
    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);
        sz[u] += sz[v];  // add subtree size of child
    }
}

Problem 2: Maximum Depth of Subtree

depth[v] = maximum distance from v to any leaf in its subtree.

int depth[MAXN];

void dfs(int u, int par) {
    depth[u] = 0;
    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);
        depth[u] = max(depth[u], depth[v] + 1);  // extend path through v
    }
}

Problem 3: Tree Diameter

The diameter of a tree is the longest path between any two nodes. Key insight: the longest path either passes through the root, or is entirely in one subtree.

Method 1: Two DFS (simplest)

int farthest_node, max_dist;

void dfs_farthest(int u, int par, int dist) {
    if (dist > max_dist) {
        max_dist = dist;
        farthest_node = u;
    }
    for (int v : adj[u]) {
        if (v != par)
            dfs_farthest(v, u, dist + 1);
    }
}

int treeDiameter(int n) {
    // Step 1: find one endpoint of diameter (farthest from node 0)
    max_dist = 0;
    dfs_farthest(0, -1, 0);
    int endpoint1 = farthest_node;

    // Step 2: find the other endpoint (farthest from endpoint1)
    max_dist = 0;
    dfs_farthest(endpoint1, -1, 0);

    return max_dist;  // diameter length
}

Method 2: DP (more generalizable)

int diameter = 0;
int max_down[MAXN];  // max_down[v] = longest path going DOWN from v

void dfs(int u, int par) {
    max_down[u] = 0;
    vector<int> child_depths;

    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);
        child_depths.push_back(max_down[v] + 1);
    }

    // Diameter through u = sum of two longest paths going down
    sort(child_depths.rbegin(), child_depths.rend());
    if (child_depths.size() >= 1) max_down[u] = child_depths[0];
    if (child_depths.size() >= 2) {
        diameter = max(diameter, child_depths[0] + child_depths[1]);
    }
    // Also consider paths that go up (handled by rerooting later)
    diameter = max(diameter, max_down[u]);
}

Problem 4: Maximum Independent Set on Tree

Choose maximum number of nodes such that no two chosen nodes are adjacent.

int dp[MAXN][2];
// dp[v][0] = max nodes in subtree of v when v is NOT chosen
// dp[v][1] = max nodes in subtree of v when v IS chosen

void dfs(int u, int par) {
    dp[u][0] = 0;
    dp[u][1] = 1;  // v itself is chosen

    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);

        dp[u][0] += max(dp[v][0], dp[v][1]);  // v not chosen: child can be either
        dp[u][1] += dp[v][0];                  // v chosen: child MUST be not chosen
    }
}

// Answer = max(dp[root][0], dp[root][1])

8.3.3 The Rerooting Technique

Problem: For each vertex v in a tree, compute some value if v were the root. Naively, this requires N separate DFS runs → O(N²). Rerooting does it in two DFS passes: O(N).

Core idea:

• DFS 1 (down pass): Compute down[v] = answer for subtree of v (treating original root as root)
• DFS 2 (up pass): Compute up[v] = answer for the "rest of the tree" above v (subtree not including v's subtree when rooted originally)
• Final answer for v as root: Combine down[v] and up[v]

Rerooting Template: Sum of Distances

Problem: For each vertex v, find the sum of distances from v to all other vertices. Output these N values.

This is a classic Gold problem. The key recurrence:

If we know dist_sum[root] (sum of distances from root to all vertices), then for a child c of root:

dist_sum[c] = dist_sum[root] - sz[c] + (n - sz[c])
            = dist_sum[root] + (n - 2 * sz[c])

Reasoning: Moving root→c, all sz[c] vertices in c's subtree get 1 closer, and (n - sz[c]) vertices outside get 1 farther.

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

const int MAXN = 100001;
vector<int> adj[MAXN];
long long sz[MAXN];      // subtree size
long long down[MAXN];    // sum of distances from v to all nodes in its subtree
long long ans[MAXN];     // final answer: sum of distances from v to ALL nodes

int n;

// DFS 1: compute sz[] and down[] (sum of distances going down)
void dfs1(int u, int par) {
    sz[u] = 1;
    down[u] = 0;
    for (int v : adj[u]) {
        if (v == par) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        down[u] += down[v] + sz[v];  // all nodes in v's subtree are 1 step farther
    }
}

// DFS 2: propagate answers downward (rerooting)
void dfs2(int u, int par) {
    for (int v : adj[u]) {
        if (v == par) continue;
        // ans[v] = ans[u] - sz[v] + (n - sz[v])
        //        = ans[u] + (n - 2 * sz[v])
        ans[v] = ans[u] + (n - 2 * sz[v]);
        dfs2(v, u);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> 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);
    }

    dfs1(0, -1);
    ans[0] = down[0];  // sum of distances from root 0 to all other nodes
    dfs2(0, -1);

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

    return 0;
}

Complexity: O(N) — two DFS passes, each O(N).

Mental Model for Rerooting

🤔 Why does it work?

Think of it as transferring the "perspective" from parent to child. When we move the root from u to its child v:

• Vertices in v's subtree: each gets 1 closer → subtract sz[v]
• Vertices NOT in v's subtree: each gets 1 farther → add (n - sz[v])
• Net change: +(n - sz[v]) - sz[v] = +(n - 2·sz[v])

8.3.4 General Rerooting Pattern

The rerooting technique generalizes to many problems. The key is to identify:

1. What does down[v] represent for the original rooting?
2. When we "reroot" from parent u to child v, how does the answer change?
3. What is the formula to compute ans[v] from ans[u]?

General structure:

DFS 1 (post-order):
    down[v] = combine(down[child_1], down[child_2], ..., sz[v])

DFS 2 (pre-order):
    ans[v] = combine(down[v], up[v])
    For each child c of v:
        up[c] = f(ans[v], down[c], sz[c], n)
        // "up[c]" is the contribution from everything outside c's subtree

8.3.4b Rerooting Example 2: Max Depth from Every Node

Problem: For each vertex v, find the maximum distance from v to any other vertex (the "eccentricity" of v). Output N values.

This is harder than sum-of-distances because the max operation doesn't decompose as cleanly as sum.

Key insight: For each vertex v, the farthest vertex is either:

1. In v's own subtree (computed by down[] in DFS 1)
2. Reachable by going up through v's parent (computed by up[] propagated in DFS 2)

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

const int MAXN = 100001;
vector<int> adj[MAXN];
int n;

int down[MAXN];   // down[v] = max depth going DOWN into v's subtree
int up[MAXN];     // up[v]   = max depth going UP through v's parent
int ans[MAXN];    // ans[v]  = eccentricity of v (max distance to any node)

// DFS 1: compute down[] (max depth in subtree of v)
void dfs1(int u, int par) {
    down[u] = 0;
    for (int v : adj[u]) {
        if (v == par) continue;
        dfs1(v, u);
        down[u] = max(down[u], down[v] + 1);
    }
}

// DFS 2: propagate up[] downward (what's the farthest node going "upward"?)
// up[v] = max distance from v going through its parent
void dfs2(int u, int par) {
    ans[u] = max(down[u], up[u]);

    // To compute up[child], we need the 1st and 2nd deepest subtrees of u
    // (if child is on the deepest path, use 2nd deepest; otherwise use deepest)
    int best1 = -1, best2 = -1;   // top two children depths
    int best1_child = -1;

    for (int v : adj[u]) {
        if (v == par) continue;
        int d = down[v] + 1;
        if (d > best1) { best2 = best1; best1 = d; best1_child = v; }
        else if (d > best2) { best2 = d; }
    }

    for (int v : adj[u]) {
        if (v == par) continue;
        // up[v] = max distance from u going UP or to SIBLING subtrees
        int sibling_best = (v == best1_child) ? best2 : best1;
        // sibling_best: deepest subtree of u NOT going through v
        int through_parent = up[u] + 1;  // go up through u's parent, then down

        if (sibling_best == -1)
            up[v] = through_parent;
        else
            up[v] = max(through_parent, sibling_best + 1);
        //                                    ↑ go through u into sibling subtree
        // (+1 because we take one step from u to v, and up[v] should be
        //  the max distance starting from v going upward)
        // Actually: up[v] = 1 (edge u→v reversed) + max(sibling_best, up[u]+1-1)
        // Simplified: the max distance from u going *not* through v, then +1 for u→v
        up[v] = max(through_parent, (sibling_best >= 0 ? sibling_best + 1 : 0));

        dfs2(v, u);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> 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);
    }

    dfs1(0, -1);
    up[0] = 0;   // root has no parent
    dfs2(0, -1);

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

    return 0;
}

Tracing the algorithm:

Tree:      0
          / \
         1   2
        / \
       3   4

down[3]=0, down[4]=0, down[1]=1, down[2]=0, down[0]=2

up[0]=0 (root)
Processing 0's children: best1=down[1]+1=2 (child 1), best2=down[2]+1=1 (child 2)
  up[1] = max(up[0]+1, best2+1) = max(1, 2) = 2   ← sibling best is child 2
  up[2] = max(up[0]+1, best1+1) = max(1, 3) = 3   ← sibling best is child 1

ans[0] = max(down[0], up[0]) = max(2, 0) = 2
ans[1] = max(down[1], up[1]) = max(1, 2) = 2
ans[2] = max(down[2], up[2]) = max(0, 3) = 3
ans[3] = max(down[3], up[3]) = max(0, ?) = ...

💡 The key trick: Track the two deepest child subtrees separately. If the child we're computing up[] for is the deepest child, use the 2nd deepest for the sibling contribution.

8.3.4c Tree Knapsack (Subtree Selection DP)

Problem: Given a rooted tree where each vertex v has weight w[v] and value b[v]. Select vertices with total weight ≤ W, with the constraint: if you select v, you must also select its parent (connected subset from root). Maximize total value.

This is the classic tree knapsack (树背包).

Naive O(N²W) Approach

// dp[v][j] = max value when selecting exactly j weight from subtree of v, with v included
// dp[v][0] = 0 only if w[v]=0 (otherwise impossible to include v with 0 weight)
// Base: dp[v][w[v]] = b[v]  (only v selected, nothing from subtree)

const int MAXN = 501, MAXW = 501;
int dp[MAXN][MAXW];
int sz[MAXN];    // "capacity used" in subtree DP
int w[MAXN], b[MAXN];

void dfs(int u, int par) {
    // Initialize: select only u itself
    fill(dp[u], dp[u] + MAXW, -1);  // -1 = infeasible
    dp[u][w[u]] = b[u];
    sz[u] = w[u];

    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);

        // Merge dp[v] into dp[u] via knapsack convolution
        // Process in reverse to avoid counting items twice
        // Limit: only merge up to min(sz[u] + sz[v], W) weight
        for (int j = min(sz[u] + sz[v], W); j >= w[u]; j--) {
            for (int k = w[v]; k <= min(j - w[u], sz[v]); k++) {
                if (dp[u][j - k] != -1 && dp[v][k] != -1) {
                    dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k]);
                }
            }
        }
        sz[u] = min(sz[u] + sz[v], W);  // track total weight in subtree
    }
}

// Answer = max(dp[root][j]) for j = 0..W
// (dp[root][0] includes not selecting root, handle separately)

Why It's Actually O(NW) — The Merging Argument

The key insight that makes tree knapsack O(NW) rather than O(N²W):

Each pair of vertices (u, v) from different subtrees is compared exactly once during the merge at their LCA. Total comparisons across all merges = O(N² / N) × N = O(N²) pairs, but each comparison costs O(1) → actually O(N²) not O(NW)...

Wait — the correct argument: The total work is bounded by Σ sz[u] × sz[v] over all child merges (u=parent, v=child). By a counting argument, this sum equals O(N²) in the worst case for arbitrary trees — but can be shown to be O(NW) when capped at W.

Proof sketch: The total work at each vertex u when merging child v is O(sz[u_before] × sz[v]).
Summed over all merges, this is O(Σ products of subtree sizes) = O(N²) for trees.
But since each pair (i,j) of vertices can only contribute to the merge at their LCA,
and we cap the DP table at W, the total work is min(O(N²), O(NW)).

Practical implementation note: For USACO, N ≤ 300 and W ≤ 300 typically, so O(N²W) or O(NW) both pass easily.

Template for "Connected Subset from Root" Knapsack

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

const int MAXN = 305;
vector<int> adj[MAXN];
int w[MAXN], b[MAXN];
int dp[MAXN][MAXN];   // dp[v][j] = max value, j weight used in subtree of v (v included)
int subtree_w[MAXN];  // total weight in subtree

int n, W;

void dfs(int u, int par) {
    fill(dp[u], dp[u] + W + 1, 0);
    dp[u][w[u]] = b[u];
    subtree_w[u] = w[u];

    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);

        // Merge dp[v] into dp[u]
        int cap = min(subtree_w[u] + subtree_w[v], W);
        for (int j = cap; j >= w[u]; j--) {
            for (int k = w[v]; k <= min(j - w[u], subtree_w[v]); k++) {
                if (dp[v][k] > 0)
                    dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k]);
            }
        }
        subtree_w[u] = min(subtree_w[u] + subtree_w[v], W);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> W;
    for (int i = 0; i < n; i++) cin >> w[i] >> b[i];
    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);
    }

    dfs(0, -1);

    int ans = 0;
    for (int j = 0; j <= W; j++)
        ans = max(ans, dp[0][j]);

    cout << ans << "\n";
    return 0;
}

8.3.5 USACO Gold Tree DP Patterns

Pattern 1: Selecting Subtree Nodes

"Choose some vertices to activate. Activation of vertex v costs c[v] and gives benefit b[v]. Constraint: can only activate v if parent is active. Maximize net benefit."

This is the "dependent knapsack" tree DP:

// dp[v][j] = max benefit choosing j vertices from subtree of v
// Transition: combine dp[v] with dp[child] via knapsack merge

Pattern 2: Tree Path Queries

"For each vertex v, find the farthest vertex, or the sum of distances."

Rerooting template — exactly as in section 8.3.3.

Pattern 3: Matching/Pairing on Trees

"Pair up vertices on a tree (each pair connected by a path). Maximize number of disjoint pairs."

dp[v][0/1] = max matchings in subtree of v, where v is unmatched (0) or matched (1).

💡 思路陷阱（Pitfall Patterns）

陷阱 1：换根题用 O(N²) 暴力 DFS

错误判断： "对每个节点做一次 DFS 计算它当根时的答案，O(N²) 应该够" 实际情况： N=10⁵ 时 O(N²)=10¹⁰，稳定 TLE；此类题几乎都是换根 DP 的典型形态

题目特征（三选一即触发）：
  1. "对每个节点 v，求以 v 为根时..."
  2. "输出 N 个值，每个值对应某节点当根的结果"
  3. "求使某个全局指标最小/最大的根节点"

正确：Two-pass DFS (dfs1 下行 + dfs2 上行) → O(N)

识别信号： 输出 N 个值且每个值依赖"以该节点为根的某属性" → 换根 DP，而非 N 次 DFS

陷阱 2：树 DP 中忘记 if (v == par) continue

错误判断： "树是无向图，从 u 出发访问邻居，DFS 会自动不走回头路" 实际情况： 无向图的邻接表中父节点也在邻居列表里，不加 par 检查会死循环/重复计数

// 错误：没有 parent 检查
void dfs(int u) {
    for (int v : adj[u]) {
        dfs(v);              // 若 u 的父节点是 v，这里会死循环！
        dp[u] += dp[v];
    }
}

// 正确：传入 parent 参数
void dfs(int u, int par) {
    for (int v : adj[u]) {
        if (v == par) continue;   // ← 这一行至关重要
        dfs(v, u);
        dp[u] += dp[v];
    }
}

识别信号： 树的 DFS 运行时栈溢出或结果明显偏大 → 先检查有无 parent 防回溯

陷阱 3：把"树直径"用单次 DFS 求，得到错误答案

错误判断： "直径就是最深的叶子到根的距离，做一次 DFS 记录最大深度就行" 实际情况： 直径的两端点不一定经过根，单次 DFS 只算了"经过根的最长路径"

树：  1
     / \
    2   3
   /     \
  4       5
  |       |
  6       7

从根 1 出发最大深度 = 3（到 6 或 7），但直径 = 6→4→2→1→3→5→7 = 6 条边
单次 DFS from root 得到 3（错），正确做法：
  方法1：两次 DFS/BFS（从任意点找最远点 A，再从 A 找最远点 B）
  方法2：树 DP，每个节点维护最深和次深子树，直径 = 全局最大的 (最深+次深)

识别信号： "树上最长路径"题 → 直径，要么两次 BFS/DFS，要么树 DP 维护双最深

⚠️ Common Mistakes

1. Missing the if (v == par) continue: Without this check, DFS will traverse the edge back to the parent, leading to infinite recursion. Every tree DFS must have this guard.

2. Wrong base case for leaf nodes: Leaf nodes have no children, so the loop doesn't execute. Make sure dp[leaf] is initialized correctly before the loop.

3. Forgetting that rerooting requires dfs2 to run in pre-order: dfs2 must propagate from parent to children (top-down), so ans[u] must be computed before ans[children of u]. Don't accidentally run it post-order.

4. Integer overflow in subtree sums: If N = 10⁵ and each vertex contributes up to N to the sum, totals can reach 10¹⁰. Use long long.

5. Off-by-one in "sum of distances": The formula down[u] += down[v] + sz[v] adds sz[v] for each node in v's subtree (they're one edge farther). Make sure you understand why sz[v] rather than sz[v]-1.

📋 Chapter Summary

📌 Key Takeaways

❓ FAQ

Q: How do I know if a problem needs rerooting? A: If the problem asks for the same computation for every vertex as the root — "for each vertex, find X if it were the root" — that's rerooting. If it asks for just one fixed root, standard tree DP suffices.

Q: What if edge weights are not 1? A: Adjust the formulas. For weighted edges, down[u] += down[v] + sz[v] * w[u][v] when edge (u,v) has weight w. The rerooting formula changes accordingly.

Q: Can I use iterative DFS instead of recursive? A: Yes, and you should for large N (to avoid stack overflow). Convert DFS to iterative using an explicit stack, processing vertices in the reverse order you push them (post-order).

🔗 Connections to Later Chapters

• Ch.8.4 (Euler Tour): Euler tour + BIT/segment tree is the go-to approach when tree DP alone isn't efficient enough for range queries on trees.
• Ch.8.1 (MST): After building an MST from a general graph, the MST is a tree. Apply tree DP on it.
• Ch.6.3 (Advanced DP): Tree DP is a special case of DP on DAGs (Chapter 8.2). The techniques generalize.

🏋️ Practice Problems

🟢 Easy

8.3-E1. Subtree Queries Given a rooted tree, for each vertex v output the number of vertices in its subtree.

8.3-E2. Tree Diameter Find the diameter (longest path) of a tree with N vertices and unit edge weights.

🟡 Medium

8.3-M1. Maximum Independent Set (USACO-style) Given a tree with N vertices, each vertex has a value. Choose a subset of vertices with maximum total value such that no two chosen vertices are adjacent (connected by an edge).

8.3-M2. Sum of Distances (LeetCode 834 / USACO Gold) For each vertex in a tree, find the sum of distances to all other vertices. Output N values.

🔴 Hard

8.3-H1. Cow Gathering (USACO 2019 February Gold) N cows on a tree. Each cow has a "happiness" value. When a cow's parent leaves, the cow becomes happier. Simulate removals to maximize total happiness. (Simplified version: find the order to remove cows so each removal maximizes the total accumulated happiness.)

🏆 Challenge

8.3-C1. Tree Knapsack (Hard) Given a rooted tree with N vertices. Each vertex v has weight w[v] and value b[v]. Select a subset S of vertices with total weight ≤ W, such that if v ∈ S then parent(v) ∈ S (connected from root). Maximize total value.