题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5758
题意:给你一颗树，树上有n个节点，有n-1条路，让你每条路至少走一遍，在走的过程中，你可以从一节点跳到其他任意节点，但不能重复走刚走过的路（也就是如果从a到b，那么此时不能立即从b走到a），让你找出在跳的次数最少的情况下走的最少步数。
题解：这是一个最小链覆盖问题。显然知道当走到叶子结点（也就是该节点没有子节点）时，这种情况是必须跳的。此时就应该跳到没有走到过的节点，但有由于需要考虑跳的次数要最少，那么我们知道在走如果以叶子结点为终点，此时跳的次数一定会增加（除非这是最后一次）。所以跳的时候一般从一个叶子结点跳到另外一个叶子结点。那么我们再来考虑走的步数最小化问题。根据以上分析，显然可以知道，为了首先保证跳的次数最少，那么每一次走一定是从一个叶子结点走到另外一个叶子结点，然后下一次又从另外一个没到过的叶子结点开始。因此，我们可以知道，对于一个节点的叶子结点来说，叶子结点个数的奇偶性决定了跳的次数。
点。
如图：
叶子结点为奇数时，首先从外面经过a节点后会走到b、c、d任意一个节点，那么剩下两个节点就可以从某一个开始走到另一个节点，比如从外面进来走到了b，那么下一步我们就可以从c走到d。
叶子结点为偶数时，同样进来先到某一个节点，那么剩下了奇数个叶子结点，肯定会多出一个向外走出去的（如果其他节点的叶子结点还没走完）。
根据以上分析，我们确定了跳的情况，那么就可以直接考虑一个暴力的树上dp求最小步数即可。dp[i]表示在深搜中i节点走到上一个节点的总步数（包括i节点子节点的步数）。由于要考虑叶子结点的两两搭配，那么我们可以增加一个维度来记录。详细看代码。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn=1e5+50;
int t;
int n;
int dp[maxn][2];
//dp[i][0]表示i节点子节点各自要走的步数
//dp[i][1]表示i节点叶子结点两两搭配后的步数
int eadg[maxn],son[maxn];
vector<int>v[maxn];
void dfs(int x,int f)
{
dp[x][0]=0;
dp[x][1]=inf;
int chd=0;
//cout<<":"<<x<<":"<<endl;
for(int i=0;i<v[x].size();i++)//先考虑x节点子节点各自走的步数
{
if(v[x][i]==f)
continue;
dfs(v[x][i],x);
chd++;
son[x]+=son[v[x][i]];
int d=(son[v[x][i]]&1?1:2);//考虑x节点走到上一个节点步数，奇数+1，偶数+2
dp[x][0]+=dp[v[x][i]][0]+d;
//cout<<v[x][i]<<":"<<son[x]<<" "<<dp[x]<<endl;
}
for(int i=0;i<v[x].size();i++)//考虑x节点的叶子节点两两搭配之后的步数
{
if(v[x][i]==f)
continue;
if(son[v[x][i]]==1)
dp[x][1]=min(dp[x][0],dp[x][1]);
int d=(son[v[x][i]]&1?1:-1);
dp[x][1]=min(dp[x][1],dp[x][0]-dp[v[x][i]][0]+dp[v[x][i]][1]+d);
}
if(!chd) son[x]=1;
}
int main()
{
//freopen("in.txt","r",stdin);
cin>>t;
while(t--)
{
memset(son,0,sizeof(son));
memset(eadg,0,sizeof(eadg));
scanf("%d",&n);
for(int i=0;i<=n;i++)
v[i].clear();
int a,b;
for(int i=0;i<n-1;i++)
{
scanf("%d%d",&a,&b);
v[a].push_back(b);
v[b].push_back(a);
eadg[a]++;
eadg[b]++;
}
if(n==2)
{
puts("1");
continue;
}
int root;
int cnt=0;
for(int i=1;i<=n;i++)
if(eadg[i]!=1)
root=i;
else
cnt++;
dfs(root,0);
printf("%d\n",dp[root][cnt&1]);
}
return 0;
}