DP on Trees

AL-28 | Compute optimal values for every subtree via post-order traversal, then extend to every possible root with a single rerooting pass -- solving "for all nodes" problems in $O(n)$.

Difficulty: [Intermediate]Prerequisites: DP -- 1D Introduction, DFS and Tree DFSCF Rating Range: 1500 -- 1900

Quick Revisit

• USE WHEN: answer at each node depends on its subtree (or full tree via rerooting)
• INVARIANT: dp[v] is computed only after all children of v are processed (post-order)
• TIME: O(n) per DFS pass | SPACE: O(n)
• CLASSIC BUG: forgetting to skip the parent in adjacency-list DFS
• PRACTICE: DP Practice Ladder

Contents

• 1. Intuition & Concept
• 2. Intuition
• 3. Implementation
• 4. Operations Reference
• 5. Problem Patterns & Tricks
• 6. Contest Cheat Sheet
• 7. Gotchas & Debugging
• Self-Test
• 8. Practice Problems
• 9. Further Reading

---

Intuition & Concept

A tree with $n$ nodes and $n-1$ edges has no cycles, so every subtree is independent once you remove the root edge. That independence is exactly what DP needs: solve smaller subproblems (children), combine at the parent.

Subtree DP (the basic idea). Root the tree at node 1. For every node $u$, define $dp[u]$ in terms of $dp[c]$ for each child $c$ of $u$. A single DFS (post-order) fills the entire table in $O(n)$.

Rerooting (the power move). Subtree DP answers queries only for the chosen root. If the problem says "for every node $v$, compute $f(v)$ as if $v$ were the root," you do not run $n$ separate DFS calls. Instead:

1. Run subtree DP once from an arbitrary root (say node 1) to get $dp\mathrm{\_}down[u]$.
2. Run a second DFS (pre-order) that computes $dp\mathrm{\_}up[u]$ -- the answer contributed by everything outside the subtree of $u$.
3. Combine: $ans[u]=\text{merge}(dp\mathrm{\_}down[u],dp\mathrm{\_}up[u])$.

Total work: $O(n)$ for both passes.

When it shows up on Codeforces. Tags: dp, trees, dfs and similar. Very common at 1600-1900 (Div 2 C/D). Classic signals:

• "For every node, compute ..."
• "Find the node that minimizes/maximizes ..."
• Tree diameter, tree center, sum of distances, maximum independent set.

Common traps at ~1100 level:

• Forgetting that the tree must be rooted before DP makes sense.
• Using adjacency matrix instead of adjacency list -- instant MLE on $n=2\times {10}^5$.
• Off-by-one: not skipping the parent when iterating neighbours.

---

Intuition

Layer 1 -- The Pain

Consider this tree with 6 nodes, each carrying a weight:

            1 (w=3)
           / \
     (w=4) 2   3 (w=5)
          / \    \
    (w=1) 4  5    6 (w=6)
            (w=2)

Problem: pick a subset of nodes so that no two picked nodes are adjacent, maximizing the total weight.

Brute force: enumerate all $2^6=64$ subsets, check the adjacency constraint for each, keep the best. For $n=6$ that is fine -- for $n=2\times {10}^5$ it is absurd. We need structure.

Layer 2 -- The Key Insight

A tree has no cycles, so each subtree is independent -- the answer for a node depends only on answers for its children.

Once we root the tree and decide whether a node $v$ is taken or not, the subtrees hanging below $v$ do not interact with each other. Define:

• $dp[v][0]$ = maximum weight in $\text{subtree}(v)$ when $v$ is not taken.
• $dp[v][1]$ = maximum weight in $\text{subtree}(v)$ when $v$ is taken.

Transitions:

$$dp[v][0]=\sum _{c\in \text{children}(v)}max(dp[c][0],dp[c][1])$$$$dp[v][1]=w[v]+\sum _{c\in \text{children}(v)}dp[c][0]$$

If $v$ is not taken, every child is free to be taken or not -- pick whichever is better. If $v$ is taken, no child may be taken.

Diagram A -- Subtree DP: values flow upward (leaves -> root)

Example: dp[v] = total number of nodes in subtree rooted at v.

  Tree structure:               After post-order DP:

         1                            1 [sz=5]
        / \                          / \
       2   3                  [sz=3] 2   3 [sz=1]
      / \                          / \
     4   5                  [sz=1] 4   5 [sz=1]

  Post-order traversal: 4 -> 5 -> 2 -> 3 -> 1

  ① sz[4] = 1              (leaf)                ↑
  ② sz[5] = 1              (leaf)                ↑  values
  ③ sz[2] = 1 + sz[4] + sz[5] = 3               ↑  flow
  ④ sz[3] = 1              (leaf)                ↑  upward
  ⑤ sz[1] = 1 + sz[2] + sz[3] = 5               ↑

  Key: each node is processed AFTER all its descendants.
  Parent never runs until every child is done -> invariant holds.

