大根堆

题目描述

给定一棵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<i,p_1=0)，表示每个节点的权值与父亲。
输出格式

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

样例输入

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

样例输出

5

要做的是求选择节点数量最大值，满足节点权值不超过已选祖先节点权值

暴力做法：树形dp (60pts)

设 f[i][0] 为 i 节点不选，其子树的最大合法节点数量，f[i][1] 为 i 节点选上，子树最大节点数量

设 v 为 i 的儿子，w[i] 为i点的权值，maxn为当前祖先的最小值

f[i][0]= max ⁡ ( f [ v ] [ 1 ] + 1 , f [ v ] [ 0 ] ) \max(f[v][1]+1,f[v][0]) max(f[v][1]+1,f[v][0]) ， w[v] < = maxn;

f[i][1]= max ⁡ ( f [ v ] [ 1 ] , f [ v ] [ 0 ] ) \max(f[v][1],f[v][0]) max(f[v][1],f[v][0])+1 ， w[v] < =min(maxn,w[i]);

递归终止条件：到叶节点

正解

进一步分析题意，发现要求 LIS，只不过化链为树

还是用求 LIS 的方法，将 i 节点的子树合并，寻找子树中第一个大于 w[i] 的权值并替换，找不到就将w[i]插入集合，最终的答案为集合大小，考虑数据范围可以使用动态开点权值线段树，合并子树即合并线段树

考虑做法的正确性

替换后的序列并不是答案，但由于不需要考虑 LIS 的具体排列，那么在维护的序列中替换元素，是为了给最优答案的出现创造机会

1. 寻找集合中第一个大于 w[i] 的权值并替换

此时可以满足替换后的序列 1～i的部分属于原序列的上升子序列。这是由于操作遵循先后顺序，序列中 1～i-1 之间的权值都在替换 i 之前出现。由此，可以递推得到，若替换的是最大元素，可以满足替换后整个序列是原序列的上升子序列

2. 加入元素

由于之前的插入元素，并未改变已知序列的最大 LIS 长度，只是更改内部序列满足最优性。故若在最后加入一个元素，仍然满足是已知最大 LIS

#include<bits/stdc++.h>
using namespace std;
const int N=200011;
struct qxxx{
	int v,next;
}cc[N];
struct tree{
	int lc,rc,sum;
}tre[N*21];
int n,w[N];
int first[N],cnt;
int tot,root[N];
int lsh[N];
inline int read()
{
	int s=0;
	char ch=getchar();
	while(ch>'9'||ch<'0')
		ch=getchar();
	while(ch>='0'&&ch<='9')
	{
		s=(s<<1)+(s<<3)+(ch^48);
		ch=getchar();
	}
	return s;
}
void qxx(int u,int v)
{
	cc[++cnt].v=v;
	cc[cnt].next=first[u];
	first[u]=cnt;
	return;
}
void insert(int &x,int l,int r,int sum)
{
	if(!x)
		x=++tot;
	if(l==r)
	{
		tre[x].sum++;
		return;
	}
	int mid=(l+r)>>1;
	if(mid>sum)
		insert(tre[x].rc,mid+1,r,sum);
	else
		insert(tre[x].lc,l,mid,sum);
	tre[x].sum++;
	return;
}
void insert_(int &x,int l,int r,int sum)
{
	if(!x)
		x=++tot;
	if(l==r)
	{
		tre[x].sum--;
		return;
	}
	int mid=(l+r)>>1;
	if(mid>sum)
		insert(tre[x].rc,mid+1,r,sum);
	else
		insert(tre[x].lc,l,mid,sum);
	tre[x].sum--;
	return;
}
int query(int x,int l,int r,int val)
{
	if(!x||!tre[x].sum)
		return 0;
	if(l==r)
		return l;
	int mid=(l+r)>>1;
	if(mid<val)
		return query(tre[x].rc,mid+1,r,val);
	else
	{
		int s1=query(tre[x].lc,l,mid,val);
		int s2=query(tre[x].rc,mid+1,r,val);
		if(s1!=0&&s2!=0)
			return min(s1,s2);
		return s1+s2;
	}
}
int merge(int p,int q,int l,int r)
{
	if(!p)
		return q;
	if(!q)
		return p;
	if(l==r)
	{
		tre[p].sum+=tre[q].sum;
		return p;
	}
	int mid=(l+r)>>1;
	tre[p].lc=merge(tre[p].lc,tre[q].lc,l,mid);
	tre[p].rc=merge(tre[p].rc,tre[q].rc,mid+1,r);
	tre[p].sum=tre[p].sum+tre[q].sum;
	return p;
}
void lsh_()
{	
	sort(lsh+1,lsh+n+1);
	int x=unique(lsh+1,lsh+n+1)-lsh;
	for(int i=1;i<=n;i++)
		w[i]=lower_bound(lsh+1,lsh+x,w[i])-lsh;
	return;
}
void dfs(int x)
{
	for(int i=first[x];i;i=cc[i].next)
	{
		dfs(cc[i].v);
		root[x]=merge(root[x],root[cc[i].v],1,n);
	}
	int val=query(root[x],1,n,w[x]);
	insert(root[x],1,n,w[x],1);
	if(val)
		insert_(root[x],1,n,val,-1);
	return;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		w[i]=read();
		qxx(read(),i);
	}
	lsh_();
	dfs(1);
	cout<<tre[root[1]].sum<<endl;
	return 0;
}