ix. Tree DP and Rerooting

State = a subtree (plus a few flags about its root). Compute children before parents: recursion, or a BFS order processed backwards (no stack overflow). Rerooting gives the answer for every root in $O(n)$ with a second, top-down pass. Size-bounded merging makes “choose $k$ vertices” DPs $O(nk)$ instead of $O(n{k}^2)$.

Patterns

Problem	State	Merge child $v$ into $u$
max weight independent set	$f_{u,0/1}$ ($u$ taken?)	$f_{u,0}+=\max (f_{v,0},f_{v,1})$, $f_{u,1}+=f_{v,0}$
min vertex cover	$f_{u,0/1}$	$f_{u,0}+=f_{v,1}$, $f_{u,1}+=\min$
min dominating set	$f_{u,\{\text{taken},\text{dominated by child},\text{not yet dominated}\}}$	three-state merge
max matching	greedy: match a leaf with its parent (or $f_{u,0/1}$ = $u$ matched to a child)
diameter / longest path	two deepest child depths	answer $=\max (d_1+d_2)$
number of connected subgraphs containing $u$	$f_u=\prod (1+f_v)$
colourings with constraints	$f_{u,c}$	$f_{u,c}\ast ={\sum }_{c^{\prime }\text{ compatible}}{f}_{v,c^{\prime }}$
exactly $k$ chosen vertices / edges	$f_{u,j}$	size-bounded knapsack merge
depth-indexed counts ($\#$ vertices at depth $d$)	$f_{u,d}$	long-path decomposition, $O(n)$ (Long-Path)
convex piecewise-linear cost per vertex	slope-trick heaps	merge heaps small-to-large (Slope Trick)
order of visiting children matters (min total waiting time)	exchange argument on children	sort by ratio, then DP (Exchange)
distinct colours/values per subtree	DSU on tree, or Euler tour + offline queries	—
delete edges to satisfy a global constraint	$f_{u,\text{state}}$	fold the constraint (parity, remaining budget, …) into the state

vector<int> order{root}, par(n, -1);                       // iterative skeleton
for (int i = 0; i < sz(order); i++) for (int v : adj[order[i]]) if (v != par[order[i]]) par[v] = order[i], order.push_back(v);
for (int i = n - 1; i >= 0; i--) { int u = order[i]; /* children of u are finished; combine them into f[u] */ }

Tree knapsack in $O(nk)$

$f_{u,j}$ = best value of a connected set of $j$ vertices in $u$‘s subtree containing $u$ (or “choose $j$ items in the subtree”, same merge). Merge children with loops bounded by the current sizes, capped at $k$:

vector<ll> treeKnap(const vector<vector<int>>& adj, const vector<ll>& val, int root, int K) {   // K >= 1
    int n = sz(adj); vector<int> order{root}, par(n, -1);
    for (int i = 0; i < sz(order); i++) for (int v : adj[order[i]]) if (v != par[order[i]]) par[v] = order[i], order.push_back(v);
    vector<vector<ll>> dp(n);
    for (int i = n - 1; i >= 0; i--) {
        int u = order[i]; vector<ll> cur{0, val[u]};       // cur[j], j >= 1 includes u
        for (int v : adj[u]) if (v != par[u]) {
            auto& d = dp[v];                                // d[0] = 0: take nothing from v's subtree
            vector<ll> nx(min<int>(K, sz(cur) + sz(d) - 2) + 1, LLONG_MIN); nx[0] = 0;
            for (int a = 1; a < sz(cur); a++) for (int b = 0; b < sz(d) && a + b < sz(nx); b++) nx[a + b] = max(nx[a + b], cur[a] + d[b]);
            cur.swap(nx); vector<ll>().swap(d);
        }
        if (sz(cur) > K + 1) cur.resize(K + 1);
        dp[u] = move(cur);
    }
    return dp[root];                                        // dp[root][j]: best connected j-set containing root
}

Proof: the merges cost $O(nk)$ in total ($O(n^2)$ without a cap)

Lay the vertices out in DFS order. When $u$‘s accumulated part $A$ (already merged children plus $u$) meets child subtree $B$, $A$ is a contiguous block of the DFS order immediately followed by the block $B$. The merge costs at most $\min (|A|,k)\cdot \min (|B|,k)$; charge it to the pairs $(x,y)$ with $x$ among the last $\min (|A|,k)$ vertices of $A$ and $y$ among the first $\min (|B|,k)$ of $B$. Each pair is charged at most once (at the merge happening at $\text{lca}(x,y)$, the only time they’re on different sides), and $y$ is less than $2k$ positions after $x$ in DFS order. So the total is at most $n\cdot 2k$. Without the cap the same argument charges each unordered pair once: $O(n^2)$.

Dependency knapsack (choose a set closed under “child chosen $\Rightarrow$ parent chosen” with total weight $\le W$) in $O(nW)$: in preorder, skipping vertex $v$ skips its whole subtree (a contiguous block of size ${\text{sub}}_v$).

// pre = preorder, sub = subtree sizes; g has n + 1 rows of W + 1 zeros
for (int i = n - 1; i >= 0; i--) {
    int v = pre[i];
    for (int w = 0; w <= W; w++) {
        g[i][w] = g[i + sub[v]][w];                                        // skip v and its subtree
        if (w >= wt[v]) g[i][w] = max(g[i][w], g[i + 1][w - wt[v]] + val[v]);   // take v, continue inside
    }
}
// answer g[0][W]; forests: add a virtual root of weight 0 and use capacity W, index from the virtual root's child
// weights must be nonnegative; to force the (virtual) root taken, read g[1][W - wt[root]] + val[root] instead of g[0][W]

Proof: the preorder recurrence enumerates exactly the closed sets

Process vertices in preorder and decide each one. If $v$ is not taken, no descendant may be taken, and its descendants are exactly the next ${\text{sub}}_v-1$ vertices in preorder, so jumping to $i+{\text{sub}}_v$ skips them all. If $v$ is taken, its children become available, and the next vertex in preorder is either its first child or (if it is a leaf) the next vertex outside its subtree, whose parent is an ancestor of $v$ that was taken (otherwise we would have jumped past $v$). By induction every state $i$ is reached only when all ancestors of ${\text{pre}}_i$ are taken, so the choices are exactly the closed sets.

Rerooting

Each vertex sends its neighbour a contribution summarising the component on its side. Let merge combine contributions (associative, with identity) and addRoot(x, v) turn the merged contributions of $v$‘s other neighbours into $v$‘s contribution. Pass 1 computes contributions towards the root; pass 2 computes, for each child, the merge of all other neighbours via prefix/suffix aggregates, so no inverse is needed.

template<class T, class M, class R>
vector<T> reroot(const vector<vector<int>>& adj, T id, M merge, R addRoot) {
    int n = sz(adj); vector<int> order{0}, par(n, -1);
    for (int i = 0; i < sz(order); i++) for (int v : adj[order[i]]) if (v != par[order[i]]) par[v] = order[i], order.push_back(v);
    vector<T> down(n, id), up(n, id), ans(n, id);          // down[u]: merge of children's contributions
    for (int i = n - 1; i >= 0; i--) { int u = order[i]; for (int v : adj[u]) if (v != par[u]) down[u] = merge(down[u], addRoot(down[v], v)); }
    for (int u : order) {                                    // up[v]: merge of u's neighbours except child v
        int k = sz(adj[u]); vector<T> c(k), suf(k + 1, id);
        for (int i = 0; i < k; i++) { int v = adj[u][i]; c[i] = v == par[u] ? addRoot(up[u], v) : addRoot(down[v], v); }
        for (int i = k - 1; i >= 0; i--) suf[i] = merge(c[i], suf[i + 1]);
        ans[u] = suf[0]; T pre = id;
        for (int i = 0; i < k; i++) { if (adj[u][i] != par[u]) up[adj[u][i]] = merge(pre, suf[i + 1]); pre = merge(pre, c[i]); }
    }
    return ans;                                              // merge of all neighbours' contributions, u as root
}
// sum of distances: T = pair(sum, cnt), merge = add, addRoot = [](T x, int) { return T{x.first + x.second + 1, x.second + 1}; }
// eccentricity:     T = int (id 0),     merge = max, addRoot = [](int x, int) { return x + 1; }

Proof: rerooting computes every root's answer

For an edge $(u,v)$ let $C(v\to u)$ be the contribution of the component containing $v$ after deleting the edge, rooted at $v$. By definition $C(v\to u)=\text{addRoot}({\text{merge}}_{w\in N(v)\setminus u}C(w\to v),v)$. Pass 1 computes $C(v\to {\text{par}}_v)$ for all $v$ bottom-up. In pass 2, processing $u$ top-down, $C({\text{par}}_u\to u)=\text{addRoot}({\text{up}}_u,{\text{par}}_u)$ is already known (it was set while processing ${\text{par}}_u$), so all contributions into $u$ are available; merging all of them except child $v$‘s (prefix before it, suffix after it, using associativity) is exactly the input needed for $C(u\to v)$. The answer at $u$ as a root is the merge over all neighbours. Each vertex costs $O(\mathrm{deg})$, total $O(n)$.

Shortcut: eccentricities on a tree are $\max (\text{dist}(v,a),\text{dist}(v,b))$ for diameter endpoints $a,b$ (Tree Basics).

When merge is specifically max (not a general associative op), the prefix/suffix machinery above can be skipped: keep just the two largest child values at each vertex, and “all neighbours except child $v$” is the largest of the two unless it came from $v$, in which case it’s the second-largest.

Other techniques on trees

• Small to large (merge the smaller map into the larger) for per-subtree sets: $O(n\log n)$ moves (Small to Large).
• Segment tree merging for per-subtree value-indexed arrays (Segment Tree Merging).
• Path DP (“count paths with property P”): centroid decomposition, or DP with $f_{u,d}$ combined at each vertex.
• DP over the Euler tour (dependency knapsack above, or “choose disjoint subtrees”).
• Dynamic DP when edge weights or vertex values change: write the transition as a $(\max ,+)$ matrix along heavy paths (Dynamic DP).