【模板】动态树（Link Cut Tree）

Link-cut-tree是一种维护动态森林的数据结构，在需要动态加边/删边的时候就需要LCT来维护。

Link-cut-tree的核心是轻重链划分，每条重链用一颗splay来维护。

点击查看代码 
#include<bits/stdc++.h>

using namespace std;

int n,m;

struct LCT{

	int son[2][100005],fa[100005],siz[100005],val[100005];

	inline void pushup(int x){siz[x]=siz[son[0][x]]^siz[son[1][x]]^val[x];}

	bool rev[100005];

	inline void pushdown(int x){

		if(!rev[x])return ;

    	rev[son[0][x]]^=1;rev[son[1][x]]^=1;

    	swap(son[0][x],son[1][x]);rev[x]=0;

	}

	inline bool isroot(int x){

		return !(son[0][fa[x]]==x||son[1][fa[x]]==x);

	}

	inline void rotate(int x){

		int y=fa[x],z=fa[y];

		if(!isroot(y))son[y==son[1][z]][z]=x;

		bool is=(son[1][y]==x);

		son[is][y]=son[!is][x];fa[son[!is][x]]=y;

		son[!is][x]=y;fa[y]=x;fa[x]=z;pushup(y);pushup(x);

	}

	int stk[100005],top;

	inline void splay(int x){

		stk[++top]=x;

    	for(int i=x;!isroot(i);i=fa[i])stk[++top]=fa[i];

     	while(top)pushdown(stk[top--]);

    	while(!isroot(x)){

	     	int y=fa[x],z=fa[y];//cout<<x<<" "<<y<<" "<<z<<endl;

	    	if(!isroot(y)){

		    	if((son[1][y]==x)^(son[1][z]==y))rotate(x);

	     		else rotate(y);

	    	}rotate(x);

    	}

	}

	inline void access(int x){

		for(int i=0;x;i=x,x=fa[x])splay(x),son[1][x]=i,pushup(x);

	}

	inline void makert(int x){

		access(x);splay(x);rev[x]^=1;

	}

	inline int find(int x){

		access(x);splay(x);while(son[0][x])x=son[0][x];

		return x;

	}

	inline void link(int x,int y){

		if(find(x)==find(y))return ;

		makert(x);fa[x]=y;

	}

	inline void split(int x,int y){

		makert(x);access(y);splay(y);

	}

	inline void cut(int x,int y){

		split(x,y);

		if(son[0][y]==x&&son[1][x]==0)son[0][y]=fa[x]=0;

	}

}T;

int main(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)scanf("%d",&T.val[i]),T.siz[i]=T.val[i];

	while(m--){

		int op,x,y;

		scanf("%d%d%d",&op,&x,&y);

		if(op==0)T.split(x,y),printf("%d\n",T.siz[y]);

		if(op==1)T.link(x,y);

		if(op==2)T.cut(x,y);

		if(op==3)T.makert(x),T.val[x]=y,T.pushup(x);

	}

	return 0;

}

【模板】最近公共祖先（LCA）

\(LCT\) 也是一种求 \(lca\) 的方法法，而且好像比倍增快

点击查看代码 
#include<bits/stdc++.h>

using namespace std;

int n,m,s;

int son[2][500005],fa[500005];

bool rev[500005];

inline void down(int x){

	if(rev[x]){

		swap(son[0][x],son[1][x]);

		rev[son[0][x]]^=1;rev[son[1][x]]^=1;

	}rev[x]=0;

}

inline bool isroot(int x){

	return son[1][fa[x]]!=x&&son[0][fa[x]]!=x;

}

inline void rotate(int x){

	int y=fa[x],z=fa[y];

	if(!isroot(y))son[y==son[1][z]][z]=x;

	bool is=(son[1][y]==x);

	son[is][y]=son[!is][x];fa[son[!is][x]]=y;

	son[!is][x]=y;fa[x]=z;fa[y]=x;

}

