题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4582
题目大意：
给出一个没有自环的有向图。
这个图的前n-1条边构成这个图的一个以节点1为根节点的DFS树。
T-Simple环的定义是：至多有一条边不在这棵DFS树上的环。
问，至少在图上选中多少条边。才使得每个T-simple环都至少有一条边被选中。
算法：
需注意的是，题目给出的是一个无向图的DFS树，
所以不在这棵树上的边一定不可能是"横叉边"，而一定是" 后向边(返祖边)"。
也就是说，不在DFS树上的边，一定是由某点指向它的某个祖先的。
很容易想象，如果不是这样，那么DFS树的形态一定会发生改变。（学过tarjan的人应该都能理解吧）
由于T-Simple环的定义要求至多有一条边不在DFS树上，
我们不妨枚举这条不在DFS树的边。
也就是对于每条不在DFS树上的边，
它连接了树上的某个点和它的某个祖先。
这两点间的树上路径以及这条不在DFS树的边，构成了一个T-simple环。
那么，这题的模型就可以抽象成。
给出一棵树，再给出若干限制。
每个限制指定一个点，以及它的一个祖先。
要求这个点到这个祖先的路径上，至少有一条边被选中。
问至少选中多少条边。
树形DP的模型也就很明显了。
我用lim[u]表示，u这个点，与它有非树边相连的祖先节点中，离它最近的那个的深度是多少。
如果u这个点没有任何通过非树边与祖先相连，那么lim[u]=0。
因为lim[u]=x表示，点x到点u的路径上，至少有一个点，它连向父节点的那条边要被选中。
不过节点0根本就没有父节点（我的节点是以0~n-1计数的），所以lim[u]=0代表没有边必须被选中
（如果不能理解的话，可以假想节点0到它到“父节点”的边被选中了，不过在计数的时候没把这条边算进去）。
d[u][x]表示，如果根到u的路径上离u最近的一条被选中的边，是由深度为x的点指向它的父节点的，那么以u为根的子树中至少要选中多少边。
于是就是一个很明了的自下向上更新的树形DP了。
显然，只有对于lim[u]<=k<=dep[u]的k，d[u][k]才是合法的。
要计算d[u][k]时，对于u的每个子节点v，
应该从d[v][0]~d[v][k]以及d[v][dep[v]]中，选取一个合法的最小值，
再把这些最小值加起来。
另外，对于dep[u][dep[u]]，应该再加上1，代表u指向根节点的那条边被选中了。
最后，d[0][0]的值即为所求。
PS：因为最近看到别人抱怨大家给的题解太简单，所以特意写的详细些。如果再看不懂。。。那就来问我吧 T^T
PPS：如果想了解这道题的贪心解法可以看sd6001大牛的解题报告
代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <climits>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <set>
#include <map>
#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;
const int MAXN = 2100;
vector<int> mm[MAXN];
int dep[MAXN], lim[MAXN];
int d[MAXN][MAXN];
void dfs(int u, int p)
{
for (int i = 0; i < mm[u].size(); i ++)
{
int v = mm[u][i];
if (v == p)
{
continue;
}
dep[v] = dep[u] + 1;
dfs(v, u);
}
}
void dp(int u, int p)
{
for (int i = lim[u]; i <= dep[u]; i ++)
{
d[u][i] = 0;
}
for (int i = 0; i < mm[u].size(); i ++)
{
int v = mm[u][i];
if (v == p)
{
continue;
}
dp(v, u);
int tmp = d[v][dep[v]];
for (int k = 0; k <= dep[u]; k ++)
{
if (d[v][k] != -1)
{
tmp = (tmp == -1) ? d[v][k] : min(tmp, d[v][k]);
}
if (k >= lim[u])
{
d[u][k] += tmp;
}
}
}
if (p != -1)
{
d[u][dep[u]] ++;
}
}
int main()
{
int n, m;
while (scanf("%d %d", &n, &m), n || m)
{
memset(d, -1, sizeof(d));
memset(lim, 0, sizeof(lim));
memset(dep, -1, sizeof(dep));
for (int i = 0; i < n; i ++)
{
mm[i].clear();
}
for (int i = 1; i < n; i ++)
{
int u, v;
scanf("%d %d", &u, &v);
u --;
v --;
mm[u].push_back(v);
mm[v].push_back(u);
}
dep[0] = 0;
dfs(0, -1);
for (int i = n; i <= m; i ++)
{
int u, v;
scanf("%d %d", &u, &v);
u --;
v --;
if (dep[u] < dep[v])
{
swap(u, v);
}
lim[u] = max(lim[u], dep[v] + 1);
}
dp(0, -1);
printf("%d\n", d[0][0]);
}
return 0;
}