lp3225 HNOI2012 矿场搭建

这实际上是一个 Tarjan 求割点的裸题。

具体来说是这样的。首先,对于每一个连通块,答案显然是独立的。然后,一个连通块至少要有两个出口——这也是容易理解的。

接下来,我们把所有点双都缩成一个点,这时候整张图就一定是一棵无根树。

我们观察这棵树。如果树上只有一个节点,那么两个出口就都必须设在这个点双中;如果树上有多个节点,那么有且仅有叶子节点要各自设一个出口:这是因为,对于非叶子节点,它都有多条路走向叶子节点。

现在问题是如何求出这棵树。我们不妨用 Tarjan 来求。

Tarjan 是一种用于求点双联通分量的常用算法,以其发明者 Tarjan 所命名。特别需要注意的是,这里用到的是 Tarjan 求割点的部分,而不是像圆方树那样求点双的部分。

对于一个点,我们记两个数组,dfn 和 lw,分别表示它的 dfs 序和它在 dfs 树的子树内的所有节点的返祖边中 dfs 最小的节点。

如果某一个节点,它是根节点,并且它在 dfs 树上有超过一个子节点,那么它必然是割点——这是由 dfs 树的性质决定的。

如果一个节点,它的子节点的 lw 总是大等于它的 dfn ,那么就说明它的这棵子树内的所有节点只能抵达它或者它子树内的点,因而它必然是割点。

结合这两条性质即可找出点双。

然后统计一下即可。存在一定的细节。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N=505;
struct ee{
	int v;
	int nxt;
}e[N<<2];
struct Data{
	int u;int v;
}lst[N<<2];
int g[N],h[N],et=0;
inline void Eadd(int U,int V,int *H){
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}
inline void add(int U,int V,int *H){
	Eadd(U,V,H);
	Eadd(V,U,H);
}
int n;
int dfn[N],lw[N],dfsid=0,cnt=0,ag[N],sn[N];
inline void dfs0(int X,int FA){
	dfn[X]=lw[X]=++dfsid;sn[X]=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA){
			continue;
		}
		if(!dfn[e[i].v]){
			++sn[X];
			dfs0(e[i].v,X);
			lw[X]=min(lw[X],lw[e[i].v]);
			if((FA&&lw[e[i].v]>=dfn[X])){
				ag[X]=1;
			}
		}else{
			lw[X]=min(lw[X],dfn[e[i].v]);
		}
	}
	if(!FA&&sn[X]>1){
		ag[X]=1;
	}
}
ll vis[N],sm[N],tot[N],cal,sz,nv,deg[N];
inline void dfs1(int X){
	vis[X]=nv;++sz;
	for(int i=h[X];i;i=e[i].nxt){
		if(vis[e[i].v]==nv){
			continue;
		}
		if(ag[e[i].v]){
			vis[e[i].v]=nv;++cal;
			continue;
		}
		dfs1(e[i].v);
	}
}
ll ans,cans,nt;
void init(){
	cnt=et=dfsid=nt=0;
	for(int i=1;i<=n;++i){
		h[i]=dfn[i]=lw[i]=vis[i]=sm[i]=tot[i]=deg[i]=ag[i]=0;
	}
	int u,v;
	for(int i=1;i<=n;++i){
		scanf("%d%d",&u,&v);
		add(u,v,h);
		++deg[u];++deg[v];
		lst[i]=(Data){u,v};
		nt=max(nt,1ll*u);nt=max(nt,1ll*v);
	}
	for(int i=1;i<=nt;++i){
		if(!dfn[i]){
			dfs0(i,0);
		}
	}
//	for(int i=1;i<=nt;++i){
//		printf("%d ",ag[i]);
//	}
//	puts("");
	ans=0,cans=1;
	for(int i=1;i<=nt;++i){
		if(ag[i]){
			if(deg[i]<=1){
				++ans;
			}
		}else if(!vis[i]){
			nv=i;cal=0;sz=0;
			dfs1(i);
			if(cal==1){
				++ans;cans*=sz;
			}else if(cal==0){
				ans+=(sz==1?1:2),cans*=(sz==1?1:sz*(sz-1)/2);
			}
		}
	}
}
int main(){
	scanf("%d",&n);
	int T=0;
	while(n){
		++T;
		init();
		printf("Case %d: %lld %lld\n",T,ans,cans);
		scanf("%d",&n);
	}
	init();
	return 0;
}

lp4430 猴子打架/Prufer 序列

额…看起来是一道找规律题,实际上还是挺有门道的。

题目的题意就是,求 n 个点的点、边均有标号的生成树个数。

n 个点的无根有标号生成树个数,根据某个叫做 Cayley 的古老定理, 值是:

当然,由于边有标号,所以这里的值还要乘上一个​。

问题是 Cayley 定理要如何证明。

一种比较简易的方法是一种被称为 Prufer 序列的构造。通过这种构造,我们发现,有且仅有 ​ 种不同的方法来构造一棵有标号无根树。

这个序列是如何构造的呢?

我们考虑递归地构造这个序列。对于当前的树,我们选其中的编号最小的叶子节点,将它的相邻点——显然是唯一的——加入序列,然后删掉这个叶子节点。

这样,我们就得到了一个序列。这个序列中每一个点的出现次数是它的入度 -1 。

由此我们可以构造出这个序列。

通过 Prufer 序列,我们无损地将一棵有标号无根树的信息压缩成了一个序列。

那么要怎么把 Prufer 序列还原为一棵有标号无根树呢?我们有一种系统的方法。

首先选择一个数,这个数既不在已有的树中,也不在当前的序列中,并且它最小。那么,我们就可以确定,这个数便是我们当前要处理的叶子节点。

然后,我们把这个节点与当前枚举到的序列中的点连边。这等于是逆向还原 Prufer 序列的生成过程。

是不是对于任何一个值域在 n 范围内的长度为 n-2 的序列都可以还原成一棵树呢?

假设我们当前正在处理第 i 个节点,序列中剩下 k 种数,那么已经被作为叶子节点,已经连接或即将被连接的节点数则是 n-k 个。每处理一个节点,至多会消耗掉一个叶子节点的配额。因此已经连接的节点至多为 i-1 个。又因为 n-2-i+1 必须大于等于 k ,所以叶子节点必然不会不够。

那么完成最后一步以后叶子节点会不会有剩呢?每个节点会被连接的次数正好是它在序列中出现的次数 +1 ,这也就意味着,总度数恰好是 2n-2 ,由于每一条边都无向,所以构成的正好是一张 n-1 条边的图。

最后的疑问就是构成的图是不是连通的。考虑到 n-1 条边的连通图与 n-1 条边的无环图是等价的,我们不妨尝试证明它无环。

我们称,一个点被作为「要处理的叶子节点」来连接的过程为「向上连边」,那么每个点的向上连边操作会且仅会发生一次。在这种情况下,环会出现,只有可能是「向上连边」的时候连向的是自己所在的连通块内的点。

然而,向上连边的目标,一定还在 Prufer 序列中,而可以向上连边的点,一定不在 Prufer 序列中。我们于是证明了这张图无环。

既然这张 n-1 条边的图无环,那么它一定连通。

由此,我们发现,每一棵树都能唯一对应地生成一个 Prufer 序列,并且每一个 Prufer 序列都能生成一棵树。

这样我们就证明了 Prufer 序列和有标号无根树的一一对应性。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const ll MOD=9999991;

inline ll pw(ll A,ll X){
	ll RT=1;
	while(X){
		if(X&1){
			RT*=A;
			RT%=MOD;
		}
		A*=A;A%=MOD;X>>=1;
	}
	return RT;
}
int n;
void init(){
	scanf("%d",&n);
	ll fac=1;
	for(int i=1;i<n;++i){
		fac=fac*i%MOD;
	}
	printf("%lld\n",pw(n,n-2)*fac%MOD);
}
int main(){
	init();
	return 0;
}

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;
}

lp3313 SDOI2014 旅行

虽然这一题被划在主席树下面,但是一眼看过去这不就是树链剖分动态开点线段树的模板题么。
树链剖分后我们考虑对每一条链,建很多棵线段树,每棵线段树表示这条链上某种颜色的情况,然后大力合并。复杂度显然是对的。
关键是如何动态开点。本质上动态开点长得就和主席树差不多(这可能是为什么这题会被放在主席树下面),但是可能存在很多细节。
另:我的线段树区间查询写成依次单点查询,居然跑到了1.2s,让我一度以为是我常数问题…甚至差点卡进去了。精彩。

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

