This is not the end.

0%

Euler Tour Tree(ETT)

Posted on

写在前面的话

ETT是一种动态树，它可以支持link，cut，子树修改，子树信息查询，链信息查询。似乎还可以支持换根（？），但是我不会。

ETT的基本工作原理

一棵有根树的括号序列

就是说，一个点进栈的时候我们把它push_back到序列里面，出栈的时候也把它push_back到序列里面。

比如说，一棵树，其中fa[2]=1,fa[3]=2,fa[4]=2，那么它的括号序就是：1 2 3 3 4 4 2 1

显然一个括号序列可以确定一个有根树。而一个有根树可能对应到多个不同的括号序列。

ETT的工作原理

ETT就是用平衡树维护整个括号序列。

子树信息查询

就是括号序中，一段区间内的左括号的信息的和。

链信息查询

首先通过差分转化成一个点到根的路径上的信息。然后，我们令一个点$x$入栈时加入序列中的那个点的权值取$val_x$，令$x$出栈时加入序列中的那个点的权值取$-val_x$，这样，序列中某个点入栈时的点左侧的所有点的$val$的和，就是这个点到根的路径上的所有点的$val$的和。

子树信息修改

直接把对序列进行区间修改即可。

link和cut

考虑对于一棵有根树，link和cut的本质是把从它的父亲那里剪下来，然后接到另一个点的下面。这对应到括号序列上就是区间平移。直接用平衡树实现就可以了。

模板

bzoj3786

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define PB push_back
#define ll long long
using namespace std;
template <class T>
inline void rd(T &x)
{
	x=0; char c=getchar(); int f=1;
	while(!isdigit(c)){if(c=='-')f=-1; c=getchar();}
	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int N=1e5+10,M=N<<1;
int xi[M],fi[M];
ll val[M],sum[M],tag[M];
int ch[M][2],fa[M],rt;
void push_up(int x) {
	fi[x]=fi[ch[x][0]]+fi[ch[x][1]]+xi[x];
	sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+val[x];
}
void Add(int x,ll d) {
	sum[x]+=fi[x]*d,val[x]+=xi[x]*d;
	tag[x]+=d;
}
void push_down(int x) {
	if(!tag[x]) return;
	Add(ch[x][0],tag[x]),Add(ch[x][1],tag[x]);
	tag[x]=0;
}
void Debug(int x) {
	if(!x) return; push_down(x);
	Debug(ch[x][0]);
	cout<<val[x]<<' ';
	Debug(ch[x][1]);
}	
void PD(int x) {
	static int stk[M],top;
	stk[top=1]=x;
	while(fa[x]) stk[++top]=fa[x],x=fa[x];
	while(top) push_down(stk[top--]);
}
int get(int x) { return ch[fa[x]][1]==x; }
void rotate(int x) {
//	printf("rotate: %d\n",x);
	int f=fa[x],ff=fa[f],d=get(x);
	fa[x]=ff; if(ff) ch[ff][ch[ff][1]==f]=x;
	fa[ch[x][d^1]]=f,ch[f][d]=ch[x][d^1];
	fa[f]=x,ch[x][d^1]=f; push_up(f),push_up(x);
//	Debug(rt);
}
void splay(int x,int gl) {
	PD(x);
	for(int f=fa[x];f!=gl;rotate(x),f=fa[x])
		if(fa[f]!=gl) rotate(get(x)==get(f)?f:x);
	if(!gl) rt=x;
}
int find(int x,int d) {
	splay(x,0); int t=ch[x][d]; push_down(t);
	while(ch[t][d^1]) t=ch[t][d^1],push_down(t);
	return t;
}
int lx[N],rx[N],n,id;
vector<int> son[N];
void dfs(int u) {
	lx[u]=++id;
	for(int i=0;i<son[u].size();++i)
		dfs(son[u][i]);
	rx[u]=++id;
}
void build(int l,int r,int &c,int f) {
	if(l>r) { c=0; return; }
	int mid=l+r>>1; c=mid,fa[c]=f;
	build(l,mid-1,ch[c][0],c),build(mid+1,r,ch[c][1],c);
	push_up(c);
}
void split(int l,int r) {
	int pr=find(l,0),sf=find(r,1);
	splay(pr,0),splay(sf,rt);
	push_down(rt),push_down(sf);
}
void update_val(int x,int d) {
	split(lx[x],rx[x]);
	Add(ch[ch[rt][1]][0],d);
	push_up(ch[rt][1]),push_up(rt);
}
void update_ed(int x,int y) {
	split(lx[x],rx[x]);
	int f1=ch[rt][1],t=ch[f1][0];
	ch[f1][0]=0,fa[t]=0; push_up(f1),push_up(rt);
	int sf=find(lx[y],1);
	splay(lx[y],0),splay(sf,rt);
	push_down(rt),push_down(sf);
	int f2=ch[rt][1];
	ch[f2][0]=t,fa[t]=f2; push_up(f2),push_up(rt);
}
int main() {
	int q,x,y; char ty[11];
	rd(n);
	for(int i=2;i<=n;++i) rd(x),son[x].PB(i);
	++id;
	dfs(1);
	++id;
	for(int i=1;i<=n;++i) {
		rd(x);
		val[lx[i]]=x,xi[lx[i]]=1;
		val[rx[i]]=-x,xi[rx[i]]=-1;
	}
	build(1,id,rt,0);
//	Debug(rt);
	rd(q);
	while(q--) {
		scanf("%s",ty);
		if(ty[0]=='Q') {
			rd(x);
			splay(lx[x],0); push_down(lx[x]);
//			Debug(rt);
			printf("%lld\n",sum[lx[x]]-sum[ch[lx[x]][1]]);
		}
		else if(ty[0]=='F') {
			rd(x),rd(y);
			update_val(x,y);
		}
		else {
			rd(x),rd(y);
			update_ed(x,y);
		}
//		Debug(rt);
	}
	return 0;
}