给出N个点，和N-1个边关系，可以对点进行涂色，涂色后该点和其相连的点都被染色，问染色最少的点将所有点全部覆盖
dp[cur][0]+=Min(dp[next][2],dp[next][1]); 父节点被涂色，当前节点不涂
dp[cur][2]+=Min(dp[next][2],dp[next][1]);当前节点被涂色
dp[cur][1]+=Min(dp[next][0],dp[next][1],dp[next][2]); 子节点存在至少一个被涂色，，当前节点不涂
对dp[cur][1]时注意如果所有的dp[next][1][<dp[next][2]时，即所有的子节点都没被直接覆盖，
需要+Min(dp[next][1]-dp[next][2]);
#include "stdio.h"#include "string.h"#include "vector"using namespace std;const int inf=0x7fffffff;struct node{int fa;vector<int>child;}data[10010];int dp[10010][3];int Min(int a,int b){if (a<b) return a;else return b;}void dfs(int cur,int last){int flag,mark,next,i;if (data[cur].child.size()==1 && last!=0){dp[cur][0]=0;dp[cur][1]=1;dp[cur][2]=inf;return ;}flag=1;mark=inf;for (i=0;i<data[cur].child.size();i++){next=data[cur].child[i];if (next==last) continue;dfs(next,cur);dp[cur][0]+=Min(dp[next][1],dp[next][2]);dp[cur][1]+=Min(Min(dp[next][0],dp[next][1]),dp[next][2]);if(dp[next][1]<=dp[next][2]){dp[cur][2]+=dp[next][1];flag=0;}else{dp[cur][2]+=dp[next][2];mark=Min(dp[next][1]-dp[next][2],mark);}}dp[cur][1]++;if(flag==1)dp[cur][2]+=mark;}int main(){int n,a,b,i;while (scanf("%d",&n)!=EOF){for (i=1;i<n;i++){scanf("%d%d",&a,&b);data[a].child.push_back(b);data[b].child.push_back(a);}dfs(1,0);if (n!=1)printf("%d\n",Min(dp[1][1],dp[1][2]));elseprintf("1\n");}return 0;}
却不去主动改变，而是放任它的生活态度。