inline int rd(){
	char ch=getchar();int r=0;
	while(!isdigit(ch)){ch=getchar();}
	while(isdigit(ch)){r=r*10+ch-'0';ch=getchar();}
	return r;
}
const int N=100005;
inline int Max(int A,int B){
	return A>B?A:B;
}
inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
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,m;
int val[N],clr[N],dep[N],sz[N],sn[N],fa[N],dfn[N],cnt=0,tp[N];
inline void dfs0(int X){
	dep[X]=dep[fa[X]]+1;sz[X]=1;sn[X]=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==fa[X]){continue;}
		fa[e[i].v]=X;
		dfs0(e[i].v);
		if(sz[e[i].v]>sz[sn[X]]){
			sn[X]=e[i].v;
		}
		sz[X]+=sz[e[i].v];
	}
}
inline void dfs1(int X){
	dfn[X]=++cnt;
	if(sn[X]){tp[sn[X]]=tp[X];dfs1(sn[X]);}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==sn[X]||e[i].v==fa[X]){continue;}
		tp[e[i].v]=e[i].v;dfs1(e[i].v);
	}
}
#define MID ((L+R)>>1)
struct Node{
	int l;int r;int sm;int mx;
}tr[4000005];
int rt[N];
int tcnt=0;
inline void chg(int &NW,int L,int R,int P,int V){
	if(!NW){NW=++tcnt;}
	if(L==R){tr[NW].sm=V,tr[NW].mx=V;return;}
	P<=MID?(chg(tr[NW].l,L,MID,P,V)):(chg(tr[NW].r,MID+1,R,P,V));
	tr[NW].sm=tr[tr[NW].l].sm+tr[tr[NW].r].sm;tr[NW].mx=Max(tr[tr[NW].l].mx,tr[tr[NW].r].mx);
}
inline int qryMx(int X,int A,int B,int L,int R){
	if(A>R||B<L||!X){return 0;}
	if(A<=L&&B>=R){return tr[X].mx;}//此处不应写成L==R 
	return Max((A<=MID?qryMx(tr[X].l,A,B,L,MID):0),(B>MID?qryMx(tr[X].r,A,B,MID+1,R):0));
}
inline int qrySm(int X,int A,int B,int L,int R){
	if(A>R||B<L||!X){return 0;}
	if(A<=L&&B>=R){return tr[X].sm;}
	return (A<=MID?qrySm(tr[X].l,A,B,L,MID):0)+(B>MID?qrySm(tr[X].r,A,B,MID+1,R):0);
}
inline void ADD(int X,int P,int V){
	chg(rt[X],1,n,P,V);
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		val[i]=rd(),clr[i]=rd();
	}
	int u,v;
	for(int i=1;i<n;++i){
		u=rd(),v=rd();
		add(u,v);
	}
	sz[0]=0;fa[1]=0;
	dfs0(1);
	tp[1]=1;
	dfs1(1);
	for(int i=1;i<=n;++i){
		ADD(clr[i],dfn[i],val[i]);
	}
	char ch[10];
	int x,y,c;
	for(int i=1;i<=m;++i){
		std::cin>>ch+1;
		switch(ch[2]){
			case 'C':{
				x=rd(),y=rd();
				ADD(clr[x],dfn[x],0);
				ADD(clr[x]=y,dfn[x],val[x]);
				break;
			}
			case 'W':{
				x=rd(),y=rd();
				ADD(clr[x],dfn[x],val[x]=y);
				break;
			}
			case 'S':{
				x=rd(),y=rd();
				int RT=0;c=clr[x];
				while(tp[x]!=tp[y]){
					if(dep[tp[x]]<dep[tp[y]]){Swap(x,y);}
					RT+=qrySm(rt[c],dfn[tp[x]],dfn[x],1,n);
					x=fa[tp[x]];
				}
				if(dep[x]<dep[y]){Swap(x,y);}
				RT+=qrySm(rt[c],dfn[y],dfn[x],1,n);
				printf("%d\n",RT);
				break;
			}
			case 'M':{
				x=rd(),y=rd();
				int RT=0;c=clr[x];
				while(tp[x]!=tp[y]){
					if(dep[tp[x]]<dep[tp[y]]){Swap(x,y);}
					RT=Max(RT,qryMx(rt[c],dfn[tp[x]],dfn[x],1,n));
					x=fa[tp[x]];
				}
				if(dep[x]<dep[y]){Swap(x,y);}
				RT=Max(RT,qryMx(rt[c],dfn[y],dfn[x],1,n));
				printf("%d\n",RT);
				break;
			}
		}
	}
}
int main(){
//	freopen("33132.in","r",stdin);
//	freopen("33132.ans","w",stdout);
	init();
	return 0;
}

lp4768 NOI2018 归程

克鲁斯卡尔重构树模板题。
我们发现,这一题可以拆成两个步骤。第一个步骤,是找到所有u可以通过共享单车达到的点;第二个步骤,是找到这些点中到原点最小的点的距离。
我们容易发现,第一个步骤和长度无关,第二个步骤和海拔无关。
首先考虑第一个步骤。
我们建出一棵克鲁斯卡尔重构树——克鲁斯卡尔重构树是这样的一个数据结构:当你使用克鲁斯卡尔算法建最小/最大生成树的时候,每一次合并,你新建一个节点p,这个点的点权是这一次合并通过的边的边权,然后将即将合并的两个点的根节点合并到p下。这样我们构造出了一棵二叉树,其中所有叶子节点是原图上的节点。
克鲁斯卡尔重构树满足一些有意义的性质。
不妨以这题为例,我们构造一棵最大生成树,那么两点之间的lca的点权就是这两个点之间路径中边权最大的值。换句话说,从u在d的降水下可以到的节点,就是所有和u的lca的点权大于等于d的节点。考虑到这是一棵最大生成树,每个点的父亲节点的点权不会大于这个节点。这也就意味着,我们需要找到u的最高的祖先,使得这个祖先的点权大于等于d。不妨称这个祖先为w,那么w的子树的所有叶子节点,就是u在d的降水下能抵达的节点。
于是,我们求出了第一个步骤的解。
然后我们考虑第二个步骤的解。考虑到这是一张无向图,我们先求出1号节点到所有节点的距离,然后把这些值赋到叶子节点上,不妨称它为『距离权值』。因为我们每一次求min必然是求「某个点的子树中所有叶子节点的『距离权值』的最小值」,那么就可以进行树形dp,把这个最小值的信息直接记录到每个虚拟节点上。
这就做完了。

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

const int N=800005,M=800005;
const int INF=0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int a;
	int nxt;
}e[M<<1];
int h[N],et=0;
inline void Eadd(int U,int V,int W,int A){
	e[++et]=(ee){V,W,A,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W,int A){
	Eadd(U,V,W,A);
	Eadd(V,U,W,A);
}
struct tee{
	int v;
	int nxt;
}te[N<<1];
int g[N],tet=0;
inline void tEadd(int U,int V){
	te[++et]=(tee){V,g[U]};
	g[U]=et;
}
inline void tadd(int U,int V){
	tEadd(U,V);
	tEadd(V,U);
}
struct data{
	int u;int v;int a;
}lst[M];
inline bool cmp(const data &A,const data &B){
	return A.a>B.a;
}
int ff[N],f[N][20];
inline int fa(int X){
	return ff[X]==X?ff[X]:ff[X]=fa(ff[X]);
}
int val[N];
int n,m,cnt,rt;
inline void uni(int X,int Y){
	X=fa(X),Y=fa(Y);
	tadd(ff[X],cnt);tadd(ff[Y],cnt);
	ff[X]=ff[Y]=cnt;
}
inline void kruskal(){
	cnt=n;
	for(int i=1;i<=m;++i){
		if(fa(lst[i].u)==fa(lst[i].v)){
			continue;
		}
		val[++cnt]=lst[i].a;
		uni(lst[i].u,lst[i].v);
		if(cnt==n*2-1){
			break;
		}
	}
	rt=fa(1);
}
int dis[N],vis[N];
struct cmp2{
	inline bool operator()(int A,int B){
		return dis[A]>dis[B];
	}
};
priority_queue< int,vector<int>,cmp2 > q;
inline void dij(){
	for(int i=2;i<=n*2;++i){
		dis[i]=INF;vis[i]=0;
	}
	vis[1]=1,dis[1]=0;
	q.push(1);
	int p;
	while(!q.empty()){
		p=q.top();q.pop();vis[p]=0; 
		for(int i=h[p];i;i=e[i].nxt){
			if(dis[e[i].v]>dis[p]+e[i].w){
				dis[e[i].v]=dis[p]+e[i].w;
				if(!vis[e[i].v]){
					q.push(e[i].v);
				}
			}
		}
	}
}
inline void dfs0(int X){
	for(int i=g[X];i;i=te[i].nxt){
		if(te[i].v==f[X][0]){
			continue;
		}
//		printf("%d %d\n",X,te[i].v);
		f[te[i].v][0]=X;
		for(int j=1;j<=18;++j){
			f[te[i].v][j]=f[f[te[i].v][j-1]][j-1];
		}
		dfs0(te[i].v);
		dis[X]=Min(dis[X],dis[te[i].v]);
	}
}
inline int qry(int X,int D){
	for(int i=18;i>=0;--i){
		if(val[f[X][i]]>D){
			X=f[X][i];
		}
	}
	return dis[X];
}
void init(){
	scanf("%d%d",&n,&m);
	et=tet=0;
	for(int i=1;i<=n*2;++i){
		g[i]=h[i]=0;
	}
	int u,v,w,a;
	for(int i=1;i<=m;++i){
		scanf("%d%d%d%d",&u,&v,&w,&a);
		add(u,v,w,a);
		lst[i]=(data){u,v,a};
	}
	std::sort(lst+1,lst+1+m,cmp);
	for(int i=1;i<=n*2;++i){
		ff[i]=i;val[i]=INF;
	}
	kruskal();
	dij();
	dfs0(rt);
//	for(int i=1;i<=rt;++i){
//		printf("%d ",dis[i]);
//	}
//	puts("");
	int Q,K,S,lans=0,x,d;
	scanf("%d%d%d",&Q,&K,&S);
	for(int i=1;i<=Q;++i){
		scanf("%d%d",&x,&d);
		x=(x+lans*K-1)%n+1;d=(d+lans*K)%(S+1);
		printf("%d\n",lans=qry(x,d));
	}
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		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;
}

lp2515 HAOI2010 软件安装

简单的tarjan缩点+树形背包DP。
考虑N<=100,M<=500,只需要设f[i][j]表示第i个点,已用j的容量。
然后直接DP即可。
特别地,由于如果某一个点的子树中的点被选中了,这个点也要被选中,所以我们在计算每个点的时候,一定要将这个点加进去。
然后仔细看看这道题,发现它不保证没有环!
这下完蛋了,咋做啊?
考虑到这个环要么都选,要么都不选,所以可以先用tarjan找环,把找环后的点拿来dfs。
然后我们考虑一个性质:如果存在环,那么这个环缩成的点一定是某一棵树的树根。
所以我们不妨计算每一个点的入度,然后将入度为0的点连向虚点0。这样只需要一次DP。

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

inline int Max(int A,int B){
	return A>B?A:B;
}
inline int Min(int A,int B){
	return A<B?A:B;
}
struct ee{
	int v;
	int nxt;
}e[505];
int h[505],g[505],et=0;
inline void add(int *H,int U,int V){
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}
int n,m,f[505][505],w[505],v[505],ww[505],val[505],d[505],in[505];
int vis[505],clr[505],dfn[505],lw[505],cnt=0,ccnt=0,st[505],tp=0;
inline void dfs0(int X){
	vis[X]=1,dfn[X]=lw[X]=++cnt;
	st[++tp]=X;
	for(int i=g[X];i;i=e[i].nxt){
		if(!dfn[e[i].v]){
			dfs0(e[i].v);lw[X]=Min(lw[X],lw[e[i].v]);
		}else if(vis[e[i].v]){
			lw[X]=Min(lw[X],dfn[e[i].v]);
		}
	}
	if(dfn[X]==lw[X]){
		++ccnt;
		while(st[tp+1]!=X){
			clr[st[tp]]=ccnt;
			val[ccnt]+=v[st[tp]],ww[ccnt]+=w[st[tp]];
			vis[st[tp]]=0;
			--tp;
		}
	}
}
inline void dfs1(int X){
	for(int i=ww[X];i<=m;++i){
		f[X][i]=val[X];
	}
	for(int i=h[X];i;i=e[i].nxt){
		dfs1(e[i].v);
		for(int j=m-ww[X];j>=0;--j){//j表示之前的子树的重量和。 
			for(int k=0;k<=j;++k){//k表示这棵子树的重量和。 
				f[X][j+ww[X]]=Max(f[X][j+ww[X]],f[e[i].v][k]+f[X][j-k+ww[X]]); 
			}
		}
	}
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&w[i]);
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&v[i]);
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&d[i]);
		if(d[i]){
			add(g,d[i],i);
		}
	}
	for(int i=1;i<=n;++i){
		if(!dfn[i]){
			dfs0(i);
		}
	}
	for(int i=1;i<=n;++i){
		if(clr[d[i]]!=clr[i]){
			add(h,clr[d[i]],clr[i]);
			++in[clr[i]];
		}
	}
	for(int i=1;i<=ccnt;++i){
		if(!in[i]){
			add(h,0,i);
		}
	}
	dfs1(0);
	printf("%d\n",f[0][m]);
}
int main(){
	init();
	return 0;
}