int stk[500005],top;

inline void splay(int x){

	stk[++top]=x;

	for(int y=x;!isroot(y);y=fa[y])stk[++top]=fa[y];

	while(top)down(stk[top--]);

	while(!isroot(x)){

		int y=fa[x],z=fa[y];

		if(!isroot(y)){

			if((son[1][y]==x)^(son[1][z]==y))rotate(x);

			else rotate(y);

		}rotate(x);

	}

}

inline int access(int x){

	int i=0;

	for(;x;i=x,x=fa[x])splay(x),son[1][x]=i;

	return i;

}

inline void makert(int x){

	access(x);splay(x);rev[x]^=1;

}

inline void link(int x,int y){

	makert(x);fa[x]=y;

}

inline void split(int x,int y){

	makert(x);access(y);splay(y);

}

inline void cut(int x,int y){

	split(x,y);son[0][y]=fa[x]=0;

}

inline int find(int x){

	access(x);splay(x);while(son[0][x])x=son[0][x];

	return x;

}

inline int lca(int x,int y){

	access(x);splay(x);

	return access(y);

}

int main(){

	scanf("%d%d%d",&n,&m,&s);

	son[0][0]=son[1][0]=-1;

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

		int x,y;scanf("%d%d",&x,&y);

		link(x,y);

	}makert(s);

	while(m--){

		int x,y;

		scanf("%d%d",&x,&y);

		printf("%d\n",lca(x,y));

	}

	return 0;

}

[SDOI2008] 洞穴勘测

又是一个模板，不过好像可以暴力水过去

点击查看代码 
#include<bits/stdc++.h>

using namespace std;

int n,m;

int son[2][10005],fa[10005];

bool rev[10005];

inline void down(int x){

	if(rev[x]){

		swap(son[0][x],son[1][x]);

		rev[son[0][x]]^=1;rev[son[1][x]]^=1;

	}rev[x]=0;

}

inline bool isroot(int x){

	return son[1][fa[x]]!=x&&son[0][fa[x]]!=x;

}

inline void rotate(int x){

	int y=fa[x],z=fa[y];

	if(!isroot(y))son[y==son[1][z]][z]=x;

	bool is=(son[1][y]==x);

	son[is][y]=son[!is][x];fa[son[!is][x]]=y;

	son[!is][x]=y;fa[x]=z;fa[y]=x;

}

int stk[10005],top;

inline void splay(int x){

	stk[++top]=x;

	for(int y=x;!isroot(y);y=fa[y])stk[++top]=fa[y];

	while(top)down(stk[top--]);

	while(!isroot(x)){

		int y=fa[x],z=fa[y];

		if(!isroot(y)){

			if((son[1][y]==x)^(son[1][z]==y))rotate(x);

			else rotate(y);

		}rotate(x);

	}

}

inline void access(int x){

	for(int i=0;x;i=x,x=fa[x])splay(x),son[1][x]=i;

}

inline void makert(int x){

	access(x);splay(x);rev[x]^=1;

}

inline void link(int x,int y){

	makert(x);fa[x]=y;

}

inline void split(int x,int y){

	makert(x);access(y);splay(y);

}

inline void cut(int x,int y){

	split(x,y);son[0][y]=fa[x]=0;

}

inline int find(int x){

	access(x);splay(x);while(son[0][x])x=son[0][x];

	return x;

}

char op[15];

int main(){

	scanf("%d%d",&n,&m);

	son[0][0]=son[1][0]=-1;

	while(m--){

		int x,y;

		scanf("%s%d%d",op,&x,&y);

		if(op[0]=='Q')puts(find(x)==find(y)?"Yes":"No");

		if(op[0]=='C')link(x,y);

		if(op[0]=='D')cut(x,y);

	}

	return 0;

}

[NOI2014] 魔法森林

\(LCT\) 想维护边上信息，只需对每条边开一个点出来即可

点击查看代码 
#include<bits/stdc++.h>

