BZOJ 4871 - [Shoi2017]摧毁“树状图”

#动态规划 #树形动态规划

Published on 2017-05-02

题目地址

描述

自从上次神刀手帮助蚯蚓国增添了上千万人口（蚯口？），蚯蚓国发展得越来越繁荣了！最近，他们在地下发现了一些神奇的纸张，经过仔细研究，居然是 D 国 X 市的超级计算机设计图纸！

这台计算机叫做 “树状图”，由 $n$ 个计算节点与 $n - 1$ 条可以双向通信的网线连接而成，所有计算节点用不超过 $n$ 的正整数编号。顾名思义，这形成了一棵树的结构。

蚯蚓国王已在图纸上掌握了这棵树的完整信息，包括 $n$ 的值与 $n - 1$ 条网线的连接信息。于是蚯蚓国王决定，派出蚯蚓国最强大的两个黑客，小 P 和小 H，入侵 “树状图”，尽可能地摧毁它。

小 P 和小 H 精通世界上最好的编程语言，经过一番商量后，他们决定依次采取如下的步骤：

小 P 选择某个计算节点，作为他入侵的起始点，并在该节点上添加一个 P 标记。
重复以下操作若干次（可以是 $0$ $0$ 次）：
- 小 P 从他当前所在的计算节点出发，选择一条没有被标记过的网线，入侵到该网线的另一端的计算节点，并在路过的网线与目的计算节点上均添加一个 P 标记。
小 H 选择某个计算节点，作为她入侵的起始点，并在该节点上添加一个 H 标记。
重复以下操作若干次（可以是 $0$ $0$ 次）：
- 小 H 从她当前所在的计算节点出发，选择一条没有被标记过的网线，入侵到该网线的另一端的计算节点，并在路过的网线与目的计算节点上均添加一个 H 标记。（注意，小 H 不能经过带有 P 标记的网线，但是可以经过带有 P 标记的计算节点）
删除所有被标记过的计算节点和网线。
对于剩下的每条网线，如果其一端或两端的计算节点在上一步被删除了，则也删除这条网线。

经过以上操作后，“树状图” 会被断开，剩下若干个（可能是 $0$ 个）连通块。为了达到摧毁的目的，蚯蚓国王希望，连通块的个数越多越好。于是他找到了你，希望你能帮他计算这个最多的个数。

小 P 和小 H 非常心急，在你计算方案之前，他们可能就已经算好了最优方案或最优方案的一部分。你能得到一个值 $x$ ：

若 $x = 0$ ，则说明小 P 和小 H 没有算好最优方案，你需要确定他们两个的入侵路线。
若 $x = 1$ ，则说明小 P 已经算好了某种两人合作的最优方案中，他的入侵路线。他将选择初始点 $p_0$ ，并沿着网线一路入侵到了目标点 $p_1$ ，并且他不会再沿着网线入侵；你只需要确定小 H 的入侵路线。
若 $x = 2$ ，则说明小 P 和小 H 算好了一种两人合作的最优方案，小 P 从点 $p_0$ 入侵到了 $p_1$ 并停下，小 H 从点 $h_0$ 入侵到了 $h_1$ 并停下。此时你不需要指挥他们入侵了，只需要计算最后两步删除计算节点与网线后，剩下的连通块个数即可。

分析

直接考虑 $x = 0$ 时怎么做，对于 $x = 1, x = 2$ 直接输出最优解就行了，不理会给定的路线。

让这棵树以 $0$ 为根，设 $d(u)$ 为点 $u$ 的儿子数量 $-1$ ，那么删除一条链的剩下的联通块个数为 $1 + \sum_{u}d(u)$ ，如果这条链两个端点的 LCA 不为根，那么答案还需要 $+1$ ，因为上方还有一个联通块。

对于两条链，由于至多有一个点相交，所以根据两条链的位置关系，也会有类似的结论，无非是有加加减减的问题罢了。这就可以树形 DP 了，有很多种状态的设置方法，我这里提供一种容易想到但是较为繁琐的状态。

$f(u, 0)$ 以 $u$ 为根的子树，有一条可以向上沿伸的链，最大的 $\sum_{u}d(u)$ 。
$f(u, 1)$ 以 $u$ 为根的子树，有一条完整的链且这条链不包含 $u$ ，最多的联通块个数。
$f(u, 2)$ 以 $u$ 为根的子树，有一条完整的链且这条链包含 $u$ ，最多的联通块个数。
$f(u, 3)$ 以 $u$ 为根的子树，有一条完整的链，还有一条可以向上沿伸的链，最大的答案（由于两条链的情况太多，所以 +1/-1 的问题十分纠结，这里将 +1/-1 直接算进答案里面了，所以这里的答案定义比较模糊，这里的答案可以与 $f(u, 0)$ 类似地使用，拼另外一条链再 +1 即为联通块个数）
$f(u, 4)$ 以 $u$ 为根的子树，有两条完整的链这条两条链不包含 $u$ ，最多的联通块个数。
$f(u, 5)$ 以 $u$ 为根的子树，有两条完整的链这条两条链包含 $u$ ，最多的联通块个数。

