发布于

lp4577 FJOI2018 领导集团问题

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

对于序列上的情况，我们维护一个集合 \(S\) ，其中 \(S_i\) 表示，长度为 \(i\) 的最长不下降子序列的最后一项的最小值。 那么，对于新的点，我们考虑两种情况：它能加长序列，那么就加长；否则，就尽可能地更新最小值。

对于树上的情况，我们首先尝试考虑一种 \(O(n^2logn)\) 的做法。我们对于每一个节点维护一个集合 \(S_i\)， 其中 \(S_{i,j}\) 表示仅用到这个节点及其子树内的所有点，能够构造的大小为 \(j\) 的集合的最小项的最大值。

如果我们把所有子节点的 \(S\) 都已经整合在一起了，那么更新根节点是比较容易的：类比于序列即可。 问题在于子节点要如何合并。

仔细观察，发现，子节点的合并是一个类似于归并的操作。 这样我们就有了一个 \(O(n^2logn)\) 的「高」效做法。

怎么优化这个做法呢？ 我们不妨考虑重链剖分启发式合并。这样就将复杂度优化到了 \(O(nlog^2n)\) ，足以通过此题。 具体来说，我们对于每个节点开一个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;
}
发布于

CF1009F Dominant Indices

首先介绍一下我们亲爱的dsu on tree，也就是（一种？）树上启发式合并。
它本质上就是一种优化的暴力：对于树上的信息，我们先把树以某种方式剖分，然后对于关键链直接上传，非关键链暴力合并。
其中，长链剖分一般用来维护和深度相关的信息。
复杂度是O(n)的。证明我不太会。
在这一题中，我们考虑暴力维护每个点为根的子树中每一层的信息，并把非长儿子的信息合并到长儿子中。
为了保证线性，我们使用指针。
我们建一个指针数组f，其中f_{i,j}表示以i为根的根节点的子树中到i的距离为j的节点的个数。
同时建一个数组tmp，那么f就变成指向的是tmp里面的值。这样子就可以O(1)合并非长儿子的信息了。因为\sigma len<=n，所以空间是足够的。
那就昨晚了。 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int N=1000005;
struct ee{
	int v;
	int nxt;
}e[N<<1];
int h[N],et=0;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);Eadd(V,U);
}
int n;
int sn[N],len[N],ans[N],tmp[N],*f[N],*id=tmp;
inline void dfs0(int X,int FA){
	sn[X]=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA){
			continue;
		}
		dfs0(e[i].v,X);
		if(len[sn[X]]<len[e[i].v]){
			sn[X]=e[i].v;
		}
	}
	len[X]=len[sn[X]]+1;
}
inline void dfs1(int X,int FA){
	f[X][0]=1;
	if(sn[X]){
		f[sn[X]]=f[X]+1;
		dfs1(sn[X],X);
		ans[X]=ans[sn[X]]+1;
	}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA||e[i].v==sn[X]){
			continue;
		}
		f[e[i].v]=id;id+=len[e[i].v];
		dfs1(e[i].v,X);
		for(int j=1;j<=len[e[i].v];++j){
			f[X][j]+=f[e[i].v][j-1];
			if((j<ans[X]&&f[X][j]>=f[X][ans[X]])||(j>ans[X]&&f[X][j]>f[X][ans[X]])){
				ans[X]=j;
			}
		}
	}
	if(f[X][ans[X]]==1){
		ans[X]=0;
	}
}
void init(){
	scanf("%d",&n);
	int u,v;
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	dfs0(1,0);
	f[1]=id;id+=len[1];
	dfs1(1,0);
	for(int i=1;i<=n;++i){
		printf("%d\n",ans[i]);
	} 
}
int main(){
	init();
	return 0;
}
发布于

lp3302 SDOI2013 森林