Layer 3 -- Visual Walkthrough

Root the tree at node 1 and process in post-order (leaves first).

Tree (rooted at 1):

            1 (w=3)
           / \
     (w=4) 2   3 (w=5)
          / \    \
    (w=1) 4  5    6 (w=6)
            (w=2)

Post-order visit: 4, 5, 2, 6, 3, 1

Step 1 -- Leaves (nodes 4, 5, 6):

  Node 4 (w=1): dp[4][0] = 0   dp[4][1] = 1
  Node 5 (w=2): dp[5][0] = 0   dp[5][1] = 2
  Node 6 (w=6): dp[6][0] = 0   dp[6][1] = 6

No children, so "not taken" yields 0 and "taken" yields the node weight.

Step 2 -- Node 2 (w=4), children = {4, 5}:

  dp[2][0] = max(dp[4][0], dp[4][1]) + max(dp[5][0], dp[5][1])
           = max(0, 1) + max(0, 2)
           = 1 + 2 = 3

  dp[2][1] = w[2] + dp[4][0] + dp[5][0]
           = 4 + 0 + 0 = 4

Not taking 2 lets us cherry-pick each child independently (total 3). Taking 2 forces children off (total 4). Taking 2 wins here.

Step 3 -- Node 3 (w=5), child = {6}:

  dp[3][0] = max(dp[6][0], dp[6][1])
           = max(0, 6) = 6

  dp[3][1] = w[3] + dp[6][0]
           = 5 + 0 = 5

Not taking 3 and taking 6 (weight 6) beats taking 3 (weight 5).

Step 4 -- Node 1 (w=3), children = {2, 3}:

  dp[1][0] = max(dp[2][0], dp[2][1]) + max(dp[3][0], dp[3][1])
           = max(3, 4) + max(6, 5)
           = 4 + 6 = 10

  dp[1][1] = w[1] + dp[2][0] + dp[3][0]
           = 3 + 3 + 6 = 12

Answer: $max(dp[1][0],dp[1][1])=max(10,12)=12$.

Optimal selection: take nodes 1, 4, 5, 6 ($3+1+2+6=12$). No two are adjacent. Verify: 1-2 edge? 2 not taken. 1-3 edge? 3 not taken. Correct.

  Summary dp table:

  Node |  w  | dp[.][0] | dp[.][1] | best
  -----+-----+----------+----------+------
    4  |  1  |    0     |    1     |   1
    5  |  2  |    0     |    2     |   2
    6  |  6  |    0     |    6     |   6
    2  |  4  |    3     |    4     |   4
    3  |  5  |    6     |    5     |   6
    1  |  3  |   10     |   12     |  12

Diagram C -- Maximum Independent Set: taken (●) vs not-taken (○)

  Tree with weights:

              1 (w=3)
             / \
       (w=4) 2   3 (w=5)
            / \    \
      (w=1) 4  5    6 (w=6)
              (w=2)

  DP values (post-order):

    Node  |  w  | dp[v][0] (v skip) | dp[v][1] (v take)
    ------+-----+--------------------+------------------
      4   |  1  |        0           |        1
      5   |  2  |        0           |        2
      6   |  6  |        0           |        6
      2   |  4  |    max(0,1)        |   4 + 0 + 0 = 4
          |     |   +max(0,2) = 3    |
      3   |  5  |    max(0,6) = 6    |   5 + 0 = 5
      1   |  3  |    max(3,4)        |   3 + 3 + 6 = 12  <- winner
          |     |   +max(6,5) = 10   |

  Optimal selection (answer = 12):

              ● 1 (w=3)            ● = taken
             / \                   ○ = not taken
            ○ 2   ○ 3
           / \      \              Taken: {1, 4, 5, 6}
          ● 4  ● 5   ● 6          Weight: 3+1+2+6 = 12

  Rule: ● node -> all children must be ○
        ○ node -> each child independently ● or ○

The walkthrough shows how each node's DP values build from its children. We can now state the guarantee that makes this correct.

Layer 4 -- The Invariant

+--------------------------------------------------------------+
| INVARIANT: After processing all children of v,               |
|   dp[v][0] = max weight in subtree(v) with v NOT taken       |
|   dp[v][1] = max weight in subtree(v) with v taken           |
| are both correct for subtree(v).                             |
+--------------------------------------------------------------+

