BZOJ 4919 大根堆(启发式合并)

题目描述

给定一棵n个节点的有根树，编号依次为1到n，其中1号点为根节点。每个点有一个权值v_i。 你需要将这棵树转化成一个大根堆。确切地说，你需要选择尽可能多的节点，满足大根堆的性质：对于任意两个点i,j，如果i在树上是j的祖先，那么v_i>v_j。 请计算可选的最多的点数，注意这些点不必形成这棵树的一个连通子树。

输入格式

第一行包含一个正整数n(1<=n<=200000)，表示节点的个数。 接下来n行，每行两个整数v_i,p_i(0<=v_i<=10^9,1<=p_i

输出格式

输出一行一个正整数，即最多的点数。

样例

样例输入

6
3 0
1 1
2 1
3 1
4 1
5 1

样例输出

5

由于上篇题解（emmm，一点也不像题解的题解）写的很乱（根本没注释）

还有一个最重要的原因是线段树合并的方法思路太乱

所以，我去研究了一下午的启发式合并和multiset

multiset的用法在上一篇随笔里

接下来借这道题理解一下启发式合并

启发式合并

顾名思义，启发式合并解决的是合并类的问题。

现在给一个最基本的合并问题。

我们要把N">N个集合，总共M">M个元素合并成一个大集合。

很容易得出，最坏的情况下需要合并N">N次，每次合并M">M个元素，也就是O(MN)">O(MN)的时间复杂度。

（一个集合有所有元素，然后一直把这个最大的往空集里合并，合并了N">N次）

然后我们想，这种合并策略时间复杂度高的原因在于把大的集合往小的集合里合并。

同样的问题，如果我们把小的集合往大的集合里合并，是不是就快很多？（for循环少跑好多次）

看看这个思路，是不是很像拍脑门临时得出来的？

是不是很受启发？

好了，它就叫启发式合并。

其思路是：每次把较小集合往较大集合里合并。

其原理是，因为是较小集合往较大集合里合，于是较小集合的元素个数被扩充了至少一倍，也就是变成了原来的二倍多，这样的话，我们就能保证，最坏的合并次数是O(log⁡N)">O(log?N)。

思路

这道题要求是维护一个大根堆

也就是说，从根节点向下，沿每根树枝所能到达的点（注意这里可以不连续）就是一个最长上升子序列

那么（显然），我们只需要递归到叶子节点，然后把子树合并上去是不是就可以了？

这样这些最长上升子序列的节点总数的和不就是答案了吗？

补充：s[i].size()即为最优答案（下面会解释到）

void dfs(int u){
    for(int i = head[u];i;i = nxt[i]){
        int v = to[i];
        dfs(v);
        if(s[u].size() < s[v].size()) swap(s[u],s[v]);//将v合并到u上,如果u的大小 < v的大小,交换
        for(sit it = s[v].begin();it != s[v].end();++it)//将v上每个点合并到u上
            s[u].insert(*it);//it是指针,it的值是s[v]中存的数的地址,*it就是该数
        s[v].clear();//可写可不写(已实验证明)
    }
    sit it = s[u].lower_bound(v[u]);
    if(it != s[u].end()) s[u].erase(it);
    s[u].insert(v[u]);
}

这时候就有人要问了：最后三行是在干啥呢？

显然，一个大根堆只有两种形式，一种是一棵树，还有一种就是由多个独立的叶子节点所构成

举个例子，以3节点为根的子树，如果要形成一颗有根树，有两个办法

一个是由3节点和5节点构成，还有一个是由5，6，7节点构成

所以此时以3节点为根的子树的最优解就是3

也就是说，如果树型的最优解大于单独节点的最优解，那么就会改变数组里数的个数，否则数组里数的个数保持不变，仍为叶子结点的个数（这就是为什么s[i].size()就是最优答案）

那么为什么要取lower_bound替换掉，而不直接把最大的替换掉呢

假设当前节点为u

那么替换的对象一定是大于等于v[u]的数

在这里，由于multiset中每个元素自动按升序排列

所以，我们认为每个数都是从开始到该数的最长上升子序列

那么如果我们把最大的数替换掉了，那么以该数为结尾的最长上升子序列就可能变得不合法

但我们把大于等于v[u]的第一个数替换掉可以看作一条新的LIS

也就是以替换掉的点为结尾的LIS的最大的点变小了

可以发现的是，在大根堆大小相同的时候，我们肯定想要顶点的权值尽可能小，这样就对后面合并更优。

所以这样才有可能去成为最大长度（有点贪心的感觉）

AC 代码

#include 
#include 
using namespace std;
#define ll long long
inline int in(){
    int x = 0;
    bool f = 1;
    char c = getchar();
    while(c > '9' || c < '0'){
        if(c == '-') f = 0;
        c = getchar();
    }
    while(c <= '9' && c >= '0'){
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    if(f) return x;
    else return -x;
}
#define sit multiset::iterator
const int N = 2e5+10;
int n,v[N];
int cnt,head[N],to[N],nxt[N];
multiset s[N];
inline void add(int u,int v){
    to[++cnt] = v;
    nxt[cnt] = head[u];
    head[u] = cnt;
}
void dfs(int u){
    for(int i = head[u];i;i = nxt[i]){
        int v = to[i];
        dfs(v);
        if(s[u].size() < s[v].size()) swap(s[u],s[v]);//将v合并到u上,如果u的大小 < v的大小,交换
        for(sit it = s[v].begin();it != s[v].end();++it)//将v上每个点合并到u上
            s[u].insert(*it);//it是指针,it的值是s[v]中存的数的地址,*it就是该数
        s[v].clear();//可写可不写(已实验证明)
    }
    sit it = s[u].lower_bound(v[u]);
    if(it != s[u].end()) s[u].erase(it);
    s[u].insert(v[u]);
}
int main(){
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    n = in();
    for(int i = 1;i <= n;++i){
        v[i] = in();
        int x = in();
        add(x,i);
    }
    dfs(1);
    printf("%d",s[1].size());
    return 0;
}

完结撒花*★,°*:.☆(￣▽￣)/$:*.°★* 。