强烈推荐此题。此题应用树型DP解答。
首先明确一点，题中的环至少需要3个顶点。因此，对于树中的每个顶点，有3种状态。
f[x][0]表示以x为根的树，变成每个顶点恰好在一个环中的图，需要连的最少边数。
f[x][1]表示以x为根的树，除了根x以外，其余顶点变成每个顶点恰好在一个环中的图，需要连的最少边数。
f[x][2]表示以x为根的树，除了根x以及和根相连的一条链（算上根一共至少2个顶点）以外，其余顶点变成每个顶点恰好在一个环中的图，需要连的最少边数。
有四种状态转移（假设正在考虑的顶点是R，有k个儿子）：
A.根R的所有子树自己解决（取状态0），转移到R的状态1。即R所有的儿子都变成每个顶点恰好在一个环中的图，R自己不变。
B.根R的k-1个棵树自己解决，剩下一棵子树取状态1和状态2的最小值，转移到R的状态2。剩下的那棵子树和根R就构成了长度至少为2的一条链。
C.根R的k-2棵子树自己解决，剩下两棵子树取状态1和状态2的最小值，在这两棵子树之间连一条边，转移到R的状态0。
D.根R的k-1棵子树自己解决，剩下一棵子树取状态2（子树里还剩下长度至少为2的一条链），在这棵子树和根之间连一条边，构成一个环，转移到R的状态0。
这样就完成了树型DP。
/**//*************************************************************************
Author: WHU_GCC
Created Time: 2007-8-30 10:44:23
File Name: pku1848.cpp
Description:
************************************************************************/
#include <iostream>
#include <vector>
using namespace std;
#define out(x) (cout << #x << ": " << x << endl)
const int maxint = 0x7FFFFFFF;
typedef long long int64;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) 
{for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) {for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }
const int maxn = 110;
const int inf = 10000;
int n;
vector <int> v[maxn];
int f[maxn][3];
int used[maxn];
void dfs(int now)
{
used[now] = 1;
vector <int> child;
for (int i = 0; i < v[now].size(); i++) if (!used[v[now][i]])
{
dfs(v[now][i]);
child.push_back(v[now][i]);
}
if (child.size() == 0)
{
f[now][0] = inf;
f[now][1] = 0;
f[now][2] = inf;
}
// case 1
{
int sum = 0;
for (int i = 0; i < child.size(); i++)
sum += f[child[i]][0];
f[now][1] <?= sum;
}
// case 2
for (int i = 0; i < child.size(); i++)
{
int p = min(f[child[i]][1], f[child[i]][2]);
int sum = 0;
for (int j = 0; j < child.size(); j++) if (j != i)
sum += f[child[j]][0];
f[now][2] <?= sum + p;
f[now][0] <?= sum + f[child[i]][2] + 1;
}
// case 3
for (int i = 0; i < child.size(); i++)
for (int j = i + 1; j < child.size(); j++)
{
int p1 = min(f[child[i]][1], f[child[i]][2]);
int p2 = min(f[child[j]][1], f[child[j]][2]);
int sum = 0;
for (int k = 0; k < child.size(); k++) if (k != i && k != j)
sum += f[child[k]][0];
f[now][0] <?= sum + p1 + p2 + 1;
}
}
int dp()
{
for (int i = 1; i <= n; i++)
f[i][0] = f[i][1] = f[i][2] = inf;
memset(used, 0, sizeof(used));
dfs(1);
if (f[1][0] == inf)
return -1;
return f[1][0];
}
int main()
{
while (scanf("%d", &n) != EOF)
{
for (int i = 0; i < n - 1; i++)
{
int t1, t2;
scanf("%d%d", &t1, &t2);
v[t1].push_back(t2);
v[t2].push_back(t1);
}
printf("%d\n", dp());
}
return 0;
}