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
3 0
1 1
2 1
3 1
4 1
5 1
Sample Output
5
设f[i][j]表示i的子树内选择点集的权值最大值为j时最多选几个点，用启发式合并配合线段树转移即可。
时间复杂度O(nlog2n)。
观察转移可以得到如下等效的简单做法：当树退化成链时，其实就是求LIS一般情况下，对于每个点维护一个集合，每次将x点所有儿子的集合合并，然后用v去替换里面最小的比它大的数，最后根节点的集合大小就是答案。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
struct Node
{
int next,to;
}edge[];
int num,head[],c[],ch[][],flag,pos,root[],n,a[],b[];
void add(int u,int v)
{
num++;
edge[num].next=head[u];
head[u]=num;
edge[num].to=v;
}
void pushup(int rt)
{
c[rt]=c[ch[rt][]]+c[ch[rt][]];
}
int merge(int a,int b)
{
if (!a) return b;
if (!b) return a;
ch[a][]=merge(ch[a][],ch[b][]);
ch[a][]=merge(ch[a][],ch[b][]);
c[a]+=c[b];
c[b]=;
return a;
}
void del(int rt,int l,int r)
{
if (l==r)
{
c[rt]--;
flag=;
return;
}
int mid=(l+r)/;
if (c[ch[rt][]]) del(ch[rt][],l,mid);
else del(ch[rt][],mid+,r);
pushup(rt);
}
void update(int &rt,int l,int r,int x)
{
if (!rt) rt=++pos;
if (l==r)
{
if (c[rt]==) c[rt]++,flag=;
return;
}
int mid=(l+r)/;
if (x<=mid)
{
update(ch[rt][],l,mid,x);
if (flag&&c[ch[rt][]]) del(ch[rt][],mid+,r);
}
else
update(ch[rt][],mid+,r,x);
pushup(rt);
}
void dfs(int x)
{int i;
for (i=head[x];i;i=edge[i].next)
{
int v=edge[i].to;
dfs(v);
root[x]=merge(root[x],root[v]);
}
flag=;
update(root[x],,n,a[x]);
}
int main()
{int i,pa,sz;
cin>>n;
for (i=;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=a[i];
scanf("%d",&pa);
if (pa)
add(pa,i);
}
sort(b+,b+n+);
sz=unique(b+,b+n+)-b-;
for (i=;i<=n;i++)
a[i]=lower_bound(b+,b+sz+,a[i])-b;
dfs();
cout<<c[root[]];
}