lp3233 HNOI2014 世界树

让我们来分析这道题。
我们很容易地可以发现,如果一个节点是末端节点,那么它肯定是由它祖先中的第一个节点管辖更优。
由此我们继续推导,可以发现,假如只有两个关键点的话,它们之间的链上一定可以找到一个分界线,使得这条分界线的一段——以及所有与链上这一端相邻的节点——放在一个关键点上,并把剩下的放在另一个关键点上。这样是最优的。
然后我们考虑有三个关键点的情况。如果有三个关键点的话,问题似乎就复杂了很多,这是因为这条分界线必须是基于三个节点共同决定的。
我们换一个思路考虑。求出三个关键点两两的LCA。那么,这一分界线就必然可以在这六个点(最多六个)两两之间的链上找到。
存在一种叫做「虚树」的数据结构。这个数据结构本质上就是将所有关键点以及关键点两两之间的LCA建成一个数。
我们如此考虑,如果有一个点是关键点,那么它向下能够管辖的点的数量就是它的子树大小减去它的所有子节点能管辖的点数之和。
它向上能够管辖的点的数量则相对比较复杂。
我们考虑每一条边,假设我们已经预处理出了虚树上每一个点相邻最近的关键点,那么,如果这条边两端的点相邻最近的关键点是相同的,那么这条边(以及和这条边相邻的所有点)都划归到那个关键点下管辖。
如果这条边两段的点相邻最近的关键点不同,则需要使用倍增来确定这条边要如何被划分成两个部分。

接下来要考虑如何确定虚树上每一个点相邻最近的关键点。
我们不妨这样考虑:一个点相邻最近的关键点如果在它的下方,那么这可以通过树形DP求得;如果在它的上方或者其他子树内呢?
显然,如果这个点的相邻最近关键点在它的上方或者和它不在同一子树内,那么它的父亲的最近关键点一定与这个点的最近关键点相同。
于是,我们不妨从上而下DP,求得这个点在上方或者不在同一子树的最近关键点。

现在我们来梳理一下这一题的思路。
首先,我们进行预处理,处理出每个点的深度和dfn。
然后,我们进行两次树形DP,求出每个点的最近关键点。
第三,我们预处理出所有「末端节点」——也就是所有「是一个虚树上节点的直接儿子且子树内没有关键点的原树上的点」。这些点的贡献可以直接统计到它们父亲的最近关键点。
最后,我们依次考虑剩下的虚树边上的点。如果两段的最近关键点相同,那么就统计到那个最近关键点。否则就进行倍增寻找答案。

顺便讲一下如何建虚树。
我们将所有关键点按照dfs序排序,然后建一个栈,代表当前正在向下延长的链。
如果当前的点与栈顶的LCA的深度小等于次栈顶,那么就说明当前点不在栈顶的子树里,也就意味着栈顶处于当前应该维护的链外。
于是,我们需要就可以将新的这个点加入虚树和栈中。
否则,就说明原来的栈顶需要被弹出,那么就处理完它应该连的边然后将它弹出。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt)
#define Fv2(i,X) for(int i=g[X];i;i=e[i].nxt)
using namespace std;

typedef pair<int,int> pii;
const int N=300005;
const int INF=0x3f3f3f3f;
struct ee{
	int v;
	int nxt;
}e[1200005];
int h[N],g[N],et=0;
inline void add(int *H,int U,int V){
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}