using namespace std;

int n,m;

int son[2][200005],fa[200005];

bool rev[200005];

struct node{

	int x,y,a,b,id;

	node(){}

	node(int _x,int _y,int _a,int _b,int _id){

		x=_x;y=_y;a=_a;b=_b;id=_id;

	}

	inline bool operator <(const node &b)const{

		return a<b.a;

	}

}val[200005],sm[200005];

inline node cmp(node x,node y){

	return x.b<y.b?y:x;

}

inline void pushup(int x){

	sm[x]=val[x];

	sm[x]=cmp(sm[x],sm[son[0][x]]);

	sm[x]=cmp(sm[x],sm[son[1][x]]);

}

inline void down(int x){

	if(rev[x]){

		swap(son[0][x],son[1][x]);

		rev[son[0][x]]^=1;rev[son[1][x]]^=1;

	}rev[x]=0;

}

inline bool isroot(int x){

	return son[0][fa[x]]!=x&&son[1][fa[x]]!=x;

}

inline void rotate(int x){

	int y=fa[x],z=fa[y];

	if(!isroot(y))son[son[1][z]==y][z]=x;

	bool is=(son[1][y]==x);

	son[is][y]=son[!is][x];fa[son[!is][x]]=y;

	son[!is][x]=y;fa[x]=z;fa[y]=x;pushup(y);pushup(x);

}

int stk[200005],top;

inline void splay(int x){

	stk[++top]=x;

	for(int i=x;!isroot(i);i=fa[i])stk[++top]=fa[i];

	while(top)down(stk[top--]);

	while(!isroot(x)){

		int y=fa[x],z=fa[y];

		if(!isroot(y)){

			if((son[1][y]==x)^(son[1][z]==y))rotate(x);

			else rotate(y);

		}rotate(x);

	}

}

inline void access(int x){

	for(int i=0;x;i=x,x=fa[x])splay(x),son[1][x]=i,pushup(x);

}

inline void makert(int x){

	access(x);splay(x);rev[x]^=1;

}

inline void link(int x,int y){

	makert(x);splay(x);fa[x]=y;

}

inline void cut(int x,int y){

	makert(x);splay(x);access(y);splay(y);

	son[0][y]=fa[x]=0;pushup(y);

}

inline node select(int x,int y){

	makert(x);splay(x);access(y);splay(y);

	return sm[y];

}

inline int find(int x){

	access(x);splay(x);for(down(x);son[0][x];down(x))x=son[0][x];

	return x;

}

vector<node> vec;

int ans=2e9;

int main(){

	scanf("%d%d",&n,&m);

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

		int x,y,a,b;

		scanf("%d%d%d%d",&x,&y,&a,&b);if(x==y)continue;

		val[n+i]=node(x,y,a,b,i+n);vec.push_back(val[n+i]);

	}son[0][0]=son[1][0]=-1;

	sort(vec.begin(),vec.end());

	for(auto it:vec){

		if(find(it.x)!=find(it.y))link(it.id,it.x),link(it.id,it.y);

		else {

			node u=select(it.x,it.y);

			if(u.b>it.b){

				cut(u.x,u.id);cut(u.y,u.id);

				link(it.x,it.id);link(it.y,it.id);

			}

		}

		if(find(1)==find(n)){

			ans=min(ans,it.a+select(1,n).b);

		}

	}

	printf("%d",ans==2e9?-1:ans);

	return 0;

}

[BJOI2014]大融合

把 \(access\) 改一下，再注意一下更新时 \(splay\) 的形态，就可以用\(LCT\) 维护虚子树信息

点击查看代码 
#include<bits/stdc++.h>

using namespace std;

int n,q;

int son[2][100005],fa[100005],siz[100005],val[100005];

bool rev[100005];

inline void pushup(int x){

	siz[x]=siz[son[0][x]]+val[x]+siz[son[1][x]];

}

