题解-luogu-p5290春节十二响

题目链接

给定一棵有 $n$ 个节点的树，将树上所有节点分为若干组，其中每一组中的任意两个节点不能存在祖先-后代关系，每一组的权值为该组中所有节点权值的最大值，求所有组的权值总和最小值。

$1 \le n \le 200000$

我感谢我自己

首先考虑树退化为链的情况。树根最多有两棵子树，树根需要被单独分为一段，其余段中不能出现同一棵子树内的两个点。

这时我们需要将左子树中的节点与右子树中的节点配对。可以证明，将左子树中的最大值与右子树中的最大值、左子树中的次大值与右子树中的次大值以此类推两两配对，可以使所有段的权值总和最小。

如此一来，两条链实则被合并成为一条链。同理，多条链也可以使用类似的方式合并为一条链。

因此，我们可以维护每个节点到叶子节点的一条等效链，并且要求高效地将两条链合并为一条新链。

不难看出，由于我们需要取最大值的性质，可以使用堆来维护链信息。即，在每个节点上建立一个堆，堆中存储从当前节点到叶子节点的等效链上所有权值信息。

接下来需要解决的即为链的合并即堆的合并问题。假设需要合并堆 $q1$ ，$q2$ 。

如果 $q1.size()>q2.size()$，那么只需取出 $q1$ 的前 $q2.size()$ 项，并将它们与 $q2$ 中的所有元素取最大值即可。时间复杂度 $O(q2.size()\log q2.size())$ 。

如果 $q1.size()<q2.size()$，那么不仅需要取出 $q1$ 的所有项，并将它们与 $q2$ 中的前 $q1.size()$ 项取最大值，还需将 $q2$ 中剩余的元素插入 $q1$ 中。时间复杂度 $O(q2.size()\log q2.size())$ 。

不难看出，将大堆合并进入小堆，时间复杂度在 $O(max(q1.size(),q2.size()))$ 级别。但如果换一种思路，将小堆合并进入大堆，时间复杂度就降到 $O(min(q1.size(),q2.size()))$ 级别。此方法与并查集的按秩合并有异曲同工之妙，被成为启发式合并。

代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N;
vector<int> G[200005];
int M[200005];
priority_queue<int> q[200005];
int tmp[200005], cnt;

void dfs(int u) {
    for (vector<int>::iterator it = G[u].begin(); it != G[u].end(); it++) {
        int v = *it;
        dfs(v);
        cnt = 0;
        if (q[u].size() < q[v].size()) swap(q[u], q[v]);
        while(q[v].size()) {
            tmp[++cnt] = max(q[u].top(), q[v].top());
            q[u].pop(), q[v].pop();
        }
        for (int i = 1; i <= cnt; ++i)
            q[u].push(tmp[i]);
    }
    q[u].push(M[u]);
}

int main() {
    scanf("%d", &N);
    for (register int i = 1; i <= N; ++i)
        scanf("%d", &M[i]);
    for (register int i = 2; i <= N; ++i) {
        int f;
        scanf("%d", &f);
        G[f].push_back(i);
    }
    dfs(1);
    ll ans = 0;
    while (q[1].size()) ans += q[1].top(), q[1].pop();
    printf("%lld", ans);
    return 0;
}

# 启发式合并, 堆

题解-luogu-p5290春节十二响

Comments

一言（ヒトコト）

Recent

Categories

Tag Cloud

Your browser is out-of-date!