题意：一棵树，进行染色，，每个没染色的节点恰好和一个染色的节点相连，求染色的节点最少的个数X（以下均以X代表子问题的解）
思路：树形DP，细化状态，从而对每个节点的每种状态互相递推
这里如何细化状态是难点，而且也是这类难题的共同问题
很容易知道每个节点i至少两个状态：dp[i][0]: i没染上色时以i的子树的X。dp[i][1]: i被染色以i为子树的X
但是仅仅这两个状态无法实现状态转移因为：
dp[u][0]=sum(dp[v][0],dp[v][1])+1 (dp[u][0]可以找到状态转移关系，dp[u][0]和u的父亲没关系)
但是dp[u][1]不仅仅与u的儿子有关系，也和u的父亲有关系，比如当他的父亲染了色，u的儿子必须全没染色，当u的父亲没染色，那么u的儿子必须有一个染了色
所以再添加一个状态来表示父亲的情况：dp[u][2],表示u和u的父亲都没染色，dp[u][1]改成u没染色但u的父亲染了色
这样递推关系就可以写出来了。
所以这类树形dp，要学会适当的添加状态，如何细化状态
//AcceptedC++0.0162015-03-14 12:41:27#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#include<vector>using namespace std;const int N= 1e4+1e2;const int inf = 0x3f3f3f3f;int n,op;struct Edge{int v;Edge(int _v=0) : v(_v) {};};int dep[N]; //每个节点的深度int fa[N]; //每个节点的父亲节点int mdep;int dp[N][3]; //每个节点为根的子树三个状态互相递推vector<Edge> es[N];void dfs(int u,int pa){fa[u]=pa;if(u==1) dep[u]=0;else dep[u]=dep[pa]+1;mdep=max(mdep,dep[u]);for(int i=0;i<es[u].size();i++){int v=es[u][i].v;if(v==pa) continue;dfs(v,u);}}void ini(){for(int i=1;i<=n;i++) es[i].clear();mdep=-1;memset(dp,0,sizeof(dp));}void debug(){printf("mdep=%d\n",mdep);printf("\n0:");for(int i=1;i<=n;i++) printf("%11d",dp[i][0]);printf("\n1:");for(int i=1;i<=n;i++) printf("%11d",dp[i][1]);printf("\n2:");for(int i=1;i<=n;i++) printf("%11d",dp[i][2]);puts("");}int main(){while(scanf("%d",&n),~op){ini();int u,v;for(int i=1;i<n;i++){scanf("%d%d",&u,&v);es[u].push_back(Edge(v));es[v].push_back(Edge(u));}scanf("%d",&op);dfs(1,0);for(int l=mdep;l>=0;l–)for(int u=1;u<=n;u++)if(dep[u]==l){int sum1=0,sum2=0;int sz=es[u].size();for(int j=0;j<sz;j++){int v=es[u][j].v;if(v==fa[u]) continue;sum1+=min(dp[v][0],dp[v][1]);if(sum1>inf) sum1=inf; //防止爆intsum2+=dp[v][2];if(sum2>inf ) sum2=inf;}dp[u][0]=sum1+1;dp[u][1]=sum2;for(int j=0;j<sz;j++){int v=es[u][j].v;if(v==fa[u]) continue;else {dp[u][2]=inf;dp[u][2]=min(dp[u][2],dp[u][1]-dp[v][2]+dp[v][0]);}}if(sz==1&&u!=1) dp[u][2]=inf; //叶节点的一个边界，所以要判根}printf("%d\n",min(dp[1][0],dp[1][2]));// debug();}return 0;}
与那些新人和旧人们共同经历吧！
