思路：首先声明我是参考：http://blog.csdn.net/frog1902/article/details/9921845这位大牛的博客的。
他说的已经很详尽，但我还是要补充几点。
看完他的解题报告在看我的才好些。
我这的back[i]对于他的lim[i]。
我要补充的是，back[i]不是真正的back[i]，可以看到这行代码：back[u]=max(back[u],dep[v]+1);也就是说是其返回祖节点再往下的一个节点。
对于没有回退边的点,其back[i]==0相当于有一个回退边到根节点，那么本节点到根节点上的任何一条边被选择都是可行的。
dp时，首先将dp[u][i]（back[u]<=i<=dep[u]）置为0，意义是如果在u到back[u]之间已经有一条边被其他节点选择了，那么其不考虑有子节点的话，需要的边数就是0。dp[u][dep[u]]++的意义是选择dep[u]到其父节点的边的点正是u自己。
我个人认为最难理解的是对于dp[u][j]，要从dp[v][dep[v]]与0<=k<=j的深度中选取最小的dp[v][k]求和作为dp[u][j]的值。
由于dp[u][j]的意义是选择了深度为j的节点到其父节点的边后，以u为根的子树仍需要多少边，那么可以这个值也就是选择了深度为j的节点到其父节点的边后,以其子节点为根还需要dp[v][j]已经确定，那么自然以u为根的需要边数就是其子节点需要边数的和（前提是所有的选边一定要合法，合法的就是这条边一定要在back[u]到u的路径上）。
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<vector> #define Maxn 2010 using namespace std; int dp[Maxn][Maxn],dep[Maxn],back[Maxn],n,m,vi[Maxn]; vector<int> head[Maxn]; void init() { memset(dp,-1,sizeof(dp)); memset(dep,0,sizeof(dep)); memset(vi,0,sizeof(vi)); memset(back,0,sizeof(back)); for(int i=0;i<=n;i++) head[i].clear(); } void add(int u,int v) { head[u].push_back(v); head[v].push_back(u); } void dfs(int u) { int i,v,sz; vi[u]=1; sz=head[u].size(); for(i=0;i<sz;i++) { v=head[u][i]; if(vi[v]) continue; dep[v]=dep[u]+1; dfs(v); } } void Treedp(int u) { int i,v,sz,j; vi[u]=1; sz=head[u].size(); for(i=back[u];i<=dep[u];i++) dp[u][i]=0; for(i=0;i<sz;i++) { v=head[u][i]; if(vi[v]) continue; Treedp(v); int temp=dp[v][dep[v]]; for(j=0;j<=dep[u];j++) { if(dp[v][j]!=-1) { if(temp!=-1) temp=min(temp,dp[v][j]); else temp=dp[v][j]; } if(j>=back[u]) { if(temp!=-1) dp[u][j]+=temp; } } } if(u!=1) dp[u][dep[u]]++; } int main() { int i,j,u,v; while(scanf("%d%d",&n,&m)!=EOF,n||m) { init(); for(i=1;i<n;i++) { scanf("%d%d",&u,&v); add(u,v); } dfs(1); for(i=n;i<=m;i++) { scanf("%d%d",&u,&v); if(dep[u]<dep[v]) swap(u,v); back[u]=max(back[u],dep[v]+1); } memset(vi,0,sizeof(vi)); Treedp(1); printf("%d ",dp[1][0]); } return 0; }