分析:比较神奇的一道题.要把树变成环肯定要先变成链，然后把链给拼接成环.接下来考虑一个脑洞大开的树形dp:设f[i][0]表示i不与父节点相连的链数，f[i][1]表示i与父节点相连的链数，先考虑怎么转移f[i][0],如果i不与父节点相连，那么i肯定与两个子节点相连，其它的子节点都不与父节点相连，而且要剪掉与父亲节点的一条边，所以f[i][0] = (Σf[j][0]) - f[p][0] - f[q][0] + f[p][1] + f[q][1] - 1.f[i][1]也能很容易推导出来f[i][1] = (Σf[j][0]) - f[p][0] + f[p][1].这两个式子中的p,q使我们选出来与i组成链的子节点，为了使得f[i][0/1]最小，我们要选出使f[j][1] - f[j][0]最小的p,q,这个在枚举的时候扫一下就可以了.
最后是合并，一个树有N-1条边，先不断地删边，然后加边，加到N-1条边，最后再补一条边形成一个环，可以发现删边和加边是对称的，需要删掉链-1条边，那么也需要加上链-1条边，最后用一条边形成一个环就可以了.
树形dp，考虑好链的种类和怎么从子节点转移，充分利用好加边和删边的对称性,就能A掉此题，最关键的还是状态的表示，树形dp可能会需要保存不同的状态，如果对于当前状态推不下去了，就多加点状态，直到可做为止.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; const int inf = 0x7fffffff; int n, head[], to[], nextt[], tot = , f[][]; void add(int x, int y)
{
to[tot] = y;
nextt[tot] = head[x];
head[x] = tot++;
} void dfs(int u, int from)
{
int min1 = inf, min2 = inf,son = ,sum = ,sum2 = ;
for (int i = head[u]; i; i = nextt[i])
{
int v = to[i];
if (v != from)
{
dfs(v, u);
son++;
sum += f[v][];
sum2 += f[v][];
int temp = f[v][] - f[v][];
if (temp < min1)
{
min2 = min1;
min1 = temp;
}
else
if (temp < min2)
min2 = temp;
}
}
if (son == )
f[u][] = f[u][] = ;
if (son == )
f[u][] = f[u][] = sum2;
else
if (son >= )
{
f[u][] = sum + min1 + min2 - ;
f[u][] = sum + min1;
}
} int main()
{
scanf("%d", &n);
for (int i = ; i < n; i++)
{
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
add(v, u);
}
dfs(, );
printf("%d\n", f[][] * - ); return ;
}