题意:给一颗树,从树上找一个点集D,任意从树上选择一点,要么这个点属于点集D,要么这个点的邻居有且仅有一个点属于点集D。

看错题了。以为是最小支配集。因为看少一个条件:不在点集D中的点的邻居有且仅有一个点属于D。
dp[i][j]dp[i][j]为点i在j状态时所要的染色最少点数。
dp[i][0]dp[i][0]为将点i染为黑色
dp[i][1]dp[i][1]为将点i染为白色,儿子为白色
dp[i][2]dp[i][2]为将点i染为白色,儿子有且仅有一黑色
那么有转移式子
dp[u][1]+=min(dp[v][0],dp[v][1])dp[u][1]+=min(dp[v][0],dp[v][1]) vvuu的儿子
dp[u][0]+=dp[v][2]dp[u][0]+=dp[v][2] vvuu的儿子
dp[u][2]=vmin(dp[v][1]+v!=vdp[v][2])dp[u][2]=\sum_{v}min(dp[v][1]+\sum_{v'!=v}dp[v'][2]) vvvv'都为u的儿子

代码:

//author: CHC
//First Edit Time: 2015-09-23 20:03
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=1e+4;
const int MAXM=1e+5;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
struct Edge {
int to,next;
Edge(){}
Edge(int _to,int _next):to(_to),next(_next){}
}e[MAXN*2];
int head[MAXN],tot;
void init(){
memset(head,-1,sizeof(head));
tot=0;
}
void AddEdge(int u,int v){
e[tot]=Edge(v,head[u]);
head[u]=tot++;
e[tot]=Edge(u,head[v]);
head[v]=tot++;
}
int dp[MAXN][3];
void dfs(int u,int father){
dp[u][1]=1;dp[u][0]=dp[u][2]=0;
int ss=0;
for(int i=head[u];~i;i=e[i].next){
int v=e[i].to;
if(v!=father){
dfs(v,u);
dp[u][1]+=min(dp[v][0],dp[v][1]);
dp[u][0]+=dp[v][2];
ss+=dp[v][2];
}
}
int sst=100000;
for(int i=head[u];~i;i=e[i].next){
int v=e[i].to;
if(v!=father){
sst=min(sst,dp[v][1]+ss-dp[v][2]);
}
}
//if(sst==INF)sst=0;
dp[u][2]=sst;
//printf("%d: ",u);
//printf("%d %d %d\n",dp[u][0],dp[u][1],dp[u][2]);
}
int main()
{
int m;
while(~scanf("%d",&m)){
if(!m)break;
init();
for(int i=0,x,y;i<m;i++){
scanf("%d%d",&x,&y);
AddEdge(x,y);
}
dfs(1,1);
printf("%d\n",min(dp[1][1],dp[1][2]));
}
return 0;
}