int dfn[N],cnt=0,sz[N],dep[N],fa[N][20];
inline void dfs0(int X){
	dfn[X]=++cnt;sz[X]=1;
	Fv(i,X){
		if(e[i].v==fa[X][0]){
			continue;
		}
		fa[e[i].v][0]=X;dep[e[i].v]=dep[X]+1;
		dfs0(e[i].v);
		sz[X]+=sz[e[i].v];
	}
}
int usd[N],pt[N],ppt[N],hr[N],ans[N],up[N];
pii nr[N];
inline void dfs1(int X){
	nr[X]=(usd[X]?pii(0,X):pii(INF,0));
	Fv2(i,X){
		dfs1(e[i].v);
		nr[X]=min(nr[X],pii(nr[e[i].v].first+dep[e[i].v]-dep[X],nr[e[i].v].second));
	}
}
inline void dfs2(int X,int D,int P){
	if(pii(D,P)<nr[X]){
		nr[X]=pii(D,P);
	}else{
		D=nr[X].first,P=nr[X].second;	
	}
	Fv2(i,X){
		dfs2(e[i].v,D+dep[e[i].v]-dep[X],P);
	}
}
//子节点中所有子树中有虚树上节点的点都是不可以选取的。
//我们不妨逆向考虑,枚举每一个虚树上的子节点,然后从那个节点开始倍增,一直倍增到这棵树的子节点,然后把这些子节点的子树挖掉。 
inline void dfs3(int X){
	ans[hr[X]=nr[X].second]+=sz[X];
	Fv2(i,X){
		int nw=e[i].v;
		for(int j=18;j>=0;--j){
			if(fa[nw][j]&&dep[fa[nw][j]]>dep[X]){
				nw=fa[nw][j];
			}
		}
		ans[hr[X]]-=sz[up[e[i].v]=nw];
		dfs3(e[i].v);
	}
}
//现在剩下的末端节点就只有虚树上的节点了。 
//如果子节点的dfs序大于当前节点,那么分割点就偏上;否则偏下。 
inline void dfs4(int X){
	Fv2(i,X){
		if(hr[e[i].v]==hr[X]){
			ans[hr[X]]+=sz[up[e[i].v]]-sz[e[i].v];
		}else{
			int len=dep[hr[e[i].v]]+dep[X]-nr[X].first;
			len=((len&1)?(len+1)>>1:((len>>1)+(int)(hr[e[i].v]>hr[X])));
//			这里比较的是编号!!! 
			int nw=e[i].v;
			for(int j=18;j>=0;--j){
				if(dep[fa[nw][j]]>=len){
					nw=fa[nw][j];
				}
			}
			ans[hr[e[i].v]]+=sz[nw]-sz[e[i].v];
			ans[hr[X]]+=sz[up[e[i].v]]-sz[nw];
		}
		dfs4(e[i].v);
	}
}
inline void dfs5(int X){
	up[X]=hr[X]=0;
	Fv2(i,X){
		dfs5(e[i].v);
	}
	g[X]=0;
}
inline bool cmp(int A,int B){
	return dfn[A]<dfn[B];
}
inline int lca(int X,int Y){
	if(dep[X]<dep[Y]){
		swap(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 st[N],tp=0;
void init(){
	int n,Q;
	scanf("%d",&n);
	int u,v;
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(h,u,v);
		add(h,v,u);
	}
	dep[1]=1;
	dfs0(1);
	for(int j=1;j<=18;++j){
		for(int i=1;i<=n;++i){
			fa[i][j]=fa[fa[i][j-1]][j-1];
		}
	}
	scanf("%d",&Q);
	int m,X,Y;
	while(Q--){
		scanf("%d",&m);
		for(int i=1;i<=m;++i){
			scanf("%d",&pt[i]);
			ppt[i]=pt[i],usd[pt[i]]=1;
		}
		sort(pt+1,pt+1+m,cmp);
		st[tp=1]=pt[1];
		for(int i=2;i<=m;++i){
			X=pt[i],Y=lca(X,st[tp]);
			while(tp>1&&dep[Y]<=dep[st[tp-1]]){
				add(g,st[tp-1],st[tp]);
				--tp;
			}
			if(Y!=st[tp]){
				add(g,Y,st[tp]);st[tp]=Y;
			}
			st[++tp]=X;
		}
		while(tp>1){
			add(g,st[tp-1],st[tp]);
			--tp;
		}
		dfs1(st[1]);
		dfs2(st[1],nr[st[1]].first,nr[st[1]].second);
		dfs3(st[1]);
		dfs4(st[1]);
		ans[hr[st[1]]]+=sz[1]-sz[st[1]];
		for(int i=1;i<=m;++i){
			printf("%d ",ans[ppt[i]]);
		}
		puts("");
		dfs5(st[1]);
		for(int i=1;i<=m;++i){
			ans[pt[i]]=0,usd[pt[i]]=0;
		}
	}
}
int main(){
	init();
	return 0;
}

lp2146 NOI2015 软件包管理器

简化题意:
存在一棵树,其上所有点的初始值为0。
存在两种操作,分别是,将一个点的所有父亲节点改为1,或者将一个点的所有儿子节点改为0。
要求维护这个修改,并能得知每一次修改的节点个数。
当然地,考虑到这棵树是静态的,我们可以预处理出每个点的子树大小和它到根的路径长度。
于是,问题就转化为:
把目标节点到根节点的所有点变成1,把目标节点的子树变成0,查询目标节点到根节点的1的数量,查询目标节点的子树的1的数量。
这个问题似乎有些困难。我们考虑它的弱化版,也就是只有目标节点到根节点的这样一种情况。
显然,只需要上一个树剖就可以解决问题。
那么加上子树修改呢?
我们意识到一个很有趣的事情,那就是,一棵子树中的点,在树剖后,仍然是DFS序序列上连续的一段。又,这一段的长度显然是子树大小,由此问题可解。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt) 

const int N=100005;
struct ee{
	int v;
	int nxt;
}e[N<<1];
int h[N],et=0;
int n,q;
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 sz[N],sn[N],dep[N],fa[N];
inline void dfs0(int X,int FA){
	sz[X]=1,sn[X]=0,dep[X]=dep[FA]+1,fa[X]=FA;
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		dfs0(e[i].v,X);
		sz[X]+=sz[e[i].v];
		if(sz[sn[X]]<sz[e[i].v]){
			sn[X]=e[i].v;
		}
	}
}
int dfn[N],cnt=0,tp[N]; 
inline void dfs1(int X,int FA,int TP){
	tp[X]=TP,dfn[X]=++cnt;
	if(sn[X]){
		dfs1(sn[X],X,TP);
	}
	Fv(i,X){
		if(e[i].v==FA||e[i].v==sn[X]){
			continue;
		}
		dfs1(e[i].v,X,e[i].v);
	}
}

#define MID ((L+R)>>1)
#define LS (X<<1)
#define RS (X<<1|1)
#define LEN (R-L+1)
int tr[N<<2],tg[N<<2];
inline void rnw(int X,int L,int R,int C){
	tr[X]=LEN*C,tg[X]=C+1;
}
inline void updt(int X,int L,int R){
	tr[X]=tr[LS]+tr[RS];
}
inline void pshd(int X,int L,int R){
	if(tg[X]){
		rnw(LS,L,MID,tg[X]-1),rnw(RS,MID+1,R,tg[X]-1);
		tg[X]=0;
	}
}
inline void chg(int X,int L,int R,int A,int B,int C){
	if(A<=L&&R<=B){
		rnw(X,L,R,C);
		return;
	}
	if(R<A||L>B){
		return;
	}
	pshd(X,L,R);
	chg(LS,L,MID,A,B,C),chg(RS,MID+1,R,A,B,C);
	updt(X,L,R);
}
inline int qry(int X,int L,int R,int A,int B){
	if(A<=L&&R<=B){
		return tr[X];
	}
	if(R<A||L>B){
		return 0;
	}
	pshd(X,L,R);
	return qry(LS,L,MID,A,B)+qry(RS,MID+1,R,A,B);
}

inline int dwqry(int X){
	return qry(1,1,n,dfn[X],dfn[X]+sz[X]-1);
}
inline void dwchg(int X){
	chg(1,1,n,dfn[X],dfn[X]+sz[X]-1,0);
}
inline int up(int X){
	int RT=0;
	while(X){
		RT-=qry(1,1,n,dfn[tp[X]],dfn[X]);
		RT+=dfn[X]-dfn[tp[X]]+1;
		chg(1,1,n,dfn[tp[X]],dfn[X],1);
		X=fa[tp[X]];
	}
	
	return RT;
}
void init(){
	scanf("%d",&n);
	int x;
	for(int i=1;i<n;++i){
		scanf("%d",&x);
		add(i+1,x+1);
	}
	dfs0(1,0);
	dfs1(1,0,1);
	scanf("%d",&q);
	char ch[10];
	for(int i=1;i<=q;++i){
		std::cin>>ch+1;
		scanf("%d",&x);
		++x;
		if(ch[1]=='i'){
			printf("%d\n",up(x));
		}else{
			printf("%d\n",dwqry(x));
			dwchg(x);
		}
	}
}
int main(){
	init();
	return 0;
}

lp2486 SDOI2011 染色

考虑这一题在链上的情况。
显然,可以建一棵线段树,修改是打标记下传,查询是左右相加特判左右相邻处颜色是否相同。
看起来在树上也可以这么做。但是仔细想想会发现不太对。
这是因为,根据树链剖分的原理,每两条剖开的链是独立查询的。
因此,在树上查询的时候,需要额外查询两个相接的链的接驳处的颜色是否相同。
这大概就做完了。

然后我们发现实时查询接驳处的颜色不仅很傻,而且容易错。
所以我们考虑开两个数组:lc和rc,储存一个区间内左端颜色和右端颜色。

另外就是链上接驳处的颜色问题。一种容易想到的方法是每一次记录它来的那个点,然后比较来的那个点和自身。
然而这么做同样是不仅傻而且容易错的。于是我们考虑另一种方法:每一次比较链顶和链顶的父亲这两个点,并将它的负贡献预先扣除。这样可以有效简化代码。

#include<iostream>
#include<cstdio>
#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt)

