洛谷 P1272 重建道路
一场可怕的地震后，人们用N个牲口棚(1≤N≤150，编号1…N)重建了农夫John的牧场。由于人们没有时间建设多余的道路，所以现在从一个牲口棚到另一个牲口棚的道路是惟一的。因此，牧场运输系统可以被构建成一棵树。John想要知道另一次地震会造成多严重的破坏。有些道路一旦被毁坏，就会使一棵含有P(1≤P≤N)个牲口棚的子树和剩余的牲口棚分离，John想知道这些道路的最小数目。 输入输出格式 输入格式： 第1行：2个整数，N和P 第2…N行：每行2个整数I和J，表示节点I是节点J的父节点。 输出格式： 单独一行，包含一旦被破坏将分离出恰含P个节点的子树的道路的最小数目。 输入输出样例 输入样例#1 11 6 1 2 1 3 1 4 1 5 2 6 2 7 2 8 4 9 4 10 4 11 输出样例#1 2 说明 【样例解释】 如果道路1-4和1-5被破坏，含有节点（1，2，3，6，7，8）的子树将被分离出来
题意应该就不用说了吧，题目中已经讲的很详细了，实在不懂，自己就花花图吧。 本题是一道树形DP，我们令方程dp[i][j]表示为以i为跟节点的子树恰好包括j个节点。 状态转移方程：
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int INF=0x3f3f3f3f; const int N=201; struct arr{ int nd,nx; }bot[N*2]; int du[N],head[N],dp[N][N],vis[N]; int n,k,res=INF,cnt; void add(int u,int v){bot[++cnt].nd=v; bot[cnt].nx=head[u]; head[u]=cnt;} inline int read(){ int x=0,w=1;char ch; while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') w=-1,ch=getchar(); while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch-48),ch=getchar(); return x*w; } void dfs(int u){ dp[u][1]=du[u];vis[u]=1; for (int i=head[u];i;i=bot[i].nx){ int v=bot[i].nd; if (!vis[v]){ dfs(v); for (int j=k;j>=1;j--) for (int k=1;k<=j;k++) dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]-2); /*树形背包类型 这里之所以要减去2,是因为在一开始的时候我们将dp[u][1]初始值赋值为du[u] 这里表示的是只有u这一个节点时，要把所有与它相连的边都切掉 而现在dp[u][j-k]+dp[v][k]都曾将u->v这条边切除过，现在我们要将这条边恢复 将u和v连在一起，这时我们需要将之前多花费两次切除给剪掉 */ } } res=min(res,dp[u][k]); } int main(){ n=read();k=read(); memset(dp,0x3f,sizeof(dp)); for (int i=1;i<n;i++) {int u=read(),v=read();add(u,v); add(v,u);du[u]++;du[v]++;} dfs(1); printf("%d",res); return 0; }dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]-2); 这里之所以要减去2,是因为我们在求dp[u][j-k]和dp[v][k]时， 都曾将u到v这条边切除过一次， 而且是肯定切除过，因为我们定义的dp[u][j]是指的以u为根的子树， 恰好包括j个节点的子树， 而u跟v本来就是父子关系，所以在这儿就是肯定切除的了。 /*这里有两重循环,第一重循环必须是从k到1,第二重可以是1到j或者j到1; 至于第一个为什么是k到1,我们可以按照01背包的想法来理解, 正是因为从1到k时我们会多次调用到dp[u][j],就相当于做完全背包时我们会多次调用之前的值, 就因为可以无限取,而在这里我们只能调用一次,具体我也讲不清楚. 刚刚自己写了下方程,好像会比较容易理解的,我在这里写出来吧. 先来说一下第一个循环k到1的情况: dp[u][5]: min(dp[u][4]+dp[v][1]、dp[u][3]+dp[v][2]、dp[u][2]+dp[v][3]、dp[u][1]+dp[v][4]) dp[u][4]: min(dp[u][3]+dp[v][1]、dp[u][2]+dp[v][2]、dp[u][1]+dp[v][3]) dp[u][3]: min(dp[u][2]+dp[v][1]、dp[u][1]+dp[v][2]) dp[u][2]: min(dp[u][1]+dp[v][1]) 在来看一下第一个循环1到k的情况 dp[u][2]: min(dp[u][1]+dp[v][1]) dp[u][3]: min(dp[u][2]+dp[v][1]、dp[u][1]+dp[v][2]) dp[u][4]: min(dp[u][3]+dp[v][1]、dp[u][2]+dp[v][2]、dp[u][1]+dp[v][3]) dp[u][5]: min(dp[u][4]+dp[v][1]、dp[u][3]+dp[v][2]、dp[u][2]+dp[v][3]、dp[u][1]+dp[v][4]) 是不是发现了这个好对称啊（QWQ），其实我们可以看出，上面那个更新后的dp[u][5] 、dp[u][4]、dp[u][3] 、dp[u][2]都不会在以后的更新中用到;而另一种情况则会用到之前更新的dp[u][3] 、dp[u][2]… 可能会有一个问题，第一种情况不也用到了很多次的dp[u][3] 、dp[u][2]，但我们可以看到一旦只要dp[u][3]等被更新后，他在下一次更新中就不会出现了。而我们可以这样理解，这里的一重循环的在更新前所有的dp[u][j]都是一个等级的，比如说现在是等级1，更新一次等级提高一次，并且只能服务于等级比他高的，去更新等级比他高的。所以讲到到这大概能理解吧。（或许是我太蠢了，一个很简单的东西要理解很久QWQ，还请大佬勿喷QWQ）
一个小思考，这道题是不是可以改编一下呢？变成这样子：求恰好切出p个点大小的子树的最小代价。（每条边都有各自的边权） 如果有大佬想出来，可以跟本蒟交流一波QWQ。欢迎评论！
