动态树 — Euler_Tour

一般提到动态树，我们会不约而同的想到 LCT，这算是比较通用，实用，能力较为广泛的一种写法了。当然，掌握 LCT 就需要熟悉掌握 Splay 和各种操作和知识。ETT（中文常用称呼：欧拉游览树）是一种及其睿智且暴力，可以用暴力数据结构维护的一种除了能胜任普通动态树的 Link & Cut 操作还可以支持换子树操作（此操作 LCT 无法完成）的动态树。

大家对这括号序很熟悉吧，如：

其括号序为：1 2 5 5 6 6 2 3 3 4 7 8 8 7 4 1。

括号序其实是一个父亲包含儿子的一种树的顺序。

然后我们看一下，如果把 4 的子树移给 3 会怎样？如图：

原图括号序：1 2 5 5 6 6 2 3 3 4 7 8 8 7 4 1

后者括号序：1 2 5 5 6 6 2 3 7 8 8 7 3 4 4 1

可以发现，7 8 8 7 平移到了 3 的后面，而 4 合拢。这就是所谓换子树操作（同样可以用于 Link & Cut 操作）。现在只需要一个数据结构可以做到区间平移且维护一些值，众大佬肯定会说用 Splay，其确实效率很高，不过这里用块状链表维护会简单很多，对于一些数据低于的题目都可以码得很快。

那怎么维护点到根的信息呢？

其实仔细想想，DFS 序也可以达到平移的效果，那么为什么需要括号序？其实，假如你要查询图中 1 到 8 的和，那么你从括号序中 1 到 8（第一个出现的）中出现两次的数的贡献抹去。如果维护的是 xor，那么直接 xor 两次即可。如果维护的是 sum，那么第一个出现的数字的贡献为正，第二个为负，然后用块状链表维护区间和即可。

用块状链表后除了单点修改是 \(O(1)\) 外其他都是 \(O(\sqrt n)\) 的。

ETT 不支持换根操作。对于链（区间）修改，分为两种情况，一是贡献相同（如 xor）是可以的，二是贡献不同（如 sum）是不行的。现在的主流做法毕竟是 LCT，所以这些操作比较多，在避开这种操作的情况下运用这种做法还是不错的。

注：标准的 ETT（用欧拉回路而不是 DFS 括号序实现）是支持换根操作的，但是实现较为复杂。

#3786. 星系探索

点击查看代码

#include<bits/stdc++.h>

using namespace std;

int n,m;

int ver[200005],ne[200005],head[100005],cnt;

inline void link(int x,int y){

	ver[++cnt]=y;

	ne[cnt]=head[x];

	head[x]=cnt;

}

int w[100005];

vector<int> vec;

int son[2][200005],val[200005],fa[200005],rt,siz[200005],tot[200005];

long long sum[200005],tag[200005];

inline void pushup(int x){

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

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

}

inline void push(int x){

	if(!tag[x])return ;

	if(son[0][x]){

		sum[son[0][x]]+=tag[x]*tot[son[0][x]];

		val[son[0][x]]+=siz[son[0][x]]*tag[x];tag[son[0][x]]+=tag[x];

	}

	if(son[1][x]){

		sum[son[1][x]]+=tag[x]*tot[son[1][x]];

		val[son[1][x]]+=siz[son[1][x]]*tag[x];tag[son[1][x]]+=tag[x];

	}tag[x]=0;

}

inline void rotate(int x,int &k){

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

	if(y==k)k=x;else 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[y]=x;fa[x]=z;pushup(x);pushup(y);

}

int stk[200005],top;

inline void splay(int x,int &k){

	stk[++top]=x;

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

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

	while(x!=k){

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

		if(y!=k){

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

			else rotate(y,k);

		}rotate(x,k);

	}

}

int build(int l=0,int r=vec.size()-1){

	if(l>r)return 0;

	int mid=(l+r)>>1,i=vec[mid];

	son[0][i]=build(l,mid-1);fa[son[0][i]]=i;

	son[1][i]=build(mid+1,r);fa[son[1][i]]=i;pushup(i);

	return i;

}

void dfs(int x,int fi){

	tot[x]=siz[x]=1;

	sum[x]=val[x]=w[x];vec.push_back(x);

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

		int u=ver[i];

		if(u==fi)continue;

		dfs(u,x);

	}

	tot[x+n]=siz[x+n]=-1;

	sum[x+n]=val[x+n]=-w[x];vec.push_back(x+n);

}

inline int pre(int x){

	splay(x,rt);x=son[0][x];

	while(son[1][x])x=son[1][x];

	return x;

}

inline int nxt(int x){

	splay(x,rt);x=son[1][x];

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

	return x;

}

void put(int x){

	if(son[0][x])put(son[0][x]);

	if(x<=2*n)printf("%d ",x<=n?x:-x+n);

	if(son[1][x])put(son[1][x]);

}

inline int& split(int l,int r){

	int x=pre(l),y=nxt(r);

	splay(x,rt);splay(y,son[1][x]);

	return son[0][y];

}

inline void update(int x,int v){

	int y=split(x,x+n);

	val[y]+=siz[y]*v;sum[y]+=tot[y]*v;

	tag[y]+=v;pushup(fa[y]);push(fa[fa[y]]);

}

inline void move(int x,int y){

	int &z=split(x,x+n),k=z;

	z=0;pushup(fa[k]);pushup(fa[fa[k]]);

	int t=split(y,y);son[1][t]=k;fa[k]=t;

	pushup(t);pushup(fa[t]);pushup(fa[fa[t]]);

}

inline long long query(int x){

	int y=nxt(x);

	splay(y,rt);return sum[son[0][y]];

}

char op[15];

int main(){

	scanf("%d",&n);

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

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

		link(x,i);link(i,x);

	}

	for(int i=1;i<=n;i++)scanf("%d",&w[i]);

	vec.push_back(2*n+1);dfs(1,1);

	vec.push_back(2*n+2);rt=build();

	scanf("%d",&m);

	while(m--){

		scanf("%s",op);

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

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

			printf("%lld\n",query(x));

		}

		else if(op[0]=='C'){

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

			move(x,y);

		}

		else if(op[0]=='F'){

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

			update(x,y);

		}

	}

	return 0;

}

[BJOI2014]大融合

点击查看代码

巴特西

动态树 — Euler_Tour_Tree

#3786. 星系探索

[BJOI2014]大融合

最新文章

热门文章