inline void Swap(int &A,int &B){
    A^=B^=A^=B;
}
int n,m;
const int N=100005;
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 sn[N],sz[N],fa[N],dep[N];
inline void dfs0(int X,int FA){
    fa[X]=FA;sz[X]=1;dep[X]=dep[FA]+1;sn[X]=0;
    Fv(i,X){
        if(e[i].v==FA){
            continue;
        }
        dfs0(e[i].v,X);
        if(sz[e[i].v]>sz[sn[X]]){
            sn[X]=e[i].v;
        }
        sz[X]+=sz[e[i].v];
    }
}
int dfn[N],tp[N],cnt=0;
inline void dfs1(int X,int FA,int TP){
    dfn[X]=++cnt;tp[X]=TP;
    if(sn[X]){
        dfs1(sn[X],X,TP);
    }
    Fv(i,X){
        if(e[i].v==FA||e[i].v==sn[X]){
            continue;
        }
        dfs1(e[i].v,X,e[i].v);
    }
}
int clr[N];
#define MID ((L+R)>>1)
#define LS (X<<1)
#define RS (X<<1|1)
int tr[N<<2],tg[N<<2],val[N<<2],lc[N<<2],rc[N<<2];
inline void mdf(int X,int C){
    tr[X]=tg[X]=lc[X]=rc[X]=C;
    val[X]=1;
}
inline void pshd(int X,int L,int R){
	if(L==R){
		return;
	}
    if(tg[X]){
        mdf(LS,tg[X]),mdf(RS,tg[X]);
        tg[X]=0;
    }
}
inline int qryc(int X,int L,int R,int P){
    if(L==R){
        return tr[X];
    }
    pshd(X,L,R);
    return P<=MID?qryc(LS,L,MID,P):qryc(RS,MID+1,R,P);
}
inline void updt(int X,int L,int R){
    val[X]=(val[LS]+val[RS]-(rc[LS]==lc[RS]));
    lc[X]=lc[LS],rc[X]=rc[RS];
}
inline void chg(int X,int L,int R,int A,int B,int C){
    if(A<=L&&R<=B){
        mdf(X,C);
        return;
    }
    if(L>B||R<A){
        return;
    }
    pshd(X,L,R);
    chg(LS,L,MID,A,B,C);chg(RS,MID+1,R,A,B,C);
    updt(X,L,R);
}
inline int qryv(int X,int L,int R,int A,int B){
    if(A<=L&&R<=B){
        return val[X];
    }
    if(L>B||R<A){
        return 0;
    }
    pshd(X,L,R);
    return qryv(LS,L,MID,A,B)+qryv(RS,MID+1,R,A,B)-((A<=MID&&B>MID)?(rc[LS]==lc[RS]):0);
}
void init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&clr[i]);
    }
    int u,v;
    for(int i=1;i<n;++i){
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    sz[0]=0,dep[0]=0;
    dfs0(1,0);
    dfs1(1,0,1);
    for(int i=1;i<=n;++i){
        chg(1,1,n,dfn[i],dfn[i],clr[i]);
    }
    char ch[4];
    int c,ans;
    for(int i=1;i<=m;++i){
        std::cin>>ch+1;
        switch(ch[1]){
            case 'Q':{
                scanf("%d%d",&u,&v);
                ans=0;
                while(tp[u]!=tp[v]){
                    if(dep[tp[u]]<dep[tp[v]]){
                        Swap(u,v);
                    }
                    ans+=qryv(1,1,n,dfn[tp[u]],dfn[u]);
                    ans-=(qryc(1,1,n,dfn[tp[u]])==qryc(1,1,n,dfn[fa[tp[u]]]));
                    u=fa[tp[u]];
                }
                if(dep[u]<dep[v]){
                    Swap(u,v);
                }
                ans+=qryv(1,1,n,dfn[v],dfn[u]);
                printf("%d\n",ans);
                break;
            }
            case 'C':{
                scanf("%d%d%d",&u,&v,&c);
                while(tp[u]!=tp[v]){
                    if(dep[tp[u]]<dep[tp[v]]){
                        Swap(u,v);
                    }
                    chg(1,1,n,dfn[tp[u]],dfn[u],c);
                    u=fa[tp[u]];
                }
                if(dep[u]<dep[v]){
                    Swap(u,v);
                }
                chg(1,1,n,dfn[v],dfn[u],c);
                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;
}

lp2590 ZJOI2008 树的统计

树剖套线段树裸题。

#include<iostream>
#include<cstdio>
#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt)
using namespace std;
inline int Max(int A,int B){
	return A>B?A:B;
}
inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
const int N=30005;
const int INF=2147483647;
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 dep[N],fa[N],sz[N],sn[N],tp[N],dfn[N];
int val[N],n;
inline void dfs0(int X,int FA){
	sz[X]=1,sn[X]=0;
	fa[X]=FA;dep[X]=dep[FA]+1;
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		dfs0(e[i].v,X);
		sz[X]+=sz[e[i].v];
		if(sz[e[i].v]>sz[sn[X]]){
			sn[X]=e[i].v;
		}
	}
}
int cnt=0;
inline void dfs1(int X,int FA,int TP){
	tp[X]=TP;
	dfn[X]=++cnt;
	if(sn[X]){
		dfs1(sn[X],X,TP);
	}
	Fv(i,X){
		if(e[i].v==FA||e[i].v==sn[X]){
			continue;
		}
		dfs1(e[i].v,X,e[i].v);
	}
}

#define MID ((L+R)>>1)
#define LS (X<<1)
#define RS (X<<1|1)
int tr[240005],mx[240005];
inline void updt(int X){
	tr[X]=tr[LS]+tr[RS];
	mx[X]=Max(mx[LS],mx[RS]);
}
inline void chg(int X,int L,int R,int P,int V){
	if(L==R){
		tr[X]=mx[X]=V;
		return;
	}
	P<=MID?chg(LS,L,MID,P,V):chg(RS,MID+1,R,P,V);
	updt(X);
	return;
}
inline int qrySm(int X,int L,int R,int A,int B){
	if(L>=A&&R<=B){
		return tr[X];
	}
	if(R<A||L>B){
		return 0;
	}
	return qrySm(LS,L,MID,A,B)+qrySm(RS,MID+1,R,A,B);
}
inline int qryMx(int X,int L,int R,int A,int B){
	if(L>=A&&R<=B){
		return mx[X];
	}
	if(R<A||L>B){
		return -INF;
	}
	return Max(qryMx(LS,L,MID,A,B),qryMx(RS,MID+1,R,A,B));
}

void init(){
	scanf("%d",&n);
	int u,v;
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
	sz[0]=0;
	dfs0(1,0);
	dfs1(1,0,1);
	for(int i=1;i<=n;++i){
		scanf("%d",&val[i]);
		chg(1,1,n,dfn[i],val[i]);
	}
	char ch[6];
	int q,ans;
	scanf("%d",&q);
	for(int i=1;i<=q;++i){
		std::cin>>ch+1;
		scanf("%d%d",&u,&v);
		switch(ch[2]){
			case 'H':{
				val[u]=v;
				chg(1,1,n,dfn[u],v);
				break;
			}
			case 'S':{
				ans=0;
				while(tp[u]!=tp[v]){
					if(dep[tp[u]]<dep[tp[v]]){
						Swap(u,v);
					}
					ans+=qrySm(1,1,n,dfn[tp[u]],dfn[u]);
					u=fa[tp[u]];
				}
				if(dep[u]>dep[v]){
					Swap(u,v);
				}
				ans+=qrySm(1,1,n,dfn[u],dfn[v]);
				printf("%d\n",ans);
				break;
			}
			case 'M':{
				ans=-INF;
				while(tp[u]!=tp[v]){
					if(dep[tp[u]]<dep[tp[v]]){
						Swap(u,v);
					}
					ans=Max(ans,qryMx(1,1,n,dfn[tp[u]],dfn[u]));
					u=fa[tp[u]];
				}
				if(dep[u]>dep[v]){
					Swap(u,v);
				}
				ans=Max(ans,qryMx(1,1,n,dfn[u],dfn[v]));
				printf("%d\n",ans);
				break;
			}
		}
	}
} 

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

lp3950 部落冲突

LCT裸题。

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

inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
const int N=300005;
int fa[N],ch[N][2],rev[N]; 

inline void updt(int X){
	return;
}
inline void flp(int X){
	Swap(ch[X][0],ch[X][1]);
	rev[X]^=1;
}
inline void pshd(int X){
	if(rev[X]){
		flp(ch[X][0]),flp(ch[X][1]);
		rev[X]=0;
	}
}
inline int ntrt(int X){
	return ch[fa[X]][0]==X||ch[fa[X]][1]==X;
}
inline int fndD(int X){
	return ch[fa[X]][1]==X;
}
inline void splayOne(int X){
	int Y=fa[X],Z=fa[Y],D=fndD(X),D2=fndD(Y),C=ch[X][D^1];
	if(ntrt(Y)){
		ch[Z][D2]=X;
	}
	ch[X][D^1]=Y,ch[Y][D]=C;
	if(C){
		fa[C]=Y;
	}
	fa[Y]=X,fa[X]=Z;
	updt(Y),updt(X);
}
int st[N];
inline void splay(int X){
	int Y=X,Z=0;
	st[++Z]=Y;
	while(ntrt(Y)){
		Y=fa[Y],st[++Z]=Y;
	}
	while(Z){
		pshd(st[Z--]);
	}
	while(ntrt(X)){
		Y=fa[X],Z=fa[Y];
		if(ntrt(Y)){
			splayOne(fndD(X)^fndD(Y)?X:Y);
		}
		splayOne(X);
	}
}
inline void access(int X){
	for(int Y=0;X;Y=X,X=fa[X]){
		splay(X),ch[X][1]=Y,updt(X);
	}
}
inline void chgrt(int X){
	access(X),splay(X),flp(X);
}
inline int qryrt(int X){
	access(X),splay(X);
	while(ch[X][0]){
		pshd(X);
		X=ch[X][0];
	}
	splay(X);
	return X;
}
inline void split(int X,int Y){
	chgrt(X);
	access(Y),splay(Y);
}
inline bool cut(int X,int Y){
	split(X,Y);
	if(ch[Y][0]!=X||ch[X][1]){
		return 0;
	}
	fa[X]=ch[Y][0]=0;
	return 1;
}
inline bool link(int X,int Y){
	chgrt(X);
	if(qryrt(Y)==X){
		return 0;
	}
	fa[X]=Y;
	return 1;
}
int n,m;
int qu[N],qv[N],tp=0;
void init(){
	scanf("%d%d",&n,&m);
	int u,v;
	for(int i=1;i<=n;++i){
		scanf("%d%d",&u,&v);
		link(u,v);
	}
	char op[4];
	for(int i=1;i<=m;++i){
		cin>>op+1;
		switch(op[1]){
			case 'Q':{
				scanf("%d%d",&u,&v);
				puts(qryrt(u)==qryrt(v)?"Yes":"No");
				break;
			}
			case 'C':{
				scanf("%d%d",&u,&v);
				++tp;
				cut(qu[tp]=u,qv[tp]=v);
				break;
			}
			case 'U':{
				scanf("%d",&u);
				link(qu[u],qv[u]);
				break;
			}
		}
	}
}
int main(){
	init();
	return 0;
}

lp4582 FJOI2014 树的重心

两个重心的情况想想都麻。我们首先考虑一个重心的情况。 我们把 假设我们现在已经求出了每个子树的大小,那么我们发现,一棵子树有且仅有它的大小是对答案有影响的。所以我们可以预处理出每棵子树的不同大小的联通结构数,然后枚举子树大小瞎统计一下。 那么想想要怎么预处理。我们令\(f_{i,j}\)表示以\(i\)为根节点的子树中选取\(j\)个节点的联通子树的个数,\(g_{i,j}\)表示当前子树前\(i\)个儿子选取\(j\)个的联通子树的个数。 那么,根据定义我们有: $$g_{nw,j}=\sum_{k=1}^{j}g_{nw-1,k}f_{v,j-k}$$ $$f_{X,i}=g_{sum\_of\_sons,i-1}$$ 然后树形DP即可。 仔细想想,如果有两个重心,那么把两个重心的连边断开,两边的答案的统计是互不干扰的。 故而我们可以将原树分成两棵树统计答案,再把答案相乘。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define Fv(A,X) for(int A=h[X];A;A=e[A].nxt)

const int MOD=10007;
const int INF=0x3f3f3f3f;
inline int Max(int A,int B){
	return A>B?A:B;
}
inline int Min(int A,int B){
	return A<B?A:B;
}
struct ee{
	int v;
	int nxt;
}e[404];
int h[205],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 sz[205],mx[205],rt=0,rt2=0,totsz,Tid=0,n;
inline void dfs0(int X,int FA){
	sz[X]=1;mx[X]=0;
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		dfs0(e[i].v,X);
		sz[X]+=sz[e[i].v];
		mx[X]=Max(mx[X],sz[e[i].v]);
	}
	mx[X]=Max(mx[X],totsz-sz[X]);
	if(mx[X]<mx[rt]){
		rt=X;
		rt2=0;
	}else if(mx[X]==mx[rt]){
		rt2=X;
	}
}
int f[205][205],g[205][205];
inline void dfs1(int X,int FA){
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		dfs1(e[i].v,X);
	}
	for(int i=0;i<=n;++i){
		for(int j=0;j<=n;++j){
			g[i][j]=0;
		}
	}
	f[X][1]=f[X][0]=g[0][0]=sz[X]=1;
	int nw=1;
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		sz[X]+=sz[e[i].v];
		for(int j=0;j<=sz[X];++j){
			for(int k=0;k<=j;++k){
				g[nw][j]=(g[nw][j]+g[nw-1][j-k]*f[e[i].v][k]%MOD)%MOD;
			}
		}
		++nw;
	}
	--nw;
	for(int i=1;i<=sz[X];++i){
		f[X][i]=g[nw][i-1];
	}
}
int ans=0;
inline void calc1(){
	ans=1;
	for(int i=0;i<=n;++i){
		sz[i]=0;
		for(int j=0;j<=n;++j){
			f[i][j]=0;
		}
	}
	dfs1(rt,0);
	for(int i=2;i<=n;++i){
		for(int j=0;j<=n;++j){
			for(int k=0;k<=n;++k){
				g[j][k]=0;
			}
		}
		g[0][0]=1;int nw=1;sz[rt]=1;
		Fv(E,rt){
			sz[rt]+=sz[e[E].v];
			for(int j=0;j<=Min(i-1,sz[rt]);++j){
				for(int k=0;k<=j;++k){
					if(2*k>=i){
						break;
					}
					g[nw][j]=(g[nw][j]+g[nw-1][j-k]*f[e[E].v][k]%MOD)%MOD;
				}
			}
			++nw;
		}
		--nw;
		ans=(ans+g[nw][i-1])%MOD;
	}
}
inline void calc2(){
	for(int i=0;i<=n;++i){
		sz[i]=0;
		for(int j=0;j<=n;++j){
			f[i][j]=0;
		}
	}
	dfs1(rt,rt2);dfs1(rt2,rt);
	ans=0;
	for(int i=1;i<=n/2;++i){
		ans=(ans+f[rt][i]*f[rt2][i]%MOD)%MOD;
	}
}
void init(){
	scanf("%d",&n);
	int u,v;
	et=rt=rt2=0;
	for(int i=1;i<=n;++i){
		h[i]=sz[i]=0;
	}
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	totsz=n;
	mx[0]=INF;
	dfs0(1,0);
	if(!rt2){
		calc1();
	}else{
		calc2();
	}
	printf("Case %d: %d\n",Tid,ans);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		++Tid;
		init();
	}
	return 0;
}