我们发现，树上的链上第k大是可以使用主席树来维护的。对于每一个节点，我们从它的父亲复制一个版本，然后每一次求出LCA以后对链的两个端点、链的LCA、链的父亲分别查询。之后统计答案即可。
对于有连边操作的树，我们可能可以想到用LCT来维护。但是代码难度太高，而且事实上我也不知道要怎么写。所以我们可以考虑一种类似于按秩合并的操作，也就是说，每一次，我们把子树大小较小的子树合并到子树大小较大的子树。对于较小的那棵树，我们暴力更新其中的每一个节点。于是可以证明，每个节点的被更新次数最多不超过log次。
这样我们就有了一个\(O(nlog^2n)\)的做法。
注意：主席树的L，R本身就是节点位置；合并的时候要记得更新小树的根节点；返回的值是第k大的值而非第k大的排名因而要逆离散化。 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;

const int N=80005;
struct data{
	int id;
	int val;
}a[N];
inline bool cmp(const data &A,const data &B){
	return A.val<B.val;
}
inline bool cmp2(const data &A,const data &B){
	return A.id<B.id;
}
struct ee{
	int v;
	int nxt;
}e[N<<1];
int h[N],et=0;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V),Eadd(V,U);
}
#define MID (L+R>>1)
class CMT{
	private:
		class Node{
			public:
				int l;int r;int sz;
		};
		Node tr[30000000];
		int cnt,rt[N];
		inline void bld(int LST,int &NW,int L,int R,int V){
			NW=++cnt;tr[NW].sz=tr[LST].sz+1;
			if(L==R){return;}
			V<=MID?(bld(tr[LST].l,tr[NW].l,L,MID,V),tr[NW].r=tr[LST].r):(bld(tr[LST].r,tr[NW].r,MID+1,R,V),tr[NW].l=tr[LST].l);
		}
		inline int qry(int A,int B,int C,int D,int L,int R,int V){
			while(L<R){
//				printf("nw:%d %d %d %d %d\n",A,B,C,D,V);
				(tr[tr[B].l].sz-tr[tr[A].l].sz+tr[tr[D].l].sz-tr[tr[C].l].sz<V)?
				(V-=tr[tr[B].l].sz-tr[tr[A].l].sz+tr[tr[D].l].sz-tr[tr[C].l].sz,L=MID+1,A=tr[A].r,B=tr[B].r,C=tr[C].r,D=tr[D].r):
				(R=MID,A=tr[A].l,B=tr[B].l,C=tr[C].l,D=tr[D].l);
			}
			return L;
		}
		inline void prnt(int X){
			if(!X){
				return;
			}
			prnt(tr[X].l);
			prnt(tr[X].r);
			printf("%d ",tr[X].sz);
		}
	public:
		inline void ADD(int LST,int VER,int V){
			bld(rt[LST],rt[VER],1,80000,V);
		}
		inline int QRY(int A,int B,int C,int D,int V){
			return qry(rt[A],rt[B],rt[C],rt[D],1,80000,V);
		}
		inline void prpr(){
			cnt=0;
		}
		inline void pt(int X){
			prnt(rt[X]);
		}
}TR;
int vis[N],fa[N][20],sz[N],dep[N],loc[N];
inline void dfs0(int X){
//	printf("\t\t\tdfs0(%d)%d\n",X,dep[X]);
	vis[X]=sz[X]=1;
	for(int i=h[X];i;i=e[i].nxt){
		if(vis[e[i].v]){
			continue;
		}
		fa[e[i].v][0]=X;
		dep[e[i].v]=dep[X]+1;
		for(int j=1;j<=18;++j){
			fa[e[i].v][j]=fa[fa[e[i].v][j-1]][j-1];
		}
		TR.ADD(X,e[i].v,a[e[i].v].val);
		dfs0(e[i].v);
		sz[X]+=sz[e[i].v];
	}
}
inline void dfs1(int X){
	vis[X]=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(!vis[e[i].v]){
			continue;
		}
		dfs1(e[i].v);
	}
}
inline int szq(int X){
	for(int i=18;i>=0;--i){
		if(fa[X][i]!=0){
			X=fa[X][i];
		}
	}
	return sz[X];
}
inline void uni(int X,int Y){
	int SZ=szq(X);
	dfs1(X);
	add(X,Y);
	fa[X][0]=Y;
	dep[X]=dep[Y]+1;
	TR.ADD(Y,X,a[X].val);
	for(int i=1;i<=18;++i){
		fa[X][i]=fa[fa[X][i-1]][i-1];
	}
	int RT=X;
	for(int i=18;i>=0;--i){
		if(fa[RT][i]){
			RT=fa[RT][i];
		}
	}
	sz[RT]+=SZ;
	dfs0(X);
}
inline int lca(int X,int Y){
	if(dep[X]<dep[Y]){
		X^=Y^=X^=Y;
	}
	for(int i=18;i>=0;--i){
		if(dep[fa[X][i]]>=dep[Y]){
			X=fa[X][i];
		}
	}
	if(X==Y){
		return X;
	}
	for(int i=18;i>=0;--i){
		if(fa[X][i]!=fa[Y][i]){
			X=fa[X][i],Y=fa[Y][i];
		}
	}
	return fa[X][0];
}
int n,m,q,tid;
void init(){
	scanf("%d",&tid);
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i].val);
		a[i].id=i;
	}
	std::sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;++i){
		loc[i]=a[i].val;
	}
	for(int i=1;i<=n;++i){
		if(a[i].val!=a[i-1].val){
			a[i].val=a[i-1].val+1;
		}else{
			a[i].val=a[i-1].val;
		}
	}
	std::sort(a+1,a+1+n,cmp2); 
	int u,v;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	TR.prpr();
	for(int i=1;i<=n;++i){
		if(!vis[i]){
			dep[i]=1;
			TR.ADD(0,i,a[i].val);
			dfs0(i);
		}
	}