解释一下状态设置的原因： $f(u, 1), f(u, 2)$ 需要区分开的原因是，在 $f(u, 2)$ 状态中，如果在点 $u$ 上面加一个点，则联通块个数会 +1，而 $f(u, 1)$ 却不存在这种问题。 $f(u, 4), f(u, 5)$ 的设置也是由于类似的原因。

转移十分麻烦，而且细节很多，这里只是简单说一下。

对于 $f(u, 0)$ ，要么是 $d(u) - 1$ ，要么是 $\max_{v\in\mathrm{son}(u)}f(v, 0) + d(u)$ （注意 $f(v, 0)$ 有可能是负数）。

对于 $f(u, 1)$ ，只能从儿子 $v$ 继承， $f(u, 1) = \max_{v\in\mathrm{son}(u)}\max(f(v, 1), f(v, 2) + 1)$ 。

对于 $f(u, 2)$ ，只能选两个 $f(v, 0)$ 拼起来，设 $\mathrm{mx}_i$ 为 $u$ 的儿子中第 $i$ 大的 $f(v, 0)$ ，则答案为 $\mathrm{mx}_1 + \mathrm{mx}_2 + d(u) + 1$ ，注意两个 $f(v, 0)$ 都可以不选，也就是 $\mathrm{mx}$ 的初始值为 $0$ ，后面还有很多初始值的问题，大家自行判断。

对于 $f(u, 3)$ ，可以从儿子继承上来。也可让完整的链在子树中，然后再选一个 $f(v, 0)$ 继承，注意不要重复。也可以是两条链都包含 $u$ ，设 $\mathrm{mx}_i$ 为 $u$ 的儿子中第 $i$ 大的 $f(v, 0)$ ，经过计算此时为 $\mathrm{mx}_1 + \mathrm{mx}_2 + \mathrm{mx}_3 + d(u)$ 。

对于 $f(u, 4)$ ，可以两条链从同一个儿子继承。也可以两条链从不同的儿子继承，此时有三种情况，注意存在一个联通块被算了两次需要 $-1$ 的情况。

对于 $f(u, 5)$ ，可以由 $f(u, 3)$ 拼一条链。也可以两条链同时包含 $u$ ，设 $\mathrm{mx}_i$ 为 $u$ 的儿子中第 $i$ 大的 $f(v, 0)$ ，此时为 $\mathrm{mx}_1 + \mathrm{mx}_2 + \mathrm{mx}_3 + \mathrm{mx}_4 + d(u) + 1$ 。也可以从儿子继承一个完整的，然后再选两个 $f(v, 0)$ 拼起来，这种情况比较麻烦，需要记录一下前缀、后缀最大值，然后枚举存在完整链的儿子，再来更新答案。

转移十分复杂，叙述严重不清，建议参照代码服用。

复杂度仍然是 $O(n)$ 。

代码

//  Created by Sengxian on 2017/04/27.
//  Copyright (c) 2017年 Sengxian. All rights reserved.
//  BZOJ 4871 树形 DP
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int readInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 100000 + 3, INF = 0x0f0f0f0f;
int x, n, p0, p1, h0, h1;

struct Edge {
    Edge *next;
    int to;
    Edge(Edge *next = NULL, int to = 0) : next(next), to(to) {}
} pool[MAX_N * 2], *pit = pool, *first[MAX_N];

int f[MAX_N][6], cnt[MAX_N];

void dfs(int u, int fa) {
    cnt[u] = -1;
    for (Edge *e = first[u]; e; e = e->next)
        if (e->to != fa) ++cnt[u], dfs(e->to, u);
}

inline void tension(int &a, const int &b) {
    if (b > a) a = b;
}