lp4332 SHOI2014 三叉神经树

我们知道,每一个\(x_{i}\)各不相同。这启发我们,这一题的点将形成一棵树的结构。
仔细观察题目描述,我们发现,对于每一个点,它的修改影响到的有且仅有它的祖先。
我们不妨设一个点的权值为它的子节点们中信号为1的个数。那么根据题目给出的性质,当且仅当某个节点的权值为1的时候它的某个0子节点变成1,或者某个节点的权值为2的时候它的某个1子节点变成0,这个信号才会继续向上传输。容易发现,这样的传输覆盖的是且总是某一条竖直上下的全1/全2链。
详细地说,如果修改的叶子节点是0变成1,那么影响到的就是从它拉出的一条竖直向上的全1链以及这条链的父亲;如果修改的叶子节点是1变成0,那么影响到的就是从它拉出的一条竖直向上的全2链以及这条链的父亲。
因此,我们可以考虑在LCT剖出的实链上维护全1链以及全2链,然后修改的时候修改一整条链。这就完成了这题的要求。
但是仔细想想,我们会发现,维护全1链和全2链会显得很麻。所以我们不妨改为维护深度最深的非1节点和非2节点。对于将0变为1的操作,我们找到深度最深的非1节点,把它旋到根,然后修改即可,如果深度最深的非1节点不存在,那就意味着根节点也是1,那么答案就会发生变化;对于将1变为0的操作,如法炮制。
另外,由于这一题只有竖直上下的链的操作,所以我们甚至不需要写换根函数。当然,由于这一题没有分离和合并操作,因此,我们也不需要写分离和合并函数。

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

inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
const int N=500005;
int fa[N*3],ch[N*3][2],val[N*3],n1[N*3],n2[N*3],lzy[N*3];
//先看右子节点(下方)是否存在,再看本节点是否满足要求,然后看左子节点(上方)是否存在。 
inline void updt(int X){
	n1[X]=n1[ch[X][1]]?n1[ch[X][1]]:(val[X]==1?n1[ch[X][0]]:X);
	n2[X]=n2[ch[X][1]]?n2[ch[X][1]]:(val[X]==2?n2[ch[X][0]]:X);
}
inline void rnw(int X,int V){
	val[X]^=3,Swap(n1[X],n2[X]),lzy[X]+=V;
}
inline void pshd(int X){
	if(lzy[X]!=0){
		rnw(ch[X][0],lzy[X]);rnw(ch[X][1],lzy[X]);lzy[X]=0;
	}
}
inline bool fndD(int X){
	return ch[fa[X]][1]==X;
}
inline bool ntrt(int X){
	return ch[fa[X]][0]==X||ch[fa[X]][1]==X;
}
inline void splayOne(int X){
	int Y=fa[X],Z=fa[Y],D=fndD(X),D2=fndD(Y),C=ch[X][D^1];
	if(ntrt(Y)){
		ch[Z][D2]=X;
	}
	ch[X][D^1]=Y,ch[Y][D]=C;
	if(C){
		fa[C]=Y;
	}
	fa[Y]=X,fa[X]=Z;
	updt(Y),updt(X);
}
int st[N*3];
inline void splay(int X){
	int Y=X,Z=0;
	st[++Z]=Y;
	while(ntrt(Y)){
		Y=fa[Y];
		st[++Z]=Y;
	}
	while(Z){
		pshd(st[Z--]);
	} 
	while(ntrt(X)){
		Y=fa[X],Z=fa[Y];
		if(ntrt(Y)){
			splayOne(fndD(X)^fndD(Y)?X:Y);
		}
		splayOne(X);
	}
}
inline void access(int X){
	for(int Y=0;X;Y=X,X=fa[X]){
		splay(X),ch[X][1]=Y,updt(X);
	}
}
int n,Q,in[N*3];
std::queue<int> q;
void init(){
	scanf("%d",&n);
	int x,y,z;
	for(int i=1;i<=n;++i){
		scanf("%d%d%d",&x,&y,&z);
		fa[x]=fa[y]=fa[z]=i;
		in[i]=3;
	}
	for(int i=1;i<=(n<<1|1);++i){
		scanf("%d",&x);
		q.push(i+n);
		val[i+n]=x<<1;
	}
	while(!q.empty()){
		x=q.front();
		q.pop();
		if(x<=n){
			updt(x);
		}
		val[fa[x]]+=val[x]>>1;
		--in[fa[x]];
		if(!in[fa[x]]){
			q.push(fa[x]);
		}
	}
	scanf("%d",&Q);
	int tp,nwrt=val[1]>>1;
	for(int i=1;i<=Q;++i){
		scanf("%d",&x);
		tp=(val[x]^=2)-1;
		x=fa[x];
		access(x),splay(x);
		if((~tp?n1:n2)[x]){
			x=(~tp?n1:n2)[x];
			splay(x);
			rnw(ch[x][1],tp),updt(ch[x][1]);
			val[x]+=tp;updt(x);
		}else{
			rnw(x,tp);updt(x);
			nwrt^=1;
		}
		puts(nwrt?"1":"0");
	}
}
int main(){
	init();
	return 0;
}

