Luogu P1272 重建道路

YorkWu

July 27, 2019

1187 views

No comments

982 words

[题目链接](https://www.luogu.org/problem/P1272)

树形DP，有点背包的意思。

---

用$f[x][i]$表示以x为根的子树，保留i个节点，最少割掉多少条边。然后搜一次树，回溯的时候转移，方程是$f[x][i]=min(f[x][i],f[x][j]+f[y][i-j]-2)$枚举j从1道i-1，具体看代码注释吧。

```cpp
#include<bits/stdc++.h>
using namespace std;

int n, p, dig[159];
struct Edge{
    int to, nxt;
}e[309];
int head[159], tot;
int f[159][159];

void add(int x, int y){
    e[++tot].to = y;
    e[tot].nxt = head[x];
    head[x] = tot;
}

void dfs(int x, int fa){
    f[x][1] = dig[x];
    //初始化一下，以x为根，只保留一个节点就是砍掉其他所有相连边，就是度数。
    for(int i = head[x]; i; i = e[i].nxt){
        int y = e[i].to;
        if(y == fa) continue;
        dfs(y, x);
        for(int j = p; j >= 1; j--){
            for(int k = 1; k < j; k++){
                f[x][j] = min(f[x][j], f[x][k] + f[y][j - k] - 2);
                //之所以要-2是因为刚刚初始化的时候砍掉了x->y的这条边，f[x][k]多砍了一次，f[y][j-k]又多砍了一次，所以减去2。
            }
        }
    }
}

int main(){
    scanf("%d%d", &n, &p);
    for(int i = 1; i <= n - 1; i++){
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y), add(y, x);
        dig[x]++, dig[y]++;
    }
    memset(f, 0x3f, sizeof(f));
    dfs(1, 0);
    int ans = 0x3f3f3f3f;
    for(int i = 1; i <= n; i++){
        ans = min(ans, f[i][p]);
    }
    printf("%d\n", ans);
    return 0;
}
```

Last modification：March 14, 2020