传送门>>
题中说的分离出一颗大小为 $p$ 的子树, 其实更好的理解是保留下一颗子树(其实是一个意思)
所以又回到了常见的树上背包模型
令 $f[u][j]$ 表示以 u 为根的树 (不与父亲相连), 保留 j 个节点(包括根) 的最小切割次数
有 $$f[u][j] = min\left \{ f[u][j-k]+f[v][k]-2 \right \}$$
边界(初始化) $$f[u][1] = deg[u]$$
为什么要 $-2$ 呢 $?$
因为一条边在初始化时已被切割两次(父亲一次, 儿子一次), 但转移时是视为这条边是连通的, 所以要 $-2$
代码如下
- #include <iostream>
- #include <algorithm>
- #include <cstdio>
- #include <cstring>
- #define ll long long
- using namespace std;
- template <typename T> void in(T &x) {
- x = 0; T f = 1; char ch = getchar();
- while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
- while( isdigit(ch)) {x = 10 * x + ch - 48; ch = getchar();}
- x *= f;
- }
- template <typename T> void out(T x) {
- if(x <0) x = -x , putchar('-');
- if(x> 9) out(x/10);
- putchar(x%10 + 48);
- }
- //-------------------------------------------------------
- const int N = 151;
- int n,p;
- int sz[N],f[N][N],ans = 1e9+7;
- struct edge {
- int v,nxt;
- edge(int v = 0,int nxt = 0):v(v),nxt(nxt){};
- }e[N<<1]; int head[N],e_cnt;
- void add(int u,int v) {
- e[++e_cnt] = edge(v,head[u]); head[u] = e_cnt;
- }
- void dfs(int u,int fa) {
- int i,j,k;
- sz[u] = 1; int deg = (fa ? 1 : 0);
- for(i = head[u]; i;i = e[i].nxt) {
- int v = e[i].v; if(v == fa) continue;
- dfs(v,u);
- sz[u] += sz[v]; ++deg;
- }
- f[u][1] = deg;
- for(i = head[u]; i;i = e[i].nxt) {
- int v = e[i].v; if(v == fa) continue;
- for(j = min(p,sz[u]);j>= 1; --j) {
- for(k = 1;k <= min(j,sz[v]); ++k) {
- f[u][j] = min(f[u][j],f[u][j-k]+f[v][k]-2);//notice : -2
- }
- }
- }
- if(sz[u]>= p) {
- ans = min(ans,f[u][p]);
- }
- }
- int main() {
- int i,u,v;
- in(n); in(p);
- for(i = 1;i < n; ++i) {
- in(u); in(v);
- add(u,v); add(v,u);
- }
- memset(f,0x3f,sizeof(f));
- dfs(1,0);
- out(ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3155711.html