lp1501 国家集训队 Tree II

如果没有操作2,就是树链剖分套线段树的裸题了。
但是操作2让这题变得麻烦了很多。
考虑LCT。我们知道LCT维护每一条链使用了平衡树。仔细观察这一题的信息,我们发现它们都是可以使用平衡树来维护的。
那么,我们就可以用LCT来维护这道题。
注意:处理信息的时候要先乘再加,否则可能会引起混乱。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define add(X,Y) (X=(X+Y)%MOD)
#define mlt(X,Y) (X=(1ll*X*Y%MOD))
using namespace std;

typedef long long ll;
inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
const int N=100005;
const ll MOD=51061;
int fa[N],ch[N][2],rev[N],sz[N];
ll sm[N],val[N],lzy1[N],lzy2[N];
inline void updt(int X){
	sz[X]=sz[ch[X][0]]+sz[ch[X][1]]+1;
	sm[X]=(sm[ch[X][0]]+sm[ch[X][1]]+val[X])%MOD;
}
inline void flp(int X){
	Swap(ch[X][0],ch[X][1]);
	rev[X]^=1;
}
inline void rnw1(int X,ll V){
	add(sm[X],1ll*V*sz[X]);
//	这里不应使用mlt,这是因为mlt会修改原数。 
	add(val[X],V);
	add(lzy1[X],V);
}
inline void rnw2(int X,ll V){
	mlt(sm[X],V);
	mlt(val[X],V);
	mlt(lzy2[X],V);
	mlt(lzy1[X],V);
}
inline void pshd(int X){
	if(lzy2[X]!=1){
		rnw2(ch[X][0],lzy2[X]);
		rnw2(ch[X][1],lzy2[X]);
		lzy2[X]=1;
	}
	if(lzy1[X]){
		rnw1(ch[X][0],lzy1[X]);
		rnw1(ch[X][1],lzy1[X]);
		lzy1[X]=0;
	}
	if(rev[X]){
		if(ch[X][0])flp(ch[X][0]);
		if(ch[X][1])flp(ch[X][1]);
		rev[X]=0;
	}
}
inline bool ntrt(int X){
	return ch[fa[X]][0]==X||ch[fa[X]][1]==X;
}
inline bool fndD(int X){
	return ch[fa[X]][1]==X;
}
inline void splayOne(int X){
	int Y=fa[X],Z=fa[Y],D=fndD(X),D2=fndD(Y),C=ch[X][D^1];
	if(ntrt(Y)){
		ch[Z][D2]=X;
	}
	ch[X][D^1]=Y,ch[Y][D]=C;
	if(C){
		fa[C]=Y;
	}
	fa[X]=Z,fa[Y]=X;
	updt(Y),updt(X);
}
int st[N];
inline void splay(int X){
	int Y=X,Z=0;
	st[++Z]=Y;
	while(ntrt(Y)){
		Y=fa[Y],st[++Z]=Y;
	}
	while(Z){
		pshd(st[Z--]);
	}
	while(ntrt(X)){
		Y=fa[X],Z=fa[Y];
		if(ntrt(Y)){
			splayOne(fndD(X)^fndD(Y)?X:Y);
		}
		splayOne(X);
	}
}
inline void access(int X){
	for(int Y=0;X;Y=X,X=fa[X]){
		splay(X),ch[X][1]=Y,updt(X);
	}
}
inline void chgrt(int X){
	access(X),splay(X),flp(X);
}
inline void split(int X,int Y){
	chgrt(X),access(Y),splay(Y);
}
//X在Y下方。
inline void link(int X,int Y){
	chgrt(X),fa[X]=Y;
} 
inline void cut(int X,int Y){
	split(X,Y),fa[X]=ch[Y][0]=0;
}

int n,q;
void init(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i){
		sm[i]=val[i]=lzy2[i]=1;
	}
	int X,Y,P,Q;
	ll V;
	for(int i=1;i<n;++i){
		scanf("%d%d",&X,&Y);
		link(X,Y);
	}
	char op[4];
	for(int i=1;i<=q;++i){
		std::cin>>op;
		scanf("%d%d",&X,&Y);
		switch(op[0]){
			case '+':{
				scanf("%lld",&V);
				split(X,Y);
				rnw1(Y,V);
				break;
			}
			case '-':{
				scanf("%d%d",&P,&Q);
				cut(X,Y);
				link(P,Q);
				break;
			}
			case '*':{
				scanf("%lld",&V);
				split(X,Y);
				rnw2(Y,V);
				break;
			}
			case '/':{
				split(X,Y);
				printf("%lld\n",sm[Y]);
				break;
			}
		}
	}
}
int main(){
	init();
	return 0;
}

lp3203 HNOI2010 弹飞绵羊

依照题意,我们发现,题目求的就是指定点到根的路径长度。
于是,我们对于每一个修改弹力的操作,都可以转化为断边和连边的操作。
那么,我们用Splay维护大小,就可以实现了。
注意:sz数组需要初始化。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
const int N=200005;
int fa[N],ch[N][2],sz[N];
inline void updt(int X){
	sz[X]=sz[ch[X][0]]+sz[ch[X][1]]+1;
}
inline bool fndD(int X){
	return ch[fa[X]][1]==X;
}
inline bool ntrt(int X){
	return ch[fa[X]][0]==X||ch[fa[X]][1]==X;
}
inline void splayOne(int X){
	int Y=fa[X],Z=fa[Y],D=fndD(X),D2=fndD(Y),C=ch[X][D^1];
	if(ntrt(Y)){
		ch[Z][D2]=X;
	}
	ch[X][D^1]=Y,ch[Y][D]=C;
	if(C){
		fa[C]=Y;
	}
	fa[Y]=X,fa[X]=Z;
	updt(Y),updt(X);
}
int st[N];
inline void splay(int X){
	int Y=X;
	while(ntrt(X)){
		Y=fa[X];
		if(ntrt(Y)){
			splayOne(fndD(X)^fndD(Y)?X:Y);
		}
		splayOne(X);
	} 
}
inline void access(int X){
	for(int Y=0;X;Y=X,X=fa[X]){
		splay(X),ch[X][1]=Y,updt(X);
	}
}
//令X在Y的上方。 
//由于这里保证存在有边,所以直接断边即可。 
inline void cut(int X){
	access(X),splay(X);
//	splay(Y);
//	fa[X]=ch[Y][0]=0;
	ch[X][0]=fa[ch[X][0]]=0;
}
inline void link(int X,int Y){
	fa[Y]=X;
	updt(X);
}
int a[N];
int n,q;
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		sz[i]=1;
//		记得初始化sz数组 
		scanf("%d",&a[i]);
		if(i+a[i]<=n){
			link(i+a[i],i);
		}
	}
	scanf("%d",&q);
	int X,Y,op;
	for(int i=1;i<=q;++i){
		scanf("%d",&op);
		if(op==1){
			scanf("%d",&X);++X;
			access(X),splay(X);
			printf("%d\n",sz[X]);
		}else{
			scanf("%d%d",&X,&Y);++X;
			if(X+a[X]<=n){
				cut(X);
			}
			access(X),splay(X);
			if(X+Y<=n){
				link(X+Y,X);
			}
			a[X]=Y;
		}
	}
}
int main(){
//	freopen("3203.in","r",stdin);
//	freopen("3203.myout","w",stdout);
	init();
	return 0;
}

lp2147 SDOI2008 洞穴勘测

维护链接和断开,LCT裸题,(看起来)也可以用按秩合并优化并查集。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>


inline void Swap(int &A,int &B){
	A^=B^=A^=B;
} 
const int N=10005;

int fa[N],ch[N][2],rev[N]; 