Post-order guarantees every child is finished before its parent. The invariant holds trivially at leaves and is preserved at each internal node by the transition formulas.

What the Code Won't Teach You

Why tree DP is natural. Trees have no cycles, so subtree answers are independent -- removing the edge between a node and its parent splits the tree into pieces that don't interact. This is exactly the "optimal substructure" property DP requires. On general graphs with cycles, subproblems overlap through back-edges, making pure DP much harder (or impossible without extra machinery).

The "root and think about subtrees" paradigm. Even when the tree is unrooted in the problem statement, the first move is always: pick any node as root and decompose into subtrees. The answer for the whole tree = combine(answers for root's children's subtrees). This mental reflex -- root it, then think subtree by subtree -- is the entry point for every tree DP problem.

When tree DP needs additional dimensions. Sometimes $dp[v]$ (one value per node) isn't enough. If the problem has a budget, count, or resource constraint, you may need $dp[v][k]$ = "best answer for subtree of $v$ using exactly $k$ resources." The merging step then becomes a knapsack-like convolution over children's DP arrays -- $O(n\cdot K)$ or $O(n\cdot K^2)$ depending on the merge. Recognize the extra parameter early so you can design the state correctly.

Rerooting intuition. Compute $dp\mathrm{\_}down[v]$ (the answer considering only the subtree below $v$), then $dp\mathrm{\_}up[v]$ (the contribution from everything above$v$), and combine for the full answer at $v$. The key formula: $dp\mathrm{\_}up[\text{child}]$ is derived from $dp\mathrm{\_}up[\text{parent}]$ plus the sibling subtrees -- "everything the parent sees, minus what the child already contributed." Two DFS passes, $O(n)$ total.

Diagram B -- Rerooting: dp_down (pass 1, ↑) then dp_up (pass 2, ↓)

Problem: for each node v, find sum of distances to all other nodes.
Tree (n=5):
         1
        / \
       2   3
      / \
     4   5

PASS 1 -- bottom-up (leaves -> root):
  Compute dp_down[v] = sum of distances within subtree(v), sz[v] = subtree size.

  dp_down[4]=0  sz[4]=1                              ↑
  dp_down[5]=0  sz[5]=1                              ↑
  dp_down[2]=dp_down[4]+sz[4]+dp_down[5]+sz[5]=2     ↑ flows up
  dp_down[3]=0  sz[3]=1                              ↑
  dp_down[1]=dp_down[2]+sz[2]+dp_down[3]+sz[3]=6     ↑

  After Pass 1:

         1 [dp_down=6, sz=5]
        / \
       2   3 [dp_down=0, sz=1]
 [dp_down=2, sz=3]
      / \
     4   5
 [dp_down=0] [dp_down=0]

PASS 2 -- top-down rerooting (root -> leaves):
  ans[v] = sum of distances from v to ALL nodes (not just subtree).
  Formula: ans[child] = ans[parent] - sz[child] + (n - sz[child])
           i.e. sz[child] nodes get closer, (n-sz[child]) get farther.

  ans[1] = dp_down[1] = 6                            ↓
  ans[2] = 6 - 3 + (5 - 3) = 5                       ↓ reroot
  ans[3] = 6 - 1 + (5 - 1) = 9                       ↓ propagates
  ans[4] = 5 - 1 + (5 - 1) = 8                       ↓ downward
  ans[5] = 5 - 1 + (5 - 1) = 8                       ↓

  After Pass 2:

         1 [ans=6]
        / \
       2   3 [ans=9]
   [ans=5]
      / \
     4   5
  [ans=8] [ans=8]

  Verify ans[4]: distances from 4 are 4->2(1), 4->1(2), 4->3(3), 4->5(2) = 8 OK
  Two passes. O(n) total. No repeated work.

Layer 5 -- When to Reach for This

Trigger phrases:

• "tree" + "optimal selection" or "maximum/minimum subset"
• "subtree DP", "for every subtree compute ..."
• "rerooting" or "for every node as root"
• "no two adjacent nodes" on a tree
• "sum of distances", "farthest node", "tree diameter"

Counter-examples (this is NOT tree DP):

• Graph has cycles --> not a tree; consider general graph DP or cycle-finding first.
• Grid/matrix structure --> grid DP, not tree DP.
• Problem asks for k-th shortest path on a tree --> usually binary lifting or LCA, not DP on trees.
• DAG but not a tree --> topological-order DP, not subtree DP.

---

Implementation

Version 1 -- Subtree DP: Maximum Independent Set on a Tree

