強(qiáng)烈推薦此題。此題應(yīng)用樹型DP解答。
首先明確一點(diǎn)，題中的環(huán)至少需要3個(gè)頂點(diǎn)。因此，對于樹中的每個(gè)頂點(diǎn)，有3種狀態(tài)。
f[x][0]表示以x為根的樹，變成每個(gè)頂點(diǎn)恰好在一個(gè)環(huán)中的圖，需要連的最少邊數(shù)。
f[x][1]表示以x為根的樹，除了根x以外，其余頂點(diǎn)變成每個(gè)頂點(diǎn)恰好在一個(gè)環(huán)中的圖，需要連的最少邊數(shù)。
f[x][2]表示以x為根的樹，除了根x以及和根相連的一條鏈（算上根一共至少2個(gè)頂點(diǎn)）以外，其余頂點(diǎn)變成每個(gè)頂點(diǎn)恰好在一個(gè)環(huán)中的圖，需要連的最少邊數(shù)。
有四種狀態(tài)轉(zhuǎn)移（假設(shè)正在考慮的頂點(diǎn)是R，有k個(gè)兒子）：
A.根R的所有子樹自己解決（取狀態(tài)0），轉(zhuǎn)移到R的狀態(tài)1。即R所有的兒子都變成每個(gè)頂點(diǎn)恰好在一個(gè)環(huán)中的圖，R自己不變。
B.根R的k-1個(gè)棵樹自己解決，剩下一棵子樹取狀態(tài)1和狀態(tài)2的最小值，轉(zhuǎn)移到R的狀態(tài)2。剩下的那棵子樹和根R就構(gòu)成了長度至少為2的一條鏈。
C.根R的k-2棵子樹自己解決，剩下兩棵子樹取狀態(tài)1和狀態(tài)2的最小值，在這兩棵子樹之間連一條邊，轉(zhuǎn)移到R的狀態(tài)0。
D.根R的k-1棵子樹自己解決，剩下一棵子樹取狀態(tài)2（子樹里還剩下長度至少為2的一條鏈），在這棵子樹和根之間連一條邊，構(gòu)成一個(gè)環(huán)，轉(zhuǎn)移到R的狀態(tài)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;
}