void dp(int u, int fa) {
    memset(f[u], -0x3f, sizeof f[u]);
    for (Edge *e = first[u]; e; e = e->next) if (e->to != fa) dp(e->to, u);

    // f[u][0] 向上
    f[u][0] = cnt[u]; // 单独 
    for (Edge *e = first[u]; e; e = e->next) if (e->to != fa)
        tension(f[u][0], f[e->to][0] + cnt[u]);

    // f[u][1] 有一个完整的，不包含 u
    for (Edge *e = first[u]; e; e = e->next) if (e->to != fa)
        tension(f[u][1], f[e->to][2] + 1), tension(f[u][1], f[e->to][1]);

    // f[u][2] 有一个完整的，包含 u
    int mx1 = 0;
    f[u][2] = cnt[u] + 1;
    for (Edge *e = first[u]; e; e = e->next) if (e->to != fa) {
        tension(f[u][2], mx1 + f[e->to][0] + cnt[u] + 1);
        tension(mx1, f[e->to][0]);
    }

    // f[u][3] 有一个完整的，且向上
    for (Edge *e = first[u]; e; e = e->next) if (e->to != fa) // 继承
        tension(f[u][3], f[e->to][3] + cnt[u]);

    // 完整的在下面
    int mx2 = 0;
    mx1 = -INF;
    for (Edge *e = first[u]; e; e = e->next) if (e->to != fa) {
        tension(f[u][3], mx1 + f[e->to][0] + cnt[u]);
        tension(f[u][3], f[e->to][1] - 1 + mx2 + cnt[u]);
        tension(f[u][3], f[e->to][2] - 1 + mx2 + cnt[u]);
        tension(mx1, f[e->to][1] - 1), tension(mx1, f[e->to][2] - 1);
        tension(mx2, f[e->to][0]);
    }

    // 交于一点
    int mx3 = 0;
    mx1 = mx2 = 0;
    for (Edge *e = first[u]; e; e = e->next) if (e->to != fa) {
        int v = f[e->to][0];
        if (v > mx1) swap(mx1, v);
        if (v > mx2) swap(mx2, v);
        if (v > mx3) swap(mx3, v);
    }
    tension(f[u][3], mx1 + mx2 + cnt[u] + mx3);

    // f[u][4] 有两个完整的，不包含 u
    for (Edge *e = first[u]; e; e = e->next) if (e->to != fa)
        tension(f[u][4], f[e->to][5] + 1), tension(f[u][4], f[e->to][4]);
    // 两边继承
    mx1 = -INF, mx2 = -INF;
    for (Edge *e = first[u]; e; e = e->next) if (e->to != fa) {
        tension(f[u][4], f[e->to][1] + mx1 - 1);
        tension(f[u][4], f[e->to][1] + mx2);
        tension(f[u][4], f[e->to][2] + mx1);
        tension(f[u][4], f[e->to][2] + mx2 + 1);
        tension(mx1, f[e->to][1]), tension(mx2, f[e->to][2]);
    }

    // f[u][5] 有两个完整的，包含 u
    // 封笔
    mx1 = -INF, mx2 = 0;
    for (Edge *e = first[u]; e; e = e->next) if (e->to != fa) {
        tension(f[u][5], mx1 + f[e->to][0] + cnt[u] + 1);
        tension(f[u][5], f[e->to][3] + mx2 + cnt[u] + 1);
        tension(mx1, f[e->to][3]), tension(mx2, f[e->to][0]);
    }
    // 全部在 u 上
    int mx4 = 0;
    mx1 = mx2 = mx3 = 0;
    for (Edge *e = first[u]; e; e = e->next) if (e->to != fa) {
        int v = f[e->to][0];
        if (v > mx1) swap(mx1, v);
        if (v > mx2) swap(mx2, v);
        if (v > mx3) swap(mx3, v);
        if (v > mx4) swap(mx4, v);
    }
    tension(f[u][5], mx1 + mx2 + mx3 + mx4 + cnt[u] + 1);

    vector<int> vec;
    vec.push_back(-1);
    for (Edge *e = first[u]; e; e = e->next) if (e->to != fa) vec.push_back(e->to);

    int sz = vec.size();
    static int pre[MAX_N], suf[MAX_N], prepre[MAX_N], sufsuf[MAX_N];
    pre[0] = prepre[0] = suf[sz] = sufsuf[sz] = 0;
    for (int i = 1; i < sz; ++i) {
        prepre[i] = max(prepre[i - 1], f[vec[i]][0] + pre[i - 1]);
        pre[i] = max(pre[i - 1], f[vec[i]][0]);
    }
    for (int i = sz - 1; i >= 1; --i) {
        sufsuf[i] = max(sufsuf[i + 1], f[vec[i]][0] + suf[i + 1]);
        suf[i] = max(suf[i + 1], f[vec[i]][0]);
    }
    for (int i = 1; i < sz; ++i) {
        int mx = max(f[vec[i]][1], f[vec[i]][2]);
        tension(f[u][5], mx + prepre[i - 1] + cnt[u]);
        tension(f[u][5], mx + sufsuf[i + 1] + cnt[u]);
        tension(f[u][5], mx + pre[i - 1] + suf[i + 1] + cnt[u]);
    }
}

int main() {
#ifdef DEBUG
    freopen("test.in", "r", stdin);
#endif
    int caseNum = readInt();
    x = readInt();

    while (caseNum--) {
        n = readInt();
        if (x >= 1) p0 = readInt() - 1, p1 = readInt() - 1;
        if (x == 2) h0 = readInt() - 1, h1 = readInt() - 1;

        pit = pool;
        for (int i = 0; i < n; ++i) first[i] = NULL;
        for (int i = 0; i < n - 1; ++i) {
            int u = readInt() - 1, v = readInt() - 1;
            first[u] = new (pit++) Edge(first[u], v);
            first[v] = new (pit++) Edge(first[v], u);
        }

        dfs(0, -1);
        dp(0, -1);

        printf("%d\n", max(f[0][4], f[0][5]));
    }

    return 0;
}

BZOJ 4815 - [Cqoi2017]小Q的表格 BZOJ 4872 - [Shoi2017]分手是祝愿

Sengxian's Blog

BZOJ 4871 - [Shoi2017]摧毁“树状图”

描述

分析

代码