[SDOI2006]保安站岗————树形DP

题解：本题主要考查树形DP。 简要题意：在一棵点有点权的树上，选择一些点，这些点能将所有与它们相连的点覆盖，最终将整棵树上的点全部覆盖，试求最小代价 1.树形DP：本题很巧妙，有三种情况，所以设： $f[x][0]$为选择x点来覆盖x点 $f[x][1]$为x节点被儿子y覆盖 $f[x][2]$为x节点被父亲节点覆盖 易得选择x点来覆盖x点方程：$f[x][0]+=min(f[y][0],f[y][1],f[y][2]);$ x节点被父亲节点覆盖方程：$f[x][0]+=min(f[y][0],f[y][1])$ 关键在于x节点被儿子y覆盖的情况：如果儿子都是儿子的儿子选择了，那父亲怎么办，我们可以让儿子付出最小的代价，让一个儿子覆盖父亲就可以了 代码如下：

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; const int inf=1e9+7; struct Edge { int from,to; }p[66666]; int n,cnt,head[66666],val[666666]; int f[6666][4]; void add(int x,int y) { p[++cnt].from=head[x]; head[x]=cnt; p[cnt].to=y; } void dfs(int x,int fa) { f[x][0]=val[x]; int sum=0,minn=inf; for(int i=head[x];i;i=p[i].from) { int y=p[i].to; if(y==fa)continue; dfs(y,x); int t=min(f[y][0],f[y][1]); f[x][0]+=min(t,f[y][2]); f[x][2]+=t; if(f[y][0]<f[y][1])sum++; else minn=min(minn,f[y][0]-f[y][1]); f[x][1]+=t; } if(!sum)f[x][1]+=minn; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { int x,num,y; scanf("%d",&x); scanf("%d",&val[x]); scanf("%d",&num); for(int j=1;j<=num;j++) { scanf("%d",&y); add(x,y);add(y,x); } } dfs(1,0); printf("%d",min(f[1][0],f[1][1])); return 0; }