Core Logic and Mathematical Principles
Tree Dynamic Programming (Tree DP) is an algorithmic model that establishes the progression of dynamic programming stages on a tree topology (a directed acyclic graph). Its essence lies in the natural topological order of post-order traversal (DFS), enabling the linear energy transfer of states from child nodes to parent nodes.
1. Geometric Specialization of Topological Order
In linear DP, stages progress orderly along a one-dimensional axis (as indicated by the subscript $i$). In a tree structure, the optimal decision of a parent node $u$ depends on the fixed states of all its child nodes $v \\in ext{son}(u)$. Since trees are acyclic, we can collect child node information through a single Depth-First Search (DFS) during the recursive backtrack (i.e., at the post-order traversal position). At this point, the lifecycle of the child nodes has ended, and their states are optimal, perfectly satisfying the no post-order property.
2. The Bossless Ball (Classic Maximum Independent Set Model)
Given a tree with parent-child relationships, each node has a happiness value. We need to select a subset of nodes such that no two connected nodes (i.e., parent-child relationships) can be selected simultaneously. The goal is to find the maximum sum of happiness values of this subset.
-
Discretization of Decision Conflicts: For any node $u$, there are only two core decisions:
- Select $u$: Once $u$ is selected, all its direct child nodes $v$ absolutely cannot be selected.
- Do not select $u$: If $u$ is not selected, its child nodes $v$ are free from the constraints of their parent, and they can be either selected or not (select whichever branch yields the greatest benefit).
-
Dimensional Analysis of States: By introducing a two-dimensional state $f[u][0/1]$, we decouple the complex global exclusion conflicts into local parent-child node interactions, thus compressing the exponential search space to a linear grid of $O(N)$.
State Design and Algorithm Derivation
1. State Space Definition
Let $f[u][0]$ represent the maximum happiness value obtainable when not selecting node $u$ in the subtree rooted at $u$. Let $f[u][1]$ represent the maximum happiness value obtainable when selecting node $u$ in the subtree rooted at $u$.
2. Derivation of State Transition Equations
For node $u$, let its child node set be $ ext{son}(u)$, and the original happiness value of the current node be $R[u]$:
- When selecting node $u$: All child nodes $v$ are forced to be disqualified from being selected and can only transition from the state of not selecting $v$.
$$f[u][1] = R[u] + \sum_{v \\in \text{son}(u)} f[v][0]$$
- When not selecting node $u$: Each child node $v$ can freely choose to be either selected or not, adopting a globally optimal strategy to maximize the total sum.
$$f[u][0] = \sum_{v \\in \text{son}(u)} \max(f[v][0], f[v][1])$$
3. Boundary Conditions
When $u$ is a leaf node ($ ext{son}(u) = \emptyset$):
$$f[u][0] = 0, \quad f[u][1] = R[u]$$
This boundary condition is naturally activated when the DFS backtrack reaches the leaf nodes.
C++ Standard Source Code (NOIP Style)
The following code is the standard implementation for the "Bossless Ball" exam case. It uses a high-performance adjacency list (std::vector) to construct the tree, strictly adhering to the Linux g++ -O2 compilation standard.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 6005;
int r[MAXN]; // Store the happiness value of each node
int f[MAXN][2]; // f[u][0]: do not select u, f[u][1]: select u
bool has_parent[MAXN];// Mark whether there is a parent, used to find the root of the tree
vector<int> tree[MAXN];// Adjacency list to build the tree
// Core of Tree DP: Use DFS backtracking to achieve bottom-up state transitions
void dfs(int u) {
// 1. Initialize the basic state of leaf nodes
f[u][0] = 0;
f[u][1] = r[u];
// 2. Propagate down the topology
for (int v : tree[u]) {
dfs(v); // First, let child nodes calculate their own subtree states
// 3. Update the parent node using child node states during backtracking (contribution from bottom to top)
f[u][1] += f[v][0]; // If u is selected, child node v cannot be selected
f[u][0] += max(f[v][0], f[v][1]); // If u is not selected, child node v can choose the maximum
}
}
int main() {
// Optimize I/O performance
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
if (!(cin >> n)) return 0;
for (int i = 1; i <= n; ++i) {
cin >> r[i];
}
// Read relationships and build directed tree (from parent to child)
for (int i = 1; i < n; ++i) {
int l, k; // l is a direct subordinate of k (l is child, k is parent)
cin >> l >> k;
tree[k].push_back(l);
has_parent[l] = true; // Mark that l has a parent
}
// Find the geometric root of the entire tree (the node without a parent is the root)
int root = 1;
while (has_parent[root]) {
root++;
}
// Start the DFS state network intertwining from the root node
dfs(root);
// The global optimal solution must arise from the two terminal states of "selecting root" and "not selecting root"
cout << max(f[root][0], f[root][1]) << "\n";
return 0;
}NOIP Practical Pitfall Guide
1. Undirected Graph Tree Construction Leading to Infinite Loop and Stack Overflow
- Phenomenon: Some problems provide undirected tree edges (e.g., $u$ connected to $v$, without specifying who is the parent). If contestants directly add bidirectional edges
tree[u].push_back(v); tree[v].push_back(u);and writefor(int v : tree[u]) dfs(v);in DFS, it will cause DFS to jump back and forth between parent and child nodes, instantly triggering segmentation fault / stack overflow. - Avoidance Method: When constructing trees from undirected edges, the DFS function must take an additional parameter to record the current node's parent:
void dfs(int u, int fa). In the loop for traversing child nodes, a safety sentinel must be enforced:if (v == fa) continue;.
2. Incorrect Root Node Localization
- Phenomenon: Assuming node $1$ is the root of the entire tree and directly calling
dfs(1). This can be fatal in many problems because the node numbering is random, and node $1$ is likely just a leaf node at the end. Starting the search from it not only misses large portions of the subtree but also leads to contradictory state logic. - Avoidance Method: Utilize an in-degree array or boolean marking array
has_parentto record the dependency of each node. After reading all edges, it is essential to forcefully traverse once to find the node with "in-degree 0 / no parent" as the true starting point for DFS.
Classic NOIP/Luogu Problems
1. Luogu P1352 Bossless Ball
- Problem Description: This is the textbook model detailed above.
- Essence of the Problem and Solution Approach: A standard tree maximum independent set problem. The core lies in the decoupled design of the two-dimensional state $f[u][0/1]$. A single DFS with $O(N)$ complexity can perfectly conclude the solution.
2. Luogu P2015 Binary Apple Tree
- Problem Description: There is a binary apple tree, with several apples on each branch. Due to cleaning requirements, some branches must be cut off, leaving exactly $Q$ branches. It is known that the root of the tree cannot be cut off. The goal is to maximize the number of apples retained while keeping $Q$ branches.
- Essence of the Problem and Solution Approach: A tree knapsack (tree with weight-dependent knapsack) model.
- State Design: Let $f[u][j]$ represent the maximum number of apples obtainable in the subtree rooted at $u$ while retaining $j$ branches.
- Core Idea: During the DFS backtrack, the capacity $j$ of the parent node $u$ needs to be allocated to the left and right subtrees. For child node $v$, if it is allocated $k$ branches, since the branch connecting $u$ and $v$ must be retained (consuming 1 capacity), the actual available capacity for $v$'s subtree is $k-1$. By nesting a layer of capacity enumeration similar to grouped knapsack within the parent node:
$$f[u][j] = \max_{v \\in \text{son}(u)} \{ f[u][j - k] + f[v][k - 1] + \text{apple}(u, v) \}$$
This model perfectly integrates tree structure with dynamic programming capacity knapsack.