题目意思：有N 个节点形成树状结构，现在想知道。给定一个数字P，问：删除最少的边使得形成的子树的节点有P 个；
很明显的树形DP[i][j] I为根子树形成j个节点最少减多少；
依赖性01问题，只不过这个合并时候的输的初始化不好想；
给出代码加注释；#include <cstdio>
#include <algorithm> #include <cmath> #include <cstdlib> #include <cstring> using namespace std; const int maxn=155; const int INF=0x3fffffff; struct Edge { int to,dis,pre; Edge(int to=0,int dis=0,int pre=0):to(to),dis(dis),pre(pre){} }; Edge edge[maxn]; int head[maxn],pos; int dp[maxn][maxn]; int N,P; bool fa[maxn]; void inint() { memset(fa,false,sizeof(fa)); for(int i=1;i<maxn;i++) for(int j=1;j<maxn;j++) dp[i][j]=INF; memset(head,-1,sizeof(head)); pos=0; } void add_edge(int s,int to,int dis) { edge[pos]=Edge(to,dis,head[s]); head[s]=pos++; } int dfs(int s) { int ans=1,key; dp[s][1]=0;//一开始只有一个跟节点； for(int w=head[s];~w;w=edge[w].pre) { Edge & tmp=edge[w]; key=dfs(tmp.to); ans+=key; for(int i=ans;i>=1;i--) {
//虽然对于枚举i=1 的情况下是不允许的但是 dp[s][i] 需要++ 而且下面的循环节也不会执行
dp[s][i]++; //多引出一个分支所以对应原本的【s】【i】，要切除新枚举出来的子树；
for(int j=1;j<=key&&(j<i);j++) dp[s][i]=min(dp[s][i],dp[s][i-j]+dp[tmp.to][j]); } } return ans; } void solve() { int root; for(int i=1;i<=N;i++) if(!fa[i]){root=i;break;} dfs(root); int ans=dp[root][P]; for(int i=1;i<=N;i++) ans=min(ans,dp[i][P]+1);//之所以加一 因为不是跟所以要把他和父亲的连线切了 printf("%d ",ans); } int main() { int a,b; while(~scanf("%d%d",&N,&P)) { inint(); for(int i=2;i<=N;i++) { scanf("%d%d",&a,&b); add_edge(a,b,-1); fa[b]=true; } solve(); } }