BZOJ 4919 (树上LIS+启发式合并)

题面

给定一棵n个节点的有根树，编号依次为1到n，其中1号点为根节点。每个点有一个权值v_i。

你需要将这棵树转化成一个大根堆。确切地说，你需要选择尽可能多的节点，满足大根堆的性质：对于任意两个点i,j，如果i在树上是j的祖先，那么v_i>v_j。

请计算可选的最多的点数，注意这些点不必形成这棵树的一个连通子树。

分析

由于点不需要相邻，此题其实是树上的LIS，从叶子节点向根节点形成LIS

考虑LIS的\(O(nlogn)\)算法中用到的数组，用multiset对每个节点维护这样一个数组，存储子树内的值

向上的同时合并两个multiset，用启发式合并

时间复杂度应该是\(O(nlog^2n)\)

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<set>

#define maxn 200005

using namespace std;

int n;

struct edge{

	int from;

	int to;

	int next;

}E[maxn<<1];

int head[maxn];

int sz;

void add_edge(int u,int v){

	sz++;

	E[sz].from=u;

	E[sz].to=v;

	E[sz].next=head[u];

	head[u]=sz;

} 

int a[maxn];

multiset<int>s[maxn];

void merge(int x,int y){//启发式合并

	if(s[x].size()<s[y].size()) swap(s[x],s[y]);

	for(multiset<int>::iterator it=s[y].begin();it!=s[y].end();it++){

		s[x].insert(*it);

	}

}

void dfs(int x,int fa){

	for(int i=head[x];i;i=E[i].next){

		int y=E[i].to;

		if(y!=fa){

			dfs(y,x);

			merge(x,y);

		}

	}

	multiset<int>::iterator it=s[x].lower_bound(a[x]);

	if(it==s[x].end()) s[x].insert(a[x]);

	else{

		s[x].erase(it);

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

	}

}

int main(){

	int fa;

	scanf("%d",&n);

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

		scanf("%d %d",&a[i],&fa);

		if(fa!=0){

			add_edge(i,fa);

			add_edge(fa,i);

		}

	}

	dfs(1,0);

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

}

巴特西

BZOJ 4919 (树上LIS+启发式合并)

题面

分析

代码

最新文章

热门文章