Each node has weight $w[i]$. Pick a subset of nodes with no two adjacent, maximizing total weight.

$dp[u][0]$ = best answer in subtree of $u$ when $u$ is not taken. $dp[u][1]$ = best answer in subtree of $u$ when $u$ is taken.

Transition:

$$dp[u][0]=\sum _{c\in \text{children}(u)}max(dp[c][0],dp[c][1])$$$$dp[u][1]=w[u]+\sum _{c\in \text{children}(u)}dp[c][0]$$

Minimal template

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

int main() {
    int n;
    scanf("%d", &n);
    vector<long long> w(n + 1);
    for (int i = 1; i <= n; i++) scanf("%lld", &w[i]);
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // dp[u][0] = u not taken, dp[u][1] = u taken
    vector<array<long long, 2>> dp(n + 1, {0, 0});

    // Iterative post-order DFS to avoid stack overflow
    vector<int> order, par(n + 1, 0);
    vector<bool> vis(n + 1, false);
    order.reserve(n);
    stack<int> st;
    st.push(1);
    vis[1] = true;
    while (!st.empty()) {
        int u = st.top(); st.pop();
        order.push_back(u);
        for (int v : adj[u]) {
            if (!vis[v]) {
                vis[v] = true;
                par[v] = u;
                st.push(v);
            }
        }
    }

    // Process in reverse order (leaves first)
    for (int i = (int)order.size() - 1; i >= 0; i--) {
        int u = order[i];
        dp[u][1] = w[u];
        for (int v : adj[u]) {
            if (v == par[u]) continue;
            dp[u][0] += max(dp[v][0], dp[v][1]);
            dp[u][1] += dp[v][0];
        }
    }

    printf("%lld\n", max(dp[1][0], dp[1][1]));
}

Explained version

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

int main() {
    int n;
    scanf("%d", &n);
    vector<long long> w(n + 1);
    for (int i = 1; i <= n; i++) scanf("%lld", &w[i]);

    // Build adjacency list (undirected tree)
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // dp[u][0]: max weight in subtree(u) with u NOT selected
    // dp[u][1]: max weight in subtree(u) with u selected
    vector<array<long long, 2>> dp(n + 1, {0, 0});

    // --- Iterative DFS to get processing order ---
    // We need post-order: process children before parents.
    // Strategy: BFS-like push to get pre-order, then reverse.
    vector<int> order, par(n + 1, 0);
    vector<bool> vis(n + 1, false);
    order.reserve(n);
    stack<int> st;
    st.push(1);       // root the tree at node 1
    vis[1] = true;
    while (!st.empty()) {
        int u = st.top(); st.pop();
        order.push_back(u);
        for (int v : adj[u]) {
            if (!vis[v]) {
                vis[v] = true;
                par[v] = u;   // record parent for skipping in DP
                st.push(v);
            }
        }
    }

    // --- Subtree DP (post-order = reversed pre-order) ---
    for (int i = (int)order.size() - 1; i >= 0; i--) {
        int u = order[i];
        dp[u][1] = w[u]; // if we take u, start with its weight
        for (int v : adj[u]) {
            if (v == par[u]) continue; // skip parent edge
            // If u is NOT taken, each child can be taken or not
            dp[u][0] += max(dp[v][0], dp[v][1]);
            // If u IS taken, no child can be taken
            dp[u][1] += dp[v][0];
        }
    }

    // Answer: best of taking or not taking the root
    printf("%lld\n", max(dp[1][0], dp[1][1]));
}

Version 2 -- Rerooting: Sum of Distances to All Nodes

Given a tree with $n$ nodes, for every node $u$ compute the sum of distances from $u$ to all other nodes.

Key rerooting identity: when moving from parent $p$ to child $c$ across their edge, $sz[c]$ nodes get closer by 1 and $n-sz[c]$ nodes get farther by 1:

$$ans[c]=ans[p]-sz[c]+(n-sz[c])=ans[p]+n-2\cdot sz[c]$$

