lp4577 FJOI2018 领导集团问题

我们尝试类比序列上的情况来看这一题。

对于序列上的情况,我们维护一个集合 ​ ,其中 ​ 表示,长度为 ​ 的最长不下降子序列的最后一项的最小值。

那么,对于新的点,我们考虑两种情况:它能加长序列,那么就加长;否则,就尽可能地更新最小值。

对于树上的情况,我们首先尝试考虑一种 ​ 的做法。我们对于每一个节点维护一个集合 ​, 其中 ​ 表示仅用到这个节点及其子树内的所有点,能够构造的大小为 ​ 的集合的最小项的最大值。

如果我们把所有子节点的 ​ 都已经整合在一起了,那么更新根节点是比较容易的:类比于序列即可。

问题在于子节点要如何合并。

仔细观察,发现,子节点的合并是一个类似于归并的操作。

这样我们就有了一个 ​ 的「高」效做法。

怎么优化这个做法呢?

我们不妨考虑重链剖分启发式合并。这样就将复杂度优化到了 ​ ,足以通过此题。

具体来说,我们对于每个节点开一个map,然后暴力合并。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int N=200005;
struct ee{
	int v;
	int nxt;
}e[N];
int h[N],et=0;
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
int w[N],sz[N],sn[N],dep[N],fa[N];
int id[N];
multiset<int> lst[N];
int n;
inline void dfs0(int X){
	sn[X]=0,sz[X]=1;
	for(int i=h[X];i;i=e[i].nxt){
		dfs0(e[i].v);
		sz[X]+=sz[e[i].v];
		if(sz[sn[X]]<sz[e[i].v]){
			sn[X]=e[i].v;
		}
	}
}
inline void dfs1(int X){
	if(sn[X]){
		dfs1(sn[X]);
		id[X]=id[sn[X]];
	}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==sn[X]){
			continue;
		}
		dfs1(e[i].v);
		lst[id[X]].insert(lst[id[e[i].v]].begin(),lst[id[e[i].v]].end());
	}
	lst[id[X]].insert(w[X]);
	multiset<int>::iterator it=lst[id[X]].lower_bound(w[X]);
	if(it!=lst[id[X]].begin()){
		--it;lst[id[X]].erase(it);
	}
}
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&w[i]);
		id[i]=i;
	}
	int x;
	for(int i=2;i<=n;++i){
		scanf("%d",&x);
		fa[i]=x;add(x,i);
	}
	dfs0(1);
	dfs1(1);
	printf("%d\n",lst[id[1]].size());
}
int main(){
	init();
	return 0;
}

发表评论

电子邮件地址不会被公开。