Luogu1272 重建道路

发布于 2019-10-22  293 次阅读


Link

一道树形DP

首先想可不可枚举删的边数和删那条边,发现完全不可行。

考虑将状态设为,对于一个点,我们在它的子树中删除 p-j 个点(即保留 j 个点)要删掉的最少边

可以先想边界,如果一个点都不删,则 f[i][0] = 0

如果只保留一个点,那么保留的点就是它自己,所以要删掉它的所有儿子节点的连边,则 f[i][1] = son[i]

现在想转移,如果要在点 i 上保留 j 个点,答案会从它的一棵子树删掉 j-k 个点中转移而来。我们设一条边从u->v ,则 f[u][j] = f[u][j] = min(f[u][j], f[u][k] + f[v][j - k] - 2);

其中转移方程中的-2是引起题解版大肆讨论的地方。可以这样理解,因为 vu 的儿子,而 v 的答案又是从 v 某个儿子中转移过来的,两次转移的前提条件都是有相连的边,再看我们的转移方程,这两条边已经在转移中统计,所以需要减掉。

Code

#include <bits/stdc++.h>
#define TEST std::cout << "pass" << endl;
using namespace std;

const int SIZE = 150 + 5;

int n, p, num;
int head[SIZE], f[SIZE][SIZE], son[SIZE];

struct node {
    int to, Next;
} edge[SIZE << 1];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void Addedge(int x, int y)
{
    edge[++num].to = y;
    edge[num].Next = head[x];
    head[x] = num;
}

inline void DP(int u, int fa)
{
    for (int i = head[u]; i; i = edge[i].Next) {
        int v = edge[i].to;
        if (v == fa) continue;
        DP(v, u);
        for (int j = p; j >= 1; j--) 
            for (int k = 1; k < j; k++) {
                f[u][j] = std::min(f[u][j], f[u][k] + f[v][j - k] - 2);
            }
    }
}

int main()
{
    int u, v;
    n = read(), p = read();
    for (int i = 1; i < n; i++) {
        u = read(), v = read();
        Addedge(u, v);
        Addedge(v, u);
        son[u]++, son[v]++;
    }
    memset(f, 0x3f, sizeof(f));
    for (int i = 1; i <= n; i++) f[i][0] = 0, f[i][1] = son[i];
    DP(1, 0);
    int ans = 2e9;
    for (int i = 1; i <= n; i++) ans = std::min(ans, f[i][p]);
    printf("%d", ans);
    return 0;
}

朴实沉毅