[Lydsy1706月赛]大根堆

4919: [Lydsy1706月赛]大根堆

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 358 Solved: 150
[Submit][Status][Discuss]

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

很显然如果树退化成链的话，那么本题求的就是LIS。

但如果没有呢？

考虑一个节点x可能有很多儿子，但是每个儿子代表的子树是互不影响的，所以我们完全可以合并它们的LIS状态集合(启发式合并就好啦)，然后用val[x]替换掉集合中最小的>=它的数就好了。

最后的答案即为根的集合大小。

#include<bits/stdc++.h>

#define ll long long

#define pb push_back

using namespace std;

const int maxn=200005;

multiset<int> s[maxn];

multiset<int> ::iterator it;

vector<int> g[maxn];

int val[maxn],n,fa;

void dfs(int x){

	int to;

	for(int i=g[x].size()-1;i>=0;i--){

		to=g[x][i];

		dfs(to);

		if(s[to].size()>s[x].size()) swap(s[to],s[x]);

		for(it=s[to].begin();it!=s[to].end();++it) s[x].insert(*it);

		s[to].clear();

	}

	if(s[x].size()){

		it=s[x].lower_bound(val[x]);

		if(*it>=val[x]) s[x].erase(it);

	}

	s[x].insert(val[x]);

}

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;i++){

		scanf("%d%d",val+i,&fa);

		g[fa].pb(i);

	}

	dfs(1);

	printf("%d\n",s[1].size());

	return 0;

}

巴特西