inline void down(int x){

	if(rev[x]){

		swap(son[0][x],son[1][x]);

		rev[son[0][x]]^=1;rev[son[1][x]]^=1;

	}rev[x]=0;

}

inline bool isroot(int x){

	return son[1][fa[x]]!=x&&son[0][fa[x]]!=x;

}

inline void rotate(int x){

	int y=fa[x],z=fa[y];

	if(!isroot(y))son[son[1][z]==y][z]=x;

	bool is=(son[1][y]==x);

	son[is][y]=son[!is][x];fa[son[!is][x]]=y;

	son[!is][x]=y;fa[x]=z;fa[y]=x;pushup(y);pushup(x);

}

int stk[100005],top;

inline void splay(int x){

	stk[++top]=x;

	for(int i=x;!isroot(i);i=fa[i])stk[++top]=fa[i];

	while(top)down(stk[top--]);

	while(!isroot(x)){

		int y=fa[x],z=fa[y];

		if(!isroot(y)){

			if((son[1][y]==x)^(son[1][z]==y))rotate(x);

			else rotate(y);

		}rotate(x);

	}

}

inline void access(int x){

	for(int i=0;x;i=x,x=fa[x]){

		splay(x);val[x]+=siz[son[1][x]];

		son[1][x]=i;val[x]-=siz[i];pushup(x);

	}

}

inline void makert(int x){

	access(x);splay(x);rev[x]^=1;

}

inline void link(int x,int y){

	makert(x);makert(y);fa[x]=y;

	val[y]+=siz[x];pushup(y);

}

inline void cut(int x,int y){

	makert(x);access(y);splay(y);

	son[0][y]=fa[x]=0;pushup(x);pushup(y);(x);makert(y);

}

inline int query(int x){

	access(x);splay(x);

	return siz[x];

}

char op[2];

int main(){

	scanf("%d%d",&n,&q);

	for(int i=1;i<=n;i++)siz[i]=val[i]=1;

	while(q--){

		int x,y;

		scanf("%s%d%d",op,&x,&y);

		if(op[0]=='A')link(x,y);

		else {

			cut(y,x);

			printf("%lld\n",1ll*query(x)*query(y));

			link(x,y);

		}

	}

	return 0;

}

【模板】 "动态DP"&动态树分治(加强版)

对于静态树，可以将 \(splay\) 静态化为一颗普通 \(BST\) ，称为 “全局平衡二叉树”

点击查看代码 
#include<bits/stdc++.h>

#pragma GCC optimize(2)

#pragma GCC optimize(3)

#pragma GCC optimize("Ofast")

#pragma GCC optimize("inline")

using namespace std;

int n,m;

const int SIZE=(1<<21)+1;

char ibuf[SIZE],*iS=ibuf,*iT=ibuf;

#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),(iS==iT?EOF:*iS++)):*iS++)

template <class T>

void read(T &x){

    int f=0;x=0;char c=gc();

    while(!isdigit(c)) f|=c=='-',c=gc();

    while(isdigit(c)) x=x*10+c-'0',c=gc();

    if(f) x=-x;

}

int ver[2000005],ne[2000005],head[1000005],cnt;

inline void link(int x,int y){

	ver[++cnt]=y;

	ne[cnt]=head[x];

	head[x]=cnt;

}

int siz[1000005],son[1000005];

void dfs(int x,int fi){

	siz[x]=1;

	for(int i=head[x];i;i=ne[i]){

		int u=ver[i];

		if(u==fi)continue;

		dfs(u,x);siz[x]+=siz[u];

		if(siz[u]>siz[son[x]])son[x]=u;

	}

}

struct mat{

	int a[2][2];

	mat(int _x=0,int _y=0){a[0][0]=a[1][1]=_x;a[0][1]=a[1][0]=_y;}

	inline int* operator [](int t){

		return a[t];

	}