Minimal template

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

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

    vector<long long> sz(n + 1, 1), dp(n + 1, 0), ans(n + 1, 0);
    vector<int> order, par(n + 1, 0);
    vector<bool> vis(n + 1, false);
    order.reserve(n);

    // BFS to get order + parent
    stack<int> st;
    st.push(1); vis[1] = true;
    while (!st.empty()) {
        int u = st.top(); st.pop();
        order.push_back(u);
        for (int v : adj[u]) if (!vis[v]) {
            vis[v] = true;
            par[v] = u;
            st.push(v);
        }
    }

    // Pass 1: subtree sizes and sum-of-distances from root
    for (int i = (int)order.size() - 1; i >= 0; i--) {
        int u = order[i];
        for (int v : adj[u]) if (v != par[u]) {
            sz[u] += sz[v];
            dp[u] += dp[v] + sz[v]; // each node in subtree(v) is 1 farther
        }
    }

    // Pass 2: rerooting (pre-order)
    ans[1] = dp[1];
    for (int i = 0; i < (int)order.size(); i++) {
        int u = order[i];
        for (int v : adj[u]) if (v != par[u]) {
            ans[v] = ans[u] + n - 2 * sz[v];
        }
    }

    for (int i = 1; i <= n; i++) printf("%lld%c", ans[i], " \n"[i == n]);
}

Explained version

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

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

    vector<long long> sz(n + 1, 1);  // subtree size (init 1 = the node itself)
    vector<long long> dp(n + 1, 0);  // sum of dist in subtree (rooted at 1)
    vector<long long> ans(n + 1, 0); // final answer for each node as root
    vector<int> order, par(n + 1, 0);
    vector<bool> vis(n + 1, false);
    order.reserve(n);

    // --- Build DFS order + parent array (iterative to avoid stack overflow) ---
    stack<int> st;
    st.push(1); vis[1] = true;
    while (!st.empty()) {
        int u = st.top(); st.pop();
        order.push_back(u);
        for (int v : adj[u]) if (!vis[v]) {
            vis[v] = true;
            par[v] = u;
            st.push(v);
        }
    }

    // --- Pass 1: post-order (reverse of DFS order) ---
    // Compute sz[u] and dp[u] = sum of distances from u to all nodes in subtree(u)
    for (int i = (int)order.size() - 1; i >= 0; i--) {
        int u = order[i];
        for (int v : adj[u]) {
            if (v == par[u]) continue;
            sz[u] += sz[v];
            // Every node in subtree(v) is at distance (dp[v]/sz[v] avg) from v,
            // plus 1 more edge to reach u. So contribution = dp[v] + sz[v].
            dp[u] += dp[v] + sz[v];
        }
    }

    // --- Pass 2: pre-order rerooting ---
    // Key insight: when root moves from p to child c,
    //   - sz[c] nodes become 1 closer  (they are in c's subtree)
    //   - (n - sz[c]) nodes become 1 farther (they are outside)
    //   ans[c] = ans[p] - sz[c] + (n - sz[c]) = ans[p] + n - 2*sz[c]
    ans[1] = dp[1]; // root's answer is just the subtree DP value
    for (int i = 0; i < (int)order.size(); i++) {
        int u = order[i];
        for (int v : adj[u]) {
            if (v == par[u]) continue;
            ans[v] = ans[u] + n - 2 * sz[v];
        }
    }

    for (int i = 1; i <= n; i++) printf("%lld%c", ans[i], " \n"[i == n]);
}

---

Operations Reference

Every operation here is linear -- the tree's acyclic structure means each node is visited a constant number of times per pass.

Operation	Time	Space
Build adjacency list	$O(n)$	$O(n)$
Subtree DP (single DFS)	$O(n)$	$O(n)$
Rerooting (second DFS)	$O(n)$	$O(n)$
Full rerooting (both passes)	$O(n)$	$O(n)$
Naive approach (DFS from every node)	$O(n^2)$	$O(n)$
Tree diameter (two-BFS or DP)	$O(n)$	$O(n)$
Maximum independent set on tree	$O(n)$	$O(n)$

---

Problem Patterns & Tricks

Pattern 1 -- Tree Diameter

Find the longest path in the tree.

For each node $u$, track the two longest paths going down into its subtree. The diameter passing through $u$ is their sum. Global answer is the max over all $u$.

// dp[u] = longest downward path from u
// Update global diameter when combining two children
int diameter = 0;
// In post-order:
for (int v : adj[u]) {
    if (v == par[u]) continue;
    if (dp[v] + 1 + dp[u] > diameter)
        diameter = dp[v] + 1 + dp[u]; // path through u
    dp[u] = max(dp[u], dp[v] + 1);
}

Problems:CF 1143C -- Queen, CSES -- Tree Diameter

Pattern 2 -- Sum of Distances (Rerooting)

For every node, find the sum of distances to all other nodes. Classic rerooting as shown in the implementation section.

$$ans[c]=ans[p]+n-2\cdot sz[c]$$

Problems:CF 1187E -- Tree Painting, CSES -- Sum of Distances

Pattern 3 -- Maximum Independent Set on Tree

Select nodes with no two adjacent, maximizing weight sum. Two-state DP: $dp[u][0/1]$ as shown in Implementation Version 1.

