【题目链接】
【算法】
f[i][j]表示以i为根的子树中，最少删多少条边可以组成j个节点的子树
树上背包，即可
【代码】
#include <algorithm> #include <bitset> #include <cctype> #include <cerrno> #include <clocale> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <exception> #include <fstream> #include <functional> #include <limits> #include <list> #include <map> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stdexcept> #include <streambuf> #include <string> #include <utility> #include <vector> #include <cwchar> #include <cwctype> #include <stack> #include <limits.h> using namespace std; #define MAXN 200 const int INF = 1e8; int i,j,n,p,x,y,ans = INF; int sum[MAXN],f[MAXN][MAXN]; vector<int> e[MAXN]; inline void dfs(int x) { int i,j,k,y; sum[x] = 1; for (i = 0; i < e[x].size(); i++) { y = e[x][i]; dfs(y); sum[x] += sum[y]; for (j = sum[x]; j > 0; j--) { for (k = 1; k < j; k++) { f[x][j] = min(f[x][j],f[x][j-k]+f[y][k]-1); } } } } int main() { scanf("%d%d",&n,&p); for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { if (j > 1) f[i][j] = INF; } } for (i = 1; i < n; i++) { scanf("%d%d",&x,&y); e[x].push_back(y); f[x][1]++; } dfs(1); for (i = 1; i <= n; i++) { if (i == 1) ans = min(ans,f[i][p]); else ans = min(ans,f[i][p]+1); } printf("%d ",ans); return 0; }