bzoj4919: [Lydsy1706月赛]大根堆

· · 个人记录

Description

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

Input

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

Output

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

Sample Input

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

Sample Output

5

题解

容易看出这是一个变种LIS。如果只有一条链显然就是LIS。而这个就相当于在树上求LIS。

我们知道，LIS有一个经典二分做法。维护一个数组，初始时所有元素均为INF，每次加入一个元素，二分查找第一个大于等于它的元素。如果有，就将其替换，否则将新元素插入末尾。

现在我们用multiset来保存二分做法的那个数组。对于某个节点，先将不同子树之间的multiset用启发式合并合并为一个。然后把这个点权值丢进去替换掉第一个>=它的元素。

最后输出根节点的set的大小。

代码

#include<bits/stdc++.h>
#define MAXN 200010
namespace IO{
    char buf[1<<15],*fs,*ft;
    inline char gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
    inline int qr(){
        int x=0,rev=0,ch=gc();
        while(ch<'0'||ch>'9'){if(ch=='-')rev=1;ch=gc();}
        while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=gc();}
        return rev?-x:x;}
}using namespace IO;
using namespace std;
struct Edge{int t,next;}e[MAXN<<1];
int N,head[MAXN],cnt,fa[MAXN],val[MAXN];
void Add_Edge(int from,int to){
    e[++cnt].t=to;e[cnt].next=head[from];head[from]=cnt;
    e[++cnt].t=from;e[cnt].next=head[to];head[to]=cnt;
}
multiset<int> s[MAXN];
multiset<int>::iterator it;
inline void Merge(int A,int B){//multiset 启发式合并
    if(s[A].size()<s[B].size())swap(s[A],s[B]);
    it=s[B].begin();
    while(it!=s[B].end()){
        s[A].insert(*it);
        it++;
    } 
    s[B].clear();
}
void DFS(int u){
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].t;
        if(v==fa[u])continue;
        DFS(v);Merge(u,v);
    }
    it=s[u].lower_bound(val[u]);
    if(it!=s[u].end())s[u].erase(it);
    s[u].insert(val[u]);
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("bzoj4919.in","r",stdin);
    freopen("bzoj4919.out","w",stdout);
    #endif
    N=qr();
    for(int i=1;i<=N;i++){
        val[i]=qr();fa[i]=qr();
        if(i!=1)Add_Edge(fa[i],i); 
    }
    DFS(1);
    printf("%d",s[1].size());
    return 0;
}