树形dp之最小支配集（树形dp模板）

题目： CellPhoneNetwork

最小支配集：一个点可以覆盖其周围所有的点包括自己 f[i][0]被其儿子覆盖 f[i][1]被自己覆盖 f[i][2]被其父亲覆盖 设j为i的儿子 f[i][0]= min(f[j][0],f[j][1])+tmp; //tmp表示维护至少有一个儿子覆盖的最小差值 f[i][1]= min(f[j][0],f[j][1],f[j][2])+1; f[i][2]= min(f[j][0],f[j][1]); 注意：根没有父亲，所以不能被父亲覆盖

#include<bits/stdc++.h>
using namespace std;
int const INF=0x3f3f3f3f;
int const N=1e4+7;
int n,cnt;
int head[N];
struct node{
	int a,next,len;
}edge[N<<1];
void add(int x,int y,int len){
	edge[++cnt].a =y;
	edge[cnt].len =len;
	edge[cnt].next =head[x];
	head[x]=cnt;
}
int f[N][3],vis[N],ans;
void dfs(int x){
	f[x][0]=0;f[x][1]=1;f[x][2]=0;
	vis[x]=1;
	int tmp=INF;
	for(int i=head[x];i!=-1;i=edge[i].next){
		int u=edge[i].a;
		if(vis[u]) continue;
		vis[u]=1;
		dfs(u);
		f[x][1]+=min(f[u][0],min(f[u][1],f[u][2]));
		f[x][2]+=min(f[u][0],f[u][1]);
		if(f[u][1]<=f[u][0]){
			tmp=0;
			f[x][0]+=f[u][1];
		}
		else{
			f[x][0]+=f[u][0];
			tmp=min(tmp,f[u][1]-f[u][0]);
		}
	}
	f[x][0]+=tmp;
}
int main(){
	cin >> n;
	memset(head,-1,sizeof(head));
	for(int i=1;i<=n;++i){
		int a,b;
		cin >> a >> b;
		add(a,b,1);add(b,a,1);
	}
	dfs(1);
	ans=min(f[1][0],f[1][1]);  //根不能被其父亲覆盖
	cout << ans << endl;
	return 0;
}