[bzoj4919][Lydsy1706月赛]大根堆【dp】【启发式合并】【stl】

【题目链接】
　　https://www.lydsy.com/JudgeOnline/problem.php?id=4919
【题解】
　　很妙的一道题。考虑 $N * l o g N$ 的dp求最长上升序列的做法。我们把其中每一个值存入multiset中。那么其中一个值从小到大的排名即为序列末尾为这个值的序列长度。
　　现在考虑将其拓展到树上。显然两棵子树互不干扰，所以可以启发式合并。合并完了之后处理根节点，将比它大的第一个数改成它就可以了。如果不存在，直接插入。（想象一条链的过程）。
　　时间复杂度: $O (N * l o g N)$

/* --------------
    user Vanisher
    problem tree
----------------*/
# include <bits/stdc++.h>
# define    ll      long long
# define    inf     0x3f3f3f3f
# define    N       200010
using namespace std;
int read(){
    int tmp=0, fh=1; char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') fh=-1; ch=getchar();}
    while (ch>='0'&&ch<='9'){tmp=tmp*10+ch-'0'; ch=getchar();}
    return tmp*fh;
} 
multiset <int> mp[N];
struct node{
    int val,id,fa;
}p[N];
int n,f[N];
bool cmpval(node a, node b){return a.val<b.val;}
bool cmpid(node a, node b){return a.id<b.id;}
int mixed(int x, int y){
    if (mp[x].size()<mp[y].size())
        swap(x,y);
    multiset <int> :: iterator it=mp[y].begin();
    while (it!=mp[y].end()){
        mp[x].insert(*it);
        it++;
    }
    return x; 
}
int main(){
    n=read();
    for (int i=1; i<=n; i++){
        p[i].val=read(); p[i].fa=read();
        p[i].id=i;
    }
    sort(p+1,p+n+1,cmpval);
    int las=-1,cnt=0;
    for (int i=1; i<=n; i++){
        if (p[i].val!=las){
            las=p[i].val;
            cnt++;
        } 
        p[i].val=cnt;
    } 
    sort(p+1,p+n+1,cmpid);
    for (int i=1; i<=n; i++) f[i]=i;
    for (int i=n; i>=1; i--){
        multiset <int> :: iterator it=mp[f[i]].lower_bound(p[i].val);
        if (it!=mp[f[i]].end()) mp[f[i]].erase(it);
        mp[f[i]].insert(p[i].val);
        f[p[i].fa]=mixed(f[i],f[p[i].fa]);
    }
    printf("%d
",(int)mp[f[1]].size());
    return 0;
}