	inline mat operator *(mat &b){

		mat res(-1e9,-1e9);

		for(int i=0;i<2;i++){

			for(int t=0;t<2;t++){

				for(int j=0;j<2;j++)res[i][j]=max(res[i][j],a[i][t]+b[t][j]);

			}

		}return res;

	}

	inline mat operator +(mat &b){

		mat res=*this;int tmp=max(b[0][0],b[1][0]);

		res[0][0]+=tmp;res[0][1]+=tmp;res[1][0]+=b[0][0];

		return res;

	}

	inline mat operator -(mat &b){

		mat res=*this;int tmp=max(b[0][0],b[1][0]);

		res[0][0]-=tmp;res[0][1]-=tmp;res[1][0]-=b[0][0];

		return res;

	}

}val[1000005],tree[1000005];

int le[1000005],ri[1000005],stk[1000005],top;

inline void pushup(int x){

	tree[x]=tree[le[x]]*val[x]*tree[ri[x]];

}

int fa[1000005];

int build(int x,int l,int r){

	int all=0,sum=0;

	for(int i=l;i<=r;i++)all+=siz[stk[i]]-siz[son[stk[i]]];

	for(int i=l;i<=r;i++){

		sum+=siz[stk[i]]-siz[son[stk[i]]];

		if(sum>=all/2){

			le[stk[i]]=build(stk[i],l,i-1);ri[stk[i]]=build(stk[i],i+1,r);fa[stk[i]]=x;

			pushup(stk[i]);return stk[i];

		}

	}return 0;

}

bool vis[1000005];

int solve(int x,int fi=0){

	for(int y=x;y;y=son[y])vis[y]=1;

	for(int y=x;y;y=son[y]){

		for(int i=head[y];i;i=ne[i]){

			int u=ver[i];

			if(!vis[u]){

				int z=solve(u,y);

				val[y]=val[y]+tree[z];

			}

		}

	}top=0;

	for(int y=x;y;y=son[y])stk[++top]=y;

	return build(fi,1,top);

}

int a[1000005];

inline bool isroot(int x){

	return le[fa[x]]!=x&&ri[fa[x]]!=x;

}

inline void update(int x,int y){

	val[x][1][0]+=y-a[x];a[x]=y;

	while(x){

		if(isroot(x)&&fa[x])val[fa[x]]=val[fa[x]]-tree[x];

		pushup(x);

		if(isroot(x)&&fa[x])val[fa[x]]=val[fa[x]]+tree[x];

		x=fa[x];

	}

}

int ans,rt;

int main(){

	read(n);read(m);

	for(int i=1;i<=n;i++)read(a[i]);

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

		int x,y;read(x);read(y);

		link(x,y);link(y,x);

	}

	dfs(1,1);

	val[0]=tree[0]=mat(0,-1e9);

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

		val[i][1][0]=a[i];

		val[i][1][1]=-1e9;

	}rt=solve(1,0);

	while(m--){

		int x,y;read(x);read(y);x^=ans;

		update(x,y);

		printf("%d\n",ans=max(tree[rt][0][0],tree[rt][1][0]));

	}

	return 0;

}

#1220. 地平线

由于 \(splay\) 有均摊分析，最好每访问一个节点就 \(splay\) 一次，而不是只 \(splay\) 需要变为根的节点，保证复杂度

点击查看代码 
#include<bits/stdc++.h>

using namespace std;

int n,m,q,cnt;

int mpx[3000005],mpy[3000005];

int son[2][3000005],fa[3000005];

inline bool isroot(int x){

	return son[0][fa[x]]!=x&&son[1][fa[x]]!=x;

}

inline void rotate(int x){

	int y=fa[x],z=fa[y];

	if(!isroot(y))son[son[1][z]==y][z]=x;

	bool is=(son[1][y]==x);

	son[is][y]=son[!is][x];fa[son[is][y]]=y;

	son[!is][x]=y;fa[y]=x;fa[x]=z;

}