//	for(int i=1;i<n;++i){
//		printf("%d:",i);
//		TR.pt(i);
//		puts("");
//	}
	int lans=0,x,lc;
	char ch[10];
	for(int i=1;i<=q;++i){
		cin>>ch+1;
		switch(ch[1]){
			case 'Q':{
				scanf("%d%d%d",&u,&v,&x);
				u^=lans,v^=lans,x^=lans;
				lc=lca(u,v);
//				printf("\t\t\t%d %d %d\n",u,v,x);
				printf("%d\n",lans=loc[TR.QRY(fa[lc][0],u,lc,v,x)]);
				break; 
			}
			case 'L':{
				scanf("%d%d",&u,&v);
				u^=lans,v^=lans;
//				printf("\t\t\t%d %d\n",u,v);
				if(szq(u)>szq(v)){
					u^=v^=u^=v;
				}
				uni(u,v);
				break;
			}
		}
	}
}
int main(){
	init();
	return 0;
}
发布于

lp5290 十二省联考2019 春节十二响

首先我们考虑一种n^2logn的做法：将所有的子程序根据内存消耗来排序，然后每一次选中内存消耗最大且尚未被选中的，将所有内存比它小并且可以被同时选中的选中，然后统计贡献。
于是问题转化为如何用logn的复杂度查询祖先-后代关系。
我们考虑将整棵树展开为DFS序列，那么可以用树状数组维护祖先-后代关系。

如何优化这个做法呢？
我们注意到存在一种链的部分分。这种情况是容易解决的：搞两个堆，先把两条子链各自加到堆里，然后每次将它们的堆顶各自提出来，然后取较大值加入最终答案。
这启发我们用类似的方法处理一般的树状情况。
对于任意一个节点，我们建一个堆代表这个节点的子树的数值情况，每一次使用类似链的方法合并。
然而，这样并不能从本质上提升时间复杂度，它仍然需要n^2logn的时间复杂度，只不过不满。
考虑到这是树上的合并问题，因此尝试使用启发式合并，每次只合并两个节点，并将大小较小的那个节点的堆里的东西塞到大小较大的那个节点的堆里。
均摊而言，每个点的位置只会被转移一次——这是因为每一次有且仅有较小的那个堆会被合并，而较大的那个堆不会动。于是，如果一个点被转移了两次，那么一定意味着一个或者更多的节点在这一层的合并中没有被转移。所以均摊共转移不到n次。
对于每一次节点的位置转移，复杂度是logn，因此总复杂度是\(O(n*logn)\)

#include<iostream>
#include<cstdio>
#include<queue>

