High-Dimensional Mapping Techniques in Tree Dynamic Programming

Core Logic and Mathematical Principles

The basic model of Tree Dynamic Programming (Tree DP) usually focuses only on the convergence of states within subtrees (e.g., bottom-up). However, high-difficulty problems in contests often introduce full-source topological interactions or local connectivity block constraints.

To overcome the highest threshold of Tree DP, one must thoroughly master the following two core high-dimensional mapping techniques:

1. Multi-state Interleaving: When the problem constraints are no longer simply "select or not select" (e.g., at a ball without a supervisor), but rather involve multi-level transmission chains (for example: a node is covered by security, which can be because it has surveillance installed, or its parent does, or one of its children does). This multi-directional dependency can cause traditional two-dimensional states to collapse completely. We must establish a fully complete state set and create cross-dimensional grid interleaving between parent and child nodes.
2. Re-rooting Context Isolation: In Section 16.3's re-rooting method, we encountered the transfer of full-source information. However, in more complex scenarios (such as finding the second largest value of Hamming distance on a tree or when the transfer equation includes non-invertible operators), the simple differential logic of "global - subtree = external" fails. At this point, it is necessary to maintain prefix and suffix value grids for all direct child nodes of the parent during the first scan, so that when re-rooting downwards, we can extract the aggregate contributions of "all other sibling subtrees except the current child subtree" without loss.

State Design and Algorithm Derivation

Taking the classic "Minimum Dominating Set of Trees" as an example (i.e., selecting the minimum number of nodes to color black so that all nodes in the tree are either colored black themselves or adjacent to at least one black node).

1. Fully Complete State Space Design

For any node $u$, to ensure that the subtree rooted at $u$ is fully covered legally and meets topological transmission, its own state can have only the following 3 completely complete physical semantics:

• $f[u][0]$: Node $u$ is colored black. At this point, it does not matter whether its child node $v$ is covered; the state can switch arbitrarily.
• $f[u][1]$: Node $u$ is not colored black but is covered by one of its direct child nodes $v$. This means at least one of $u$'s child nodes must choose state 0.
• $f[u][2]$: Node $u$ is not colored black and is not covered by child nodes, and must wait for its parent node to be colored black to cover it. This means all child nodes of $u$ must have already been legally covered, and they are not obligated to contribute upwards (i.e., child nodes cannot be in state 2).

2. Geometric Interleaving of State Transition Equations

For the parent node $u$ and its child node set $ ext{son}(u)$:

• State 0 (itself colored black): Since $u$ is already independent, child node $v$ can choose the minimum cost from three states.

$$f[u][0] = 1 + \sum_{v \in \text{son}(u)} \min(f[v][0], f[v][1], f[v][2])$$

• State 2 (waiting for parent to cover): Since $u$ is not colored black and its children do not help it, all child nodes $v$ must stand firm. Since $u$ is not colored black, child node $v$ cannot be in state 2 (otherwise, $v$ would be in an uncovered vacuum).

$$f[u][2] = \sum_{v \in \text{son}(u)} \min(f[v][0], f[v][1])$$

• State 1 (covered by children, critical deduction point): $u$ is not colored black, and all child nodes $v$ must first choose at least one from state 0 and state 1: $\sum \min(f[v][0], f[v][1])$. However, there is a hidden core vulnerability: What if all child nodes lean towards state 1 when seeking $\min$? If all choose state 1, it means no child is colored black, and the parent node $u$ will fall into an illegal state of being uncovered. Therefore, we must forcibly select one child $v'$ to change to state 0. To minimize the total cost increase, we need to enumerate which child changing to state 0 brings the smallest "compensatory cost":

$$f[u][1] = \sum_{v \in \text{son}(u)} \min(f[v][0], f[v][1]) + \Delta_{min}$$

Where $\Delta_{min} = \min_{v \in \text{son}(u)} \{ f[v][0] - \min(f[v][0], f[v][1]) \}$. If there is already a child selected state 0 in the original combination, then $\Delta_{min} = 0$.

C++ Standard Source Code (NOIP Style)

The following code is a standard industrial implementation of the Minimum Dominating Set of Trees, perfectly demonstrating the fine control of multi-state network interaction in contests.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100005;
const int INF = 0x3f3f3f3f;

vector<int> edge[MAXN];
int f[MAXN][3]; 
// f[u][0]: u black
// f[u][1]: u white, covered by children black
// f[u][2]: u white, covered by parent black