inline void splay(int x){

	while(!isroot(x)){

		int y=fa[x],z=fa[y];

		if(!isroot(y)){

			if((son[1][y]==x)^(son[1][z]==y))rotate(x);

			else rotate(y);

		}rotate(x);

	}

}

inline void access(int x){

	for(int i=0;x;i=x,x=fa[x])splay(x),son[1][x]=i;

}

inline void cut(int x){

	access(x);splay(x);fa[son[0][x]]=0;son[0][x]=0;

}

inline int findrt(int x){

	access(x);splay(x);

	while(son[0][x])x=son[0][x];splay(x);

	return x;

}

inline void link(int x,int y){

//	cout<<"link ("<<mpx[x]<<" "<<mpy[x]<<") ("<<mpx[y]<<" "<<mpy[y]<<")\n";

	access(x);splay(x);fa[x]=y;

}

int dsu[3000005];

inline void update(int x,int y){

	int F=findrt(x);cut(x);

	if(dsu[F]&&findrt(dsu[F])!=F)link(F,dsu[F]);

	dsu[x]=y;

	if(findrt(y)!=x)link(x,y);

}

vector<int> mp[1000005];

char s[1000005],op[3];

int main(){

	scanf("%d%d%d",&n,&m,&q);

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

		mp[i].resize(m+2);

		for(int j=0;j<=m+1;j++){

			mp[i][j]=++cnt;

			if(i==0||i==n+1||j==0||j==m+1)mpx[cnt]=i,mpy[cnt]=j;

			else mpx[cnt]=-1,mpy[cnt]=-1;

		}

	}

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

		scanf("%s",s+1);

		for(int j=1;j<=m;j++){

			if(s[j]=='>')update(mp[i][j],mp[i][j+1]);

			else if(s[j]=='<')update(mp[i][j],mp[i][j-1]);

			else update(mp[i][j],mp[i-1][j]);

		}

	}

	while(q--){

		int x,y;char c[2];

		scanf("%s%d%d",op,&x,&y);

		if(op[0]=='q'){

			int F=findrt(mp[x][y]);

			printf("%d %d\n",mpx[F],mpy[F]);

		}else {

			scanf("%s",c);

			if(c[0]=='>')update(mp[x][y],mp[x][y+1]);

			else if(c[0]=='<')update(mp[x][y],mp[x][y-1]);

			else if(c[0]=='^')update(mp[x][y],mp[x-1][y]);

		}

	}

	return 0;

}

最新文章

  1. 【BZOJ-1017】魔兽地图DotR 树形DP + 背包
  2. copyallwaterdata
  3. ankhSVN安装后，VS2010使用
  4. git push
  5. 技术贴 本地代码与svn关联教程 svn upgrade问题解决
  6. hdu 逆袭指数
  7. poj3185 高斯消元
  8. python3学习笔记10(迭代器和生成器)
  9. JavaScript的 sourcemap 的理解
  10. java 中异常处理示例并捕获完整异常内容
  11. 第八届蓝桥杯国赛java B组第三题
  12. python去掉字符串中空格的方法
  13. zepto点透解决思路
  14. Cetus
  15. CLR基础
  16. Python操作redis字符串(String)详解 (三)
  17. 阿里云ftp连接遇到的错误，entering passive mode失败（一个并不成熟的产品？）
  18. 【转】Java虚拟机类型卸载和类型更新解析
  19. django 使用多说 评论系统
  20. ionic2如何调用百度地图

热门文章

  1. IDEA Debug过程中使用Drop Frame或Reset Frame实现操作回退
  2. 自定义制作SpringBoot启动图案
  3. Ansible Notes: module: get_facts
  4. ValidForm5.3.2 忽略表单项校验详解
  5. netty系列之:netty中的核心解码器json
  6. 不懂 Zookeeper？来看看这篇文章
  7. dubbo发送过程编码失败，会唤醒发送线程吗？
  8. Zookeeper安装学习（一）
  9. TyepScript学习
  10. Node.js连接MySQL数据库报错