我是参考这一篇写的：http://blog.csdn.net/fsss_7/article/details/52049474
一点感想：dp[i][0]代表以这个点为根的且总叶子数为偶数个叶子的答案
考虑每条树边的贡献，贪心的想，肯定是每条树边出现的次数越少越好
由于树链肯定从一个叶子到另外一个叶子的，那么可以想到
1：考虑每条树边下面的子树，如果有奇数个节点，那么出来一条边就可以了，剩下的自己匹配就好
2：如果是偶数条边，出来两条就行了，如果多余两条不如两条更优，少于两条，不符合题意
dp[i][1]代表总点数为奇数时，以i为根的子树，包含一条链的最优答案
奇数比偶数实际上就多了，一条链，考虑包含这条链
贪心的想，这条链只要从一个叶子节点延伸到它的第一个祖先（且这个祖先的有大于一个儿子）就行了
dp[i][1]就是当前子树包含这条链的最优值，那么dp[root][1]就是奇数的答案，dp[root][0]就是偶数的答案
#include <cstdio> #include <cstring> #include <vector> #include <queue> #include <map> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int N=1e5+5; const int INF=0x3f3f3f3f; int T,n,head[N],tot; struct Edge{ int v,next; }edge[N<<1]; void add(int u,int v){ edge[tot].v=v; edge[tot].next=head[u]; head[u]=tot++; } int d[N],son[N],dp[N][2]; void dfs(int u,int f){ int child=0;son[u]=0;dp[u][0]=0; for(int i=head[u];~i;i=edge[i].next){ int v=edge[i].v;if(v==f)continue; dfs(v,u);++child;son[u]+=son[v]; dp[u][0]+=dp[v][0]; if(son[v]&1)++dp[u][0]; else dp[u][0]+=2; } for(int i=head[u];~i;i=edge[i].next){ int v=edge[i].v;if(v==f)continue; if(child>1&&son[v]==1) dp[u][1]=min(dp[u][1],dp[u][0]); if(dp[v][1]==INF)continue; int d = ((son[v] & 1) ? 1 : -1); dp[u][1] = min(dp[u][1], dp[u][0] - dp[v][0] + dp[v][1] + d); } if(!child)son[u]=1; } int main(){ scanf("%d",&T); while(T--){ scanf("%d",&n);tot=0; memset(head,-1,sizeof(head)); memset(dp,INF,sizeof(dp)); memset(d,0,sizeof(d)); for(int i=1;i<n;++i){ int u,v;scanf("%d %d",&u,&v); add(u,v);add(v,u);++d[u];++d[v]; } if(n==2){printf("1 ");continue;} int cnt=0,root; for(int i=1;i<=n;++i) if(d[i]!=1)root=i; else ++cnt; dfs(root,0); if(cnt&1)printf("%d ",dp[root][1]); else printf("%d ",dp[root][0]); } return 0; }