typedef long long ll;
const int N=200005;
inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
inline int Max(int A,int B){
	return A>B?A:B;
}
struct ee{
	int v;
	int nxt;
}e[N<<1];
int h[N],et=0;
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
int fa[N],n;
ll ans=0;
int val[N],id[N],st[N],tp=0;
std::priority_queue<int> q[N];
inline void uni(int X,int Y){
	if(q[id[X]].size()<q[id[Y]].size()){
		Swap(id[X],id[Y]);
	}
	while(!q[id[Y]].empty()){
		st[++tp]=Max(q[id[X]].top(),q[id[Y]].top());
		q[id[X]].pop(),q[id[Y]].pop();
	}
	while(tp){
		q[id[X]].push(st[tp--]);
	} 
}
inline void dfs(int X){
	for(int i=h[X];i;i=e[i].nxt){
		dfs(e[i].v);
		uni(X,e[i].v);
	}
	q[id[X]].push(val[X]);
}
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&val[i]);
		id[i]=i;
	}
	for(int i=2;i<=n;++i){
		scanf("%d",&fa[i]);
		add(fa[i],i);
	}
	dfs(1);
	while(!q[id[1]].empty()){
		ans+=q[id[1]].top();
		q[id[1]].pop();
	}
	printf("%lld\n",ans);
}

int main(){
	init();
	return 0;
}
发布于

CF600E Lomsat gelral

一道树上启发式合并的例题。
首先考虑暴力的做法。统计每一个子节点的信息，然后传到父节点。
我们发现这样做的复杂度是\(O(n^2)\)的。显然，复杂度是错误的。
我们考虑修改统计子节点的顺序。
重链剖分有一个很有意义的性质：一个点通向根的路径上的轻边的数量最多不会超过\(log_n\)。这利用重链剖分的性质可以轻松用反证法证明。
那么，依据这个性质，我们可以统计轻边、上传重边。这也就意味着，对于每一次访问，如果它是一条轻边，那么就把它的信息统计完了清空；如果是一条重边，那么把它的信息上传。
例如，我们现在有一个节点\(X\)，那么我们先计算它的所有轻节点，然后我们再计算它的重节点，最后将它除了重节点以外的地方都搜一遍，这样就获得了它的所有信息。
为什么这样做复杂度是对的呢？这就可以基于刚刚那个性质来证明了。具体地来说，一个节点会被清理信息，当且仅当它是一个节点下面的一个轻节点。也就是说，它被清空的次数就是它通向根的路径上轻边的数量。
由刚才那个性质可得，这个值是对数级的，所以复杂度是对的。
注意sm数组的tp的控制。 

#include<iostream>
#include<cstdio>
struct ee{
	int v;
	int nxt;
}e[200005];
int h[100005],et=0;
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
int sn[100005],sz[100005],a[100005],cnt[100005];
bool kp[100005];
long long ans[100005];//ans表示每个节点的答案 
long long sm[100005];//sn表示出现次数为cnt次的颜色值的和 
int n;
inline void dfs1(int X,int FA){
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v!=FA){
			dfs1(e[i].v,X);
		}
	}
	sz[X]=1;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v){
			sz[X]+=sz[e[i].v];
			if(sz[e[i].v]>sz[sn[X]]){
				sn[X]=e[i].v;
			}
		}
	}
}
int tp;
inline void rnw(int X,int FA,int V){
	sm[cnt[a[X]]]-=a[X];
	cnt[a[X]]+=V;
	sm[cnt[a[X]]]+=a[X];
	if(sm[tp+1]){
		++tp;
	}
	if(!sm[tp]){
		--tp;
	}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v!=FA&&!kp[e[i].v]){
			rnw(e[i].v,X,V);
		}
	}
}
inline void dfs2(int X,int FA,int isSn){
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v!=FA&&e[i].v!=sn[X]){
			dfs2(e[i].v,X,0);
		}
	}
	if(sn[X]){
		dfs2(sn[X],X,1);
		kp[sn[X]]=1;
	}
	rnw(X,FA,1);
	kp[sn[X]]=0;
	ans[X]=sm[tp];
	if(!isSn){
		rnw(X,FA,-1);
	} 
}
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	int u,v;
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
	dfs1(1,0);
	dfs2(1,0,1);
	for(int i=1;i<=n;++i){
		printf("%lld ",ans[i]);
	}
}

int main(){
	init();
	return 0;
}