洛谷P1272 重建道路 题解
题目链接：P1272 重建道路
题意：
一场可怕的地震后，人们用 $N$ 个牲口棚（编号 $1\sim N$）重建了农夫 John 的牧场。由于人们没有时间建设多余的道路，所以现在从一个牲口棚到另一个牲口棚的道路是惟一的。因此，牧场运输系统可以被构建成一棵树。
John 想要知道另一次地震会造成多严重的破坏。有些道路一旦被毁坏，就会使一棵含有 $P$ 个牲口棚的子树和剩余的牲口棚分离，John 想知道这些道路的最小数目。
$1\le N\le 150$，$1\le P\le N$，保证给出的是一棵树。
题目有点难懂，意思就是说切最少刀切出一个大小为 $p$ 的块，显然树上背包
设 $dp[u][j]$ 表示 $u$ 所在子树切出大小为 $j$ 的块并强制包含 $u$ 的最小花费，则
其中 $\text{tmp}[j]$ 为上一轮的 $dp[u][j]$ 。
后面一个柿子比较难懂
考虑一个大小为 $j$ 的块（包含 $u$ ）和一个大小为 $k$ 的块（包含 $v$ ）合并，显然要把和 $v$ 相连的那条边连上，但是本来是算在里面的（虽然是在最后才算的）
解释可能不是很清楚，直接看代码好了，细节比较多的
这道题的题解真是误导大众，填表法的树上背包是假的啊！
所有sz在dp前加的都是假复杂度。别怪我没提醒你们哦
时间复杂度 $O(np)$
代码：
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(205)
int n,p;
int tmp[N],sz[N],dp[N][N];
vector<int> vec[N];
void dfs(int u,int f)
{
sz[u]=1;dp[u][1]=0;
for(int v : vec[u])
if(v!=f)++dp[u][1];
for(int v : vec[u])
{
if(v==f)continue;
dfs(v,u);
for(int j=0; j<=min(sz[u],p); j++)
tmp[j]=dp[u][j];
for(int j=1; j<=min(sz[u],p); j++)
for(int k=1; k<=min(sz[v],p)&&j+k<=p; k++)
dp[u][j+k]=min(dp[u][j+k],tmp[j]+dp[v][k]-1);
sz[u]+=sz[v];
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> p;
for(int i=1,u,v; i<n; i++)
{
cin >> u >> v;
vec[u].push_back(v);
vec[v].push_back(u);
}
memset(dp,0x3f,sizeof(dp));
dfs(1,1);int res=dp[1][p];
for(int i=2; i<=n; i++)
res=min(res,dp[i][p]+1);
cout << res << '\n';
return 0;
}