[文章目录]
Description
一棵树；某些宫殿间可以互相望见，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。帮助xuzhenyi布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。
树形DP，我的天啊，这道题不知道为什么调了好久才AC，最小支配集+点权。
首先有三个状态：
self[x]表示点x自己支配自己时子树的最优解
none[x]表示x未被支配时，子树的最优解（后改成未知点x是否被支配的最优解）
son[x]表示x被自己的儿子支配时的最优
方程：x为y的fa
self[x]+=min(self[y],none[y],son[y]);
none[x]+=min(self[y],son[y]);(这样就防止了数据溢出，因为光是son的话有可能所有的son都是极大值，也就是所有的son都是叶子结点)
son[x]=min(之前最优none[x]+selfy,son[x]+min(son[y],self[y]));
记得要初始化0x3f,然后记得self+=val；
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,t,a,b;
int h[1600],to[3100],nxt[3100],cnt;
int none[1600],self[1600],son[1600];
void add(int x,int y)
{
to[++cnt]=y;
nxt[cnt]=h[x];
h[x]=cnt;
}
void dfs(int x,int pre)
{
none[x]=0;
for(int i=h[x];i;i=nxt[i])
{
if(to[i]==pre) continue;
dfs(to[i],x);
son[x]=min(none[x]+self[to[i]],son[x]+min(self[to[i]],son[to[i]]) );
self[x]+=min(none[to[i]],min(self[to[i]],son[to[i]]) );
none[x]+=min(son[to[i]],self[to[i]]);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&b);
scanf("%d",&self[b]);
scanf("%d",&t);
for(int j=1;j<=t;j++)
{
scanf("%d",&a);
add(b,a);
add(a,b);
}
}
for(int i=1;i<=n;i++)
son[i]=none[i]=0x3f3f3f3f;
dfs(1,0);
printf("%d",min(self[1],son[1]));
return 0;
}