Problems:CSES -- Tree Matching, CF 1528A -- Parsa's Humongous Tree

Pattern 4 -- Tree Center (All Farthest Nodes via Rerooting)

Find the node that minimizes the maximum distance to any other node.

First compute the farthest node in each subtree with subtree DP, then reroot to get the farthest node considering the rest of the tree. The tree center is the node minimizing this value.

Equivalent approach: the center lies on the diameter, at its midpoint.

// dp_down[u] = farthest node distance within subtree(u)
// dp_up[u] = farthest node distance outside subtree(u)
// ans[u] = max(dp_down[u], dp_up[u])
// Need top-2 children for rerooting (can't subtract max from itself)

Problems:CF 1833G -- Ants on a Tree, CSES -- Tree Distances I

Pattern 5 -- Counting Paths / Subtree Aggregation

Count the number of node pairs at distance exactly $k$, or aggregate some function over all paths. Often uses centroid decomposition for the general case, but for small $k$ or specific structure, subtree DP suffices.

// dp[u] = number of nodes at distance d from u within subtree
// Merge child arrays, count valid pairs, then add to parent

Problems:CF 161D -- Distance in Tree, CSES -- Tree Distances II

Pattern 6 -- Edge Contribution Technique

Instead of summing over paths, sum over edges. Each edge $(u,v)$ where $v$ is a child contributes to $sz[v]\times (n-sz[v])$ paths. Useful for computing the sum of all pairwise distances.

$$\text{total}=\sum _{\text{edge }(u,v)}w(u,v)\cdot sz[v]\cdot (n-sz[v])$$

Problems:CF 1092F -- Tree with Maximum Cost, CF 600E -- Lomsat gelral

Pattern 7 -- DP with "Take / Don't Take" on Trees (Coloring)

Assign colors/states to nodes with constraints on adjacent nodes. Standard multi-state DP on tree.

// dp[u][color] = number of valid colorings of subtree(u) with u = color
// Multiply over children (independence of subtrees)
for (int v : adj[u]) {
    if (v == par[u]) continue;
    long long sum = 0;
    for (int c2 = 0; c2 < K; c2++)
        if (c2 != color) sum += dp[v][c2];
    dp[u][color] = dp[u][color] * sum % MOD;
}

Problems:CF 1223E -- Paint the Tree, CF 1528A -- Parsa's Humongous Tree

---

Contest Cheat Sheet

+------------------------------------------------------------------+
|                    DP ON TREES  --  CHEAT SHEET                  |
+------------------------------------------------------------------+
| WHEN TO USE:                                                     |
|   - Problem on a tree asks "for every node" or "optimal subset"  |
|   - "Minimize/maximize over all possible roots"  --> rerooting   |
|   - "Sum of distances", "farthest node", "tree diameter"         |
+------------------------------------------------------------------+
| SUBTREE DP TEMPLATE:                                             |
|   Root at 1. Iterative DFS for order + parent.                   |
|   for (i = n-1 .. 0)  // post-order                             |
|     for (v : adj[order[i]])                                      |
|       if (v != par[order[i]])                                    |
|         dp[order[i]] = combine(dp[order[i]], dp[v]);             |
+------------------------------------------------------------------+
| REROOTING TEMPLATE:                                              |
|   ans[root] = dp[root];                                         |
|   for (i = 0 .. n-1)  // pre-order                              |
|     for (v : adj[order[i]])                                      |
|       if (v != par[order[i]])                                    |
|         ans[v] = reroot(ans[order[i]], dp[v], n);                |
+------------------------------------------------------------------+
| SUM-OF-DIST REROOT:  ans[c] = ans[p] + n - 2*sz[c]             |
| DIAMETER:  track top-2 depths per node, ans = max(d1+d2)        |
| INDEP SET: dp[u][0] += max(dp[v][0..1]), dp[u][1] += dp[v][0]  |
+------------------------------------------------------------------+
| COMPLEXITY:  O(n) time, O(n) space for both passes               |
+------------------------------------------------------------------+

---

Gotchas & Debugging

1. Stack overflow on deep trees. Recursive DFS crashes on chains of $n=2\times {10}^5$. Always use iterative DFS (stack-based) or increase the stack size with ulimit -s unlimited / #pragma comment(linker, "/STACK:...").

2. Forgetting to skip the parent. In an undirected adjacency list, every neighbour appears -- including the parent. Always check if (v == par[u]) continue;.

3. Rerooting needs the inverse of the merge operation. If your combine is addition, the inverse is subtraction. If it is multiplication, you need modular inverse or prefix/suffix products. If the merge has no inverse (e.g., max), store the top-2 values per node.