inline void updt(int X){
	return;
}
inline void flp(int X){
	Swap(ch[X][0],ch[X][1]);
	rev[X]^=1;
}
inline void pshd(int X){
	if(rev[X]){
		flp(ch[X][0]),flp(ch[X][1]);
		rev[X]=0;
	}
}
inline int ntrt(int X){
	return ch[fa[X]][0]==X||ch[fa[X]][1]==X;
}
inline int fndD(int X){
	return ch[fa[X]][1]==X;
}
inline void splayOne(int X){
	int Y=fa[X],Z=fa[Y],D=fndD(X),D2=fndD(Y),C=ch[X][D^1];
	if(ntrt(Y)){
		ch[Z][D2]=X;
	}
	ch[X][D^1]=Y,ch[Y][D]=C;
	if(C){
		fa[C]=Y;
	}
	fa[Y]=X,fa[X]=Z;
	updt(Y),updt(X);
}
int st[N];
inline void splay(int X){
	int Y=X,Z=0;
	st[++Z]=Y;
	while(ntrt(Y)){
		Y=fa[Y],st[++Z]=Y;
	}
	while(Z){
		pshd(st[Z--]);
	}
	while(ntrt(X)){
		Y=fa[X],Z=fa[Y];
		if(ntrt(Y)){
			splayOne(fndD(X)^fndD(Y)?X:Y);
		}
		splayOne(X);
	}
}
inline void access(int X){
	for(int Y=0;X;Y=X,X=fa[X]){
		splay(X),ch[X][1]=Y,updt(X);
	}
}
inline void chgrt(int X){
	access(X),splay(X),flp(X);
}
inline int qryrt(int X){
	access(X),splay(X);
	while(ch[X][0]){
		pshd(X);
		X=ch[X][0];
	}
	splay(X);
	return X;
}
inline void split(int X,int Y){
	chgrt(X);
	access(Y),splay(Y);
}
inline bool cut(int X,int Y){
	split(X,Y);
	if(ch[Y][0]!=X||ch[X][1]){
		return 0;
	}
	fa[X]=ch[Y][0]=0;
	return 1;
}
inline bool link(int X,int Y){
	chgrt(X);
	if(qryrt(Y)==X){
		return 0;
	}
	fa[X]=Y;
	return 1;
}
int n,q;
char op[20]; 
void init(){
	scanf("%d%d",&n,&q);
	int x,y;
	for(int i=1;i<=q;++i){
		std::cin>>op;
		scanf("%d%d",&x,&y);
		switch(op[0]){
			case 'C':{
				link(x,y);
				break;
			}
			case 'D':{
				cut(x,y);
				break;
			}
			case 'Q':{
				chgrt(x);
				puts(qryrt(y)==x?"Yes":"No");
				break;
			}
		}
	} 
}
int main(){
	init();
	return 0;
}

lp3690 【模板】Link Cut Tree (动态树)

树链剖分有多种方法。例如以重量为关键字的重链剖分,以长度为关键字的长链剖分。
而LCT(Link-Cut-Tree)就是一种特殊的利用Splay维护树的剖分结构的算法。
我们称一棵树上连接同一条链的边为实边,连接不同的链的边为虚边,那么这棵树就被分成了许多链。我们称这种剖分方法为实链剖分。
由于实链剖分的虚实是可以动态变化的,因此它具有很多用途。比如动态维护连通性、换根等等操作。
下面我们大致地考虑如何用Splay维护LCT实现实链剖分。

对于实链剖分剖出的每一条链,它总是一条自上往下的链。形式化地说,链中的节点的深度连续且各不相同。
对于原树剖分出的每一条链,我们建一棵Splay维护这棵树。每个点在Splay上的权值是这个点在原树上的深度。这样,无论Splay的结构如何改变,这棵Splay始终维护的是一条链。
对于每棵Splay,我们设它的父亲为整个链的最顶端节点的父亲。
对于原树中的一条实边,由于它位于Splay中,所以它对应着Splay中的一组前驱-后继关系。
对于原树中的一条虚边,它连接的两个节点中的一个节点对应的是两条链之间的连接。位于较下方的那条链对应的Splay的父亲显然指向的是位于较上方的那个节点;而位于较上方的那个节点却不必指向位于较下方的那个节点。这条性质被称为「认父不认子」。

access(Y)
显然,在维护信息的时候,原图上的实链结构并不总是能让我们满意。这时候我们需要从根到Y将树上的某一条竖直的链变成实链,并且不改变它原来的性质。这要怎么做呢?
我们设计一个access(接驳)函数,来完成这个过程。
对于路径上的第一条需要变成实边的虚边,我们是容易找到的——这便是Y所在的Splay的根节点连向其父亲的边。当然,这需要我们将Y旋到其所在的Splay的根。
我们将Y所在的Splay的根的父亲A也旋到其所在的Splay的根,那么它原本的实子链在Splay上正好是它的右子树。所以,我们将它的右子节点改为Y节点。那么,A-Y是已经成为了一条满足操作要求的实链,于是问题就转化为了将A-X转化为实链的子问题。
于是依次向上修改即可。

chgrt(X)
在实际操作中,我们操作的链并不总是从某个节点到根的一条链。这时候我们需要换根操作。
首先,我们将根节点到将要成为根的节点X置于同一条实链上——这可以通过access来达成。
在access后,X便是X所在的Splay中原树深度最浅的节点,也就是最右的节点。这时候,倘若将X旋到其所在的Splay的根,然后翻转X,那么整条链就上下倒转了。

qryrt(X)
在确认连通性的时候,我们需要询问某个点X所在的树的根。
显然,这要求的就是access之后X所在的Splay的最左端节点。

split(X,Y)
在处理具体操作的时候,我们可能会需要将某一条链摘离出来。
如果它们连通,只需要换根到一者,然后access另一者即可。

link(X,Y)
从X到Y连边。
方法很简单,将X作为它所在的树的根,然后直接连一条虚边即可。

cut(X,Y)
删除X和Y之间的边。
倘若保证X和Y之间本来是有连边的,那倒是容易了,直接split出来之后分离两者即可。
现在我们需要考虑两者没有连边的情况。
首先,我们将X变为根,然后寻找Y的根。
考虑Splay操作的影响,我们知道,这样操作之后,在Splay树上,Y节点一定在X节点的右儿子的位置。
在这种情况下,如果Y的根不是X,那么显然两者不连通。如果Y不是X的后继,那么显然两者之间有隔着点,也就不是父子关系。

注意:
一:关于Splay:在LCT中,我习惯使用的SplayOne的方法并不是特别有效,这是因为在LCT中存在虚边。
二:在旋转的时候,需要特别注意判断C是空节点和Y是根节点的情况。在这两种情况下有两句话是不应该写的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>

inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
const int N=300005;
int fa[N],ch[N][2],rev[N],sm[N],val[N];

inline bool isrt(int X){
	return ch[fa[X]][0]!=X&&ch[fa[X]][1]!=X;
}
inline void updt(int X){
	sm[X]=sm[ch[X][0]]^sm[ch[X][1]]^val[X];
}
inline void flp(int X){
	Swap(ch[X][0],ch[X][1]);
	rev[X]^=1;
}
inline void pshd(int X){
	if(rev[X]){
		if(ch[X][0]){
			flp(ch[X][0]);
		}
		if(ch[X][1]){
			flp(ch[X][1]);
		}
		rev[X]=0;
	}
}
inline int fndD(int X){
	return ch[fa[X]][1]==X;
}
inline void splayOne(int X){
//	int D=fndD(X),D2=fndD(fa[X]);
//	fa[ch[X][D^1]]=fa[X],ch[fa[X]][D]=ch[X][D^1];
//	ch[X][D^1]=fa[X],fa[X]=fa[ch[X][D^1]];
//	ch[fa[X]][D2]=X,fa[ch[X][D^1]]=X;
//	updt(ch[X][D^1]),updt(X);
//	在LCT中,我习惯使用的SplayOne的方法并不是特别有效,这是因为在LCT中存在虚边。
	int Y=fa[X],Z=fa[Y],D=fndD(X),D2=fndD(fa[X]),C=ch[X][D^1];
	if(!isrt(Y)){
		ch[Z][D2]=X;
	}
	ch[X][D^1]=Y,ch[Y][D]=C;
	if(C){
		fa[C]=Y;
	}
	fa[X]=Z,fa[Y]=X;
	updt(Y),updt(X);
}
int st[N];
inline void splay(int X){
	int Y=X,Z=0;
	st[++Z]=Y;
	while(!isrt(Y)){
		Y=fa[Y];
		st[++Z]=Y;
	}
	while(Z){
		pshd(st[Z--]);
	}
	while(!isrt(X)){
		Y=fa[X],Z=fa[Y];
		if(!isrt(Y)){
			splayOne((fndD(X)^fndD(Y))?X:Y);
		}
		splayOne(X);
	}
}
inline void access(int X){
	for(int Y=0;X;Y=X,X=fa[X]){
		splay(X),ch[X][1]=Y,updt(X);
	}
}
inline void chgrt(int X){
	access(X),splay(X),flp(X);
}
inline int qryrt(int X){
	access(X),splay(X);
	while(ch[X][0]){
		pshd(X);
		X=ch[X][0];
	}
	splay(X);
	return X;
} 
inline void split(int X,int Y){
	chgrt(X);
	access(Y),splay(Y);
} 
inline bool link(int X,int Y){
	chgrt(X);
	if(qryrt(Y)==X){
		return 0;
	}
	fa[X]=Y;
	return 1;
}
inline bool cut(int X,int Y){
	split(X,Y);
	if(ch[Y][0]!=X||ch[X][1]){
		return 0;
	}
	fa[X]=ch[Y][0]=0;
	return 1;
}
int n,q;
void init(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i){
		scanf("%d",&val[i]);
		sm[i]=val[i];
	}
	int op,x,y;
	for(int i=1;i<=q;++i){
		scanf("%d%d%d",&op,&x,&y);
		switch(op){
			case 0:{
				split(x,y);
				printf("%d\n",sm[y]);
				break;
			}
			case 1:{
				link(x,y);
				break;
			}
			case 2:{
				cut(x,y);
				break;
			}
			case 3:{
				splay(x);
				val[x]=y;
				updt(x);
				break;
			}
		}
	}
}
int main(){
	init();
	return 0;
}