本文共 2767 字，大约阅读时间需要 9 分钟。

题意

$给一颗树，问最少删除几条边，可以使一颗子树含有p个节点？$

思路

$树上问题，想必是树形dp。$

$设f[i][j]表示以i为根的子树，有j个节点最小删除边数。$

$状态转移：$

$为什么要减1？$

$最后答案是什么？$

int ans = f[1][p];    for(int i = 2;i <= n; i++) {
           if(f[i][p] < ans) ans = f[i][p] + 1;    }

$为什么除了根节点1，其他都要+1?$

$但是dp后f[2][4]=0，为什么呢？因为不需要删除任何边，但是1-2需要删除，所以+1。$

$总流程：$

1. $预处理f[i][1]=a[i]，a[i]为每个点的出度。$

for(int i = 1;i <= n; i++) f[i][1] = a[i];

2. $dfs(1)，返回值为sum，表示以u为子树的节点个数，然后就可以转化成背包了。$

int dfs(int u) {
       int sum = 1;    for(auto v : g[u]) {
           int temp = dfs(v);        sum += temp;        // 背包。。。    }    return sum;}

3. $状态转移。$

for(int j = sum;j >= 1; j--) {
       for(int k = 1;k < j; k++) {
           f[u][j] = min(f[u][j], f[u][i - k] + f[v][k] - 1);    }}

Code

#include "bits/stdc++.h"using namespace std;const ll INF = 0x3f3f3f3f;const int N = 1e3 + 10;vector
   
    
     > f(N, vector
     
      (N, INF));vector
      
        g[N];int dfs(int u) {
       int sum = 1;    for(auto v : g[u]) {
           int temp = dfs(v);        sum += temp;        for(int j = sum;j >= 1; j--) {
               for(int k = 1;k < j; k++) {
                   f[u][j] = min(f[u][j], f[u][j - k] + f[v][k] - 1);            }        }    }    return sum;}void solve() {
       int n, p; cin >> n >> p;    vector
       
         a(n + 1);    for(int i = 1;i <= n - 1; i++) {
           int u, v; cin >> u >> v;        a[u]++;        g[u].eb(v);    }    for(int i = 1;i <= n; i++) f[i][1] = a[i];    dfs(1);    int ans = f[1][p];    for(int i = 2;i <= n; i++) {
           if(f[i][p] < ans) ans = f[i][p] + 1;    }    cout << ans << endl;}signed main() {
       solve();}
       
      
     
    
   

转载地址：http://vfjwz.baihongyu.com/