【例 5】皇宫看守（信息学奥赛一本通- P1579）-育师

在前面，我们做了《战略游戏》（树上的最小点覆盖）。那道题要求我们在节点放士兵，看守住所有的边。

今天我们要面对的是它的进化版——经典题《皇宫看守》。这道题要求我们在节点安排侍卫，看守住所有的点（一个侍卫可以看守自己、看守儿子、看守父亲）。在图论中，这被称为“树上的最小支配集”。

很多同学一上来，习惯性地沿用看守边的2个状态（放/不放），结果写到一半写不下去了。今天我们就用“状态机”的视角，彻底拆解这道题。

1. 题目背景与模型抽象

题目重述：有一棵树形的皇宫道路，要在宫殿（节点）安排侍卫。

在不同的宫殿安排侍卫，所需的经费不同。
一个宫殿如果有侍卫，那么它自己、它的所有子节点、它的父节点都会被看守住。
目标：在看守全部宫殿的前提下，求最少花费的经费。

模型抽象：相比于看守边（只管两头），看守点的保护范围更广。节点x如果自己不放侍卫，它的安全来源有两种截然不同的途径：靠父亲或者靠儿子。这两条路径对子树状态的约束完全不同，因此2个状态不够用，必须引入第 3 个状态。

2. 状态定义与“灵魂”初始化

这是本题的难点！我们切换到第一人称视角，问自己：“谁来保护我？”

状态定义

定义 dp[u][j]：表示以 u 为根的子树中，达到合法看守状态所需的最小经费。

dp[x][0]：自己放。花费经费，绝对安全，且顺便保护了全家。
dp[x][1]：靠儿子。自己不放，但所有儿子中至少有一个放了侍卫。
dp[x][2]：靠父亲。自己不放，儿子也全都不放，只能把“安全债务”甩给未来的父亲。

核心避坑：不能用memset全局初始化

在之前的“树上背包”中，我们习惯用memset(dp,0x3f,sizeof(dp))去淘汰幽灵体积。但在这道状态机DP中，不能这么写。因为状态机的每一个起步动作（自己放花经费，靠别人花 0 元）都是天生合法的。如果全局铺满无穷大，一做+=累加就会溢出报错！正确的做法是：保持默认 0 起步，只在遇到非法的“死胡同”时进行精准淘汰。

3. 状态转移方程（齿轮的严密咬合）

利用后序遍历（DFS自底向上），假设正在计算父亲x，且遍历到了儿子v：

x选择“自己放” (dp[x][0])既然x已经掏钱了，儿子v怎么选都行。儿子可以自己放、靠孙子，甚至舒服地白嫖父亲x。
dp[x][0]+=min(dp[v][0],min(dp[v][1],dp[v][2]))
x选择“靠父亲” (dp[x][2])x自己没有选，儿子v绝不能再选 2（靠父亲），只能靠自己或靠孙子。
dp[x][2]+=min(dp[v][0],dp[v][1])
x选择“靠儿子” (dp[x][1]) —— 最复杂的一步！儿子依然只能在0和1中选，但必须保证至少有一个儿子选了0（亲自放了侍卫）。
- 如果有儿子主动选了0，直接累加。
- 如果所有儿子都自私地选了1（没人放侍卫），我们必须强行逼迫其中一个额外代价最小的儿子选0。所以在循环时要记录最小差值dif=dp[v][0]-dp[v][1]以备兜底。

4. 完整代码

以下是满分代码结构，特别注意main函数最后的输出细节：

#include <iostream> #include <cstring>//对应memset #include <algorithm>//对应min max using namespace std; int n; int k[1510];//k[i]代表在i处安置侍卫所需的经费 int din[1510];//每个节点的入度 用于找根节点 int h[1510]; int vtex[1510]; int nxt[1510]; int idx; //dp[i][0]代表i号宫殿放侍卫，自己看守自己 i号团队最小花费经费 //dp[i][1]代表i号宫殿不放置侍卫，i儿子至少一个放置侍卫 i儿子看守i i号团队最小花费经费 //dp[i][2]代表i号宫殿不放置侍卫，i父亲放置侍卫 i父亲看守i i号团队最小花费经费 int dp[1510][3]; void addedge(int u,int v){ vtex[idx]=v; nxt[idx]=h[u]; h[u]=idx++; } void dfs(int x){ dp[x][0]=k[x];//初始化每个宫殿如果自己放置侍卫的经费 int p=h[x]; bool flag=0;//用于记录dp[x][1]情况下，是否有子节点已放置侍卫 //用于记录dp[x][1]且无子节点已放置侍卫情况下，dp[v][1]与dp[v][0]的最小差值 //最后将这个差值补给dp[x][1]（强行逼迫一个子节点放侍卫的最小代价差值） int dif=0x3f3f3f3f; while(p!=-1){//遍历x的所有子节点 int v=vtex[p]; dfs(v); //当x放置侍卫时，x的子节点可以放置也可以不放置 dp[x][0]+=min(dp[v][0],min(dp[v][1],dp[v][2])); //当x不放置侍卫，x的父节点放置侍卫时 dp[x][2]+=min(dp[v][0],dp[v][1]); //当x不放置侍卫，x的子节点至少一个放置侍卫时(最复杂一步) //如果x子节点自己覆盖自己比子节点的儿子覆盖子节点经费小，直接就可以达成了 //但如果所有x子节点覆盖自己都比子节点的儿子覆盖子节点经费大，就要选一个子节点 //让其自己覆盖自己，为了经费最少，我们要选差值最小的 if(dp[v][0]<=dp[v][1]){ dp[x][1]+=dp[v][0]; flag=1;//标记已经有子节点放置了侍卫 } else{ dp[x][1]+=dp[v][1]; dif=min(dif,dp[v][0]-dp[v][1]);//记录最小差值备用 } p=nxt[p]; } //如果所有子节点都没放侍卫，强行加上最小差值 //如果x是叶子节点(无子)，无穷大dif会加给dp[x][1]，从而淘汰荒谬状态 if(flag==0) dp[x][1]+=dif; } int main(){ cin>>n; //初始化头指针数组为空 memset(h,-1,sizeof(h)); //存图 for(int i=1;i<=n;i++){//共有n个宫殿 int u;//宫殿结点编号 cin>>u; cin>>k[u];//在该宫殿安置侍卫所需的经费 k int m;//该边的儿子数m cin>>m; while(m--){ int r;//子节点编号 cin>>r; din[r]++; addedge(u,r); } } //memset(dp,0x3f,sizeof(dp));//因为要求经费最小值，所以初始化dp数组为无穷大 for(int i=1;i<=n;i++){ if(din[i]==0){ dfs(i); //根节点绝不能选 dp[i][2] //根节点是整棵树的最高领导人，它没有父亲 //如果它向虚无的未来打了一张“靠父亲”的安全欠条，这笔死账会导致全盘崩溃 //即不能写成min(dp[i][0],min(dp[i][1],dp[i][2])) cout<<min(dp[i][0],dp[i][1]); break; } } return 0; }