洛谷P1272 重建道路

题目

树形DP，定义状态\(dp[i][j]\)为\(i\)的子树保留\(j\)个节点，且i不连接父亲所需要删去的最小值。

初始化：\(dp[i][1]\)等于与\(i\)相连的边数，只需要保留一个节点且要和父亲断开，那只能是\(i\)这一个节点，其他跟i相连的节点都要断开。

有转移方程\(dp[i][j]=min(dp[i][k]+dp[to][j-k]-2)\)\(to\)是\(i\)的子树中的一点

意思是\(i\)保留\(k\)节点的子树，\(to\)保留\(j-k\)个节点的子树的删去边的和，\(i\)此时保留的\(k\)节点是不包括\(to\)的，因为\(i\)在枚举子树的时候每个子树节点只会枚举一次，此时的\(dp[i][k]\)其实并没有更新。

在注意一下\(-2\)的意思，注意初始化的时候i是与所有边都是断开的，因此一开始i是不和to连接的，同时to也不和i连接，这样转移的话，i是要和to连一起的，因此就多删去了两条边，我们再少删去两条边就需要-2

#include <bits/stdc++.h>
#define N 1001
using namespace std;
int n, p, cnt, lin[N], f[N], degree[N], siz[N];
int dp[N][N];
struct edg {
    int to, nex;
}e[N *2];
inline void add(int f, int t)
{
    e[++cnt].nex = lin[f];
    e[cnt].to = t;
    lin[f] = cnt;
    degree[f]++; 
}
void dfs(int now, int fa)
{
    for (int i = lin[now]; i; i = e[i].nex)
    {
        int to = e[i].to;
        if (fa == to)
            continue;
        dfs(to, now);//预处理出子树的dp值即为dp[i][j]为当前i的子树保留j个节点，且子树不跟i相连所得到的最少连接边数。
    }
    for (int i = lin[now]; i; i = e[i].nex)
    {
        int to = e[i].to;
        if (fa == to)
            continue;
        for (int j = p; j >= 1; j--)//注意是01背包，所以如果倒着枚举，可能to的贡献会被算多次
        {
            for (int k = 1; k < j; k++)//k从小到大其实相当于j-k从大到小了
            dp[now][j] = min(dp[now][j], dp[now][j - k] + dp[to][k] - 2);
        }
    }
}
int main()
{
    scanf("%d%d", &n, &p);
    for (int i = 1; i < n; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }
    memset(dp, 13, sizeof(dp));  
    for (int i = 1; i <= n; i++)
            dp[i][1] = degree[i] , dp[i][0] = 0; 
    dfs(1, -1);
    int minn = 2147483647;
    for (int i = 1; i <= n; i++)
        minn = min(minn, dp[i][p]);
    printf("%d", minn);
    return 0;
}
/*
11 11
1 2
1 3
1 4
1 5
2 6
2 7
2 8
4 9
4 10
4 11
*/ 

洛谷P1272 重建道路

原文：https://www.cnblogs.com/liuwenyao/p/11743451.html