void dfs(int u, int fa) {
    f[u][0] = 1; // Initial cost for being colored black is 1
    f[u][2] = 0; // Current local initialization cost for waiting for parent to cover is 0

    int sum_1_0 = 0;
    int min_gap = INF;
    bool has_zero = false; // Record whether any child has spontaneously chosen state 0

    // Sentinel flag to check if it is a leaf node
    bool is_leaf = true;

    for (int v : edge[u]) {
        if (v == fa) continue;
        is_leaf = false;

        dfs(v, u); // Topological sinking

        // 1. Update f[u][0]
        f[u][0] += min({f[v][0], f[v][1], f[v][2]});

        // 2. Update f[u][2]
        f[u][2] += min(f[v][0], f[v][1]);

        // 3. Collect baseline sum for f[u][1] and calculate the gap
        int best_sub = min(f[v][0], f[v][1]);
        sum_1_0 += best_sub;

        if (f[v][0] <= f[v][1]) {
            has_zero = true;
        }
        min_gap = min(min_gap, f[v][0] - best_sub);
    }

    // Edge case for leaf nodes: assign physical extreme values
    if (is_leaf) {
        f[u][0] = 1;
        f[u][1] = INF; // Leaf has no children, cannot rely on children to cover, assign infinity
        f[u][2] = 0;   // Waiting for parent to cover is legitimate
        return;
    }

    // 4. Fine-tune the combination of f[u][1] state
    if (has_zero) {
        f[u][1] = sum_1_0; // Already has a child selected 0, no need to force a compensatory cost
    } else {
        f[u][1] = sum_1_0 + min_gap; // Forcibly pull the child with the smallest cost increase to state 0
    }
}

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

    int n;
    if (!(cin >> n)) return 0;

    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }

    dfs(1, 0);

    // The root node has no parent, so the global optimal solution can only be found in state 0 and state 1
    cout << min(f[1][0], f[1][1]) << "\n";

    return 0;
}

NOIP Practical Pitfall Guide

1. Ignoring Special Boundary State Assignments for Leaf Nodes

• Phenomenon: Contestants in multi-state Tree DP often overlook the special nature of leaf nodes. For example, in the above model, if we do not give the leaf node the special case f[u][1] = INF, the leaf node will retain the default value of 0 because it does not enter the child loop. This creates the absurd state where "the leaf node covers itself by relying on non-existent children and has a cost of 0", which can severely pollute the entire tree during upward transitions.
• Avoidance Strategy: After enumerating the child subtree loop in the DFS, must conduct a second review of the physical semantics for the is_leaf state to forcefully correct boundary values that do not meet reality.

2. Unhandled INF in Gap Calculation Leading to Data Overflow

• Phenomenon: When calculating the compensatory cost for $f[u][1]$, if some subtree's f[v][0] is already INF (due to some constraints leading to invalid), directly executing f[v][0] - best_sub will lead to INF - best_sub still being a large value. If indiscriminately added to the total, it will trigger integer underflow (turning negative).
• Avoidance Strategy: When performing large-scale state transfers or gap calculations, if the predecessor state contains INF, it should be forcibly intercepted by if statements and not participate in differential calculations.

Classic NOIP/Luogu Problems

1. Luogu P2899 [USACO08JAN] Cell Phone Network G

• Problem Description: Given a tree with $N$ nodes, establish base stations at some nodes. A base station can cover itself and all directly connected adjacent nodes. Find the minimum number of base stations needed to cover the entire tree. $N \le 10000$.
• Core Problem Essence and Solution Idea: Standard Minimum Dominating Set problem on trees.
• Core Idea: Completely equivalent to the above-derived 3-state model. Utilize a two-dimensional array f[u][0/1/2] for state topological interleaving, completing calculations in a single DFS.

2. Luogu P2458 [SDOI2006] Security Station Assignment

• Problem Description: A tree has $N$ towns, and establishing a security station at each town incurs a certain cost $W_i$. Each security station can only protect the streets and towns directly connected to it. Find the design scheme with the minimum cost.
• Core Problem Essence and Solution Idea: Weighted Minimum Dominating Set of Trees.
• Core Idea: The only difference from the previous problem is that the base cost of state 0 is no longer uniform 1, but rather each node's independent weight W[u].
• State Modification:

$$f[u][0] = W[u] + \sum \min(f[v][0], f[v][1], f[v][2])$$

The decision flow for relying on children and relying on parents remains identical, and the gap logic is completely consistent. This problem maps discrete counting losslessly to a continuous cost grid, making it a classic high-frequency problem for selection and NOIP advanced groups.