4. Integer overflow. Subtree sizes multiplied together ($sz[v]\times (n-sz[v])$) can exceed ${10}^{10}$. Use long long.

5. 1-indexed vs 0-indexed. Pick one and be consistent. The templates above use 1-indexed nodes.

6. Multiple test cases. Remember to clear/reset dp, sz, par, vis, order between test cases. Use fill or re-assign.

7. Rooting matters for DP, not for the answer. The rerooting technique makes the answer root-independent. But the DP arrays depend on which node you picked as root. Do not mix dp_down values computed from different roots.

8. Edge weights. When edges have weights, add the weight in the transition: dp[u] += dp[v] + w(u,v) * sz[v] instead of dp[u] += dp[v] + sz[v].

Mental Traps

"Tree DP always roots the tree at node 1." You can root at any node. For problems like maximum independent set, the answer is the same regardless of the root -- the DP values change but the final result doesn't. For problems where the answer depends on the root (like sum of distances), rerooting DP computes the answer for every possible root in $O(n)$. Some problems even require rerooting to find the optimal root. Don't hardcode "root = 1" into your mental model.

"dp[v] only depends on children of v." In standard subtree DP, yes. But in rerooting, $dp[v]$ also depends on the parent's contribution -- the information from the rest of the tree outside $v$'s subtree. This "parent contribution" ($dp\mathrm{\_}up[v]$) is the key insight of rerooting DP. If you only think "children -> parent," you'll never discover the second pass.

"I need to traverse the tree multiple times for rerooting." You need exactly two passes: one DFS bottom-up for subtree DP ($dp\mathrm{\_}down$), one DFS top-down for rerooting ($dp\mathrm{\_}up$). Not three, not $n$ -- just two. The second pass reuses all the information from the first.

Mental model: two passes cover the entire tree

         1                Pass 1 (↑ bottom-up):
        / \               Leaves -> root.
       2   3              dp_down[v] = f(children of v)
      / \
     4   5                Pass 2 (↓ top-down):
                          Root -> leaves.
   Pass 1: ↑ ↑ ↑ ↑       dp_up[v] = g(dp_up[parent], siblings)
   4->2, 5->2, 3->1, 2->1
                          ans[v] = combine(dp_down[v], dp_up[v])
   Pass 2: ↓ ↓ ↓ ↓
   1->2, 1->3, 2->4, 2->5    Total: O(n) + O(n) = O(n). Done.

---

Common Mistakes

1. Forgetting to skip the parent. In adjacency-list DFS, every neighbor includes the parent. Without if (u == par) continue;, you recurse back up and get infinite loops or wrong answers.
2. Rerooting with non-invertible operations. Rerooting needs to "remove" a child's contribution. This works for sum (subtract), but not for max (need prefix/suffix decomposition instead). Always ask "is my combine operation invertible?" before rerooting. For non-invertible aggregations like max/min, store top-2 children (best and second-best): when rerooting to a child that provided the best value, fall back to the second-best.
3. Stack overflow on deep trees. Recursive DFS on a chain of n = 10^5 nodes exceeds default stack limits. Use iterative DFS or increase stack size (ulimit -s unlimited or pragma).
4. Wrong subtree size computation. sz[v] = 1 + sum(sz[child]). Forgetting the +1 for the node itself is a subtle off-by-one that corrupts all ancestor values.
5. Merging children in wrong order. Some tree DP problems (e.g., tree knapsack) require careful ordering of child merges to achieve the right complexity.

Debug Drills

Drill 1. Forgotten parent exclusion.

// Compute subtree sizes
vector<int> adj[200005];
int sz[200005];

void dfs(int u) {
    sz[u] = 1;
    for (int v : adj[u]) {
        dfs(v);         // BUG: will revisit parent!
        sz[u] += sz[v];
    }
}

What's wrong?

In an undirected tree stored as an adjacency list, adj[u] includes the parent of u. Without passing and checking a parent parameter, dfs will recurse back to the parent, causing infinite recursion (stack overflow). Fix: Add int par parameter: void dfs(int u, int par) and skip v == par in the loop. Call as dfs(root, -1).

Drill 2. Rerooting double-counts root's contribution.

// Rerooting for sum of distances
void reroot(int u, int par) {
    for (int v : adj[u]) {
        if (v == par) continue;
        ans[v] = ans[u] + n - 2 * sz[v]; // correct formula
        reroot(v, u);
    }
}
// BUG: ans[root] was never initialized before calling reroot!

What's wrong?

ans[root] must be initialized to down[root] (the sum of distances from the root to all other nodes, computed in the first DFS). If ans[root] is left at 0 or uninitialized, every subsequent ans[v] computed from it will be wrong. Fix: Before calling reroot(root, -1), set ans[root] = down[root] where down[root] is the sum of depths of all nodes (computed via a prior DFS).

Drill 3. Wrong merge order in tree knapsack.

// Tree knapsack: max value picking at most K nodes from subtree of u
// dp[u][j] = best value using j nodes from subtree of u
void dfs(int u, int par) {
    sz[u] = 1;
    dp[u][1] = val[u];
    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);
        // BUG: merging in wrong order overwrites dp[u] mid-loop
        for (int j = 1; j <= sz[u] + sz[v]; j++)
            for (int k = 0; k <= sz[v] && k <= j; k++)
                dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k]);
        sz[u] += sz[v];
    }
}

What's wrong?

The inner merge loop reads and writes dp[u][j] simultaneously. When computing dp[u][j] with some allocation k to child v, dp[u][j-k] might already be overwritten by this same merge pass. This is the classic knapsack "forward overwrite" error. Fix: Use a temporary array: copy dp[u] to tmp, compute the merge into tmp, then copy back. Alternatively, iterate j in decreasing order (like 0/1 knapsack) to avoid overwriting values you still need.

---

Self-Test

Before moving to practice problems, verify you can do each of these without referring back to the notes:

• [ ] Implement tree diameter using two DFS calls or a single tree DP
• [ ] Compute the size of every subtree with one DFS
• [ ] Implement basic tree DP: maximum independent set on a tree
• [ ] Explain rerooting DP and implement it for "sum of distances to all other nodes"
• [ ] Handle the edge case: tree with a single node
• [ ] State why tree DP works (no cycles -> subtrees are independent subproblems)
• [ ] Convert between adjacency list tree representation and parent array

---

Practice Problems

CF Rating	What You Should Be Comfortable With
1200	Basic subtree DP: compute subtree sizes, subtree sums, tree diameter via two DFS passes; understand post-order evaluation
1500	Two-state DP on trees (e.g., "take/skip" at each node, tree matching); tree DP with small state per node (coloring, independent set)
1800	Rerooting technique: compute answer at root, then propagate to all nodes in O(n); problems like Tree Distances I/II (CSES), Tree Painting (CF 1187E)
2100	Merging subtree DPs (knapsack on tree), small-to-large merging / DSU on tree, DP with auxiliary data structures (segment tree, convex hull trick on tree paths)

#	Problem	Source	Difficulty	Key Idea
1	Tree Diameter	CSES	Easy	Track max depth per subtree
2	Tree Distances I	CSES	Easy-Med	Rerooting for farthest node
3	Tree Distances II	CSES	Medium	Rerooting sum-of-distances
4	Tree Matching	CSES	Medium	Greedy DP on tree edges
5	Distance in Tree	CF 161D	Medium	Count pairs at distance $k$
6	Tree Painting	CF 1187E	Medium	Rerooting with subtree sizes
7	Tree with Maximum Cost	CF 1092F	Medium	Rerooting weighted sum
8	Parsa's Humongous Tree	CF 1528A	Medium	Two-state DP (min/max at node)
9	Lomsat gelral	CF 600E	Hard	DSU on tree / small-to-large merge
10	Appleman and Tree	CF 461C	Hard	DP counting with black/white coloring

---

Further Reading

• cp-algorithms: DP on Trees -- solid reference with rerooting examples.
• Codeforces Blog: Rerooting Technique -- detailed walkthrough with practice problems.
• Codeforces Blog: DP on Trees Tutorial -- classic introductory blog.
• USACO Guide: DP on Trees -- well-structured with graded problems.
• See: DP -- 1D Introduction
• See: DFS and Tree DFS
• See also: Centroid Decomposition (tracked in GAPS.md for a future advanced file)

---

Recap

• Tree DP = post-order DFS. Compute dp[v] from children's dp values, bottom-up.
• Rerooting extends subtree answers to full-tree answers in a second DFS pass: "subtract the child, add the world."
• Rerooting requires invertibility (or prefix/suffix decomposition) of the combine operation.
• Classic problems: max independent set on tree, tree diameter, centroid decomposition setup, subtree queries.

---

Cross-Links

• DP -- 1D Introduction -- 1D DP foundations before tree DP
• DFS and Tree DFS -- tree traversal mechanics underlying tree DP
• DP Thinking Framework -- tree DP is a key state archetype
• DP Practice Ladder -- graded problem set