Euler-Tour Tree模板[bzoj 3786]及其讲解
Euler-Tour-Tree
ETT即Euler-Tour-Tree，也就是什么欧拉游览树
是一种可以维护子树操作的动态树
支持link,cut,单点修改，子树修改，查询点到根的信息
(为什么別的不行呢？因为我不会，貌似ETT不支持换根，链操作什么的)
怎么做呢？
我们维护一棵树的括号序列
括号序列就是一个点进栈时记录一次dfn，出栈时再记录一次dfn，就得到了一个有趣的序列（图片上的欧拉序改成括号序…）
括号序列有什么有趣的性质呢？
子树提取
如果想提取子树信息是非常方便的
比如以2为根的子树有2,3,4,5这些节点
而被2括起來的序列是2 3 3 4 5 5 4 2
所有的点都在其中，原因是括号序列的定义，子树没有搜完不会让自己再次加到dfn中这为ETT子树修改提供了方便
查询到根的信息
比如4到根的信息
我们在序列中可以找到这样的一段1 2 3 3 4
由于3出现了两次，说明从根到4的路径上它出栈了，也就是说3不在这条链上
我们用差分的思想就可以解決，出栈点权=-入栈点权，就可以消去了
查询到根的信息，即查询序列的区间信息
只看以上两个操作似乎只需要线段树就可以解決了，但是显然这样算不上ETT，功能比不上树链剖分下面是动态树的经典操作
link&cut
不能link和cut还叫什么动态树
我们还需要括号序列来搞事情
比如在这棵树中
我想把4从2上cut下來，再与6link一下
我们生成这样的一个序列就可以表示操作后的树
我们可以直观看到
link和cut的本质就是欧拉序列上一个子树所代表序列的平移
Euler-Tour-Tree的实现
我们都有理论基础了
还怕什么区间修改，区间查询，区间平移…
钦定的Splay Tree作为辅助树来维护欧拉序列
吼吼吼
上代码(个人感觉比Link-Cut-Tree好理解，能满足Link-Cut-Tree所不能做的操作，但是也有局限性)注意维护为出栈点还是入栈点
放代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#define MAXN 200010
using namespace std;
inline void read(int &x){
int s=0,w=1;
char c=getchar();
while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
while(isdigit(c)){s=(s<<3)+(s<<1)+c-'0';c=getchar();}
x=s*w;
}
inline void write(long long x){
if(x<0)x=-x,putchar('-');
if(x>9)write(x/10);
putchar(x%10+'0');
}
struct edge{
int to,nxxt;
}e[MAXN];
int head[MAXN],cnt;
inline void add(int x,int y){
e[++cnt].to=y;
e[cnt].nxxt=head[x];
head[x]=cnt;
}
int fa[MAXN],size[MAXN],son[MAXN][2],l[MAXN],r[MAXN],mark[MAXN],dfn[MAXN],tot,a[MAXN];
long long lazy[MAXN],sum[MAXN],val[MAXN];
inline void push_up(int root){
sum[root]=sum[son[root][0]]+sum[son[root][1]]+val[root];
size[root]=size[son[root][0]]+size[son[root][1]]+mark[root];
}
inline void push_down(int root){
if(root&&fa[root])push_down(fa[root]);
if(!root||!lazy[root])return ;
lazy[son[root][0]]+=lazy[root],lazy[son[root][1]]+=lazy[root];
val[son[root][0]]+=lazy[root]*mark[son[root][0]],val[son[root][1]]+=lazy[root]*mark[son[root][1]];
sum[son[root][0]]+=(long long)size[son[root][0]]*lazy[root],sum[son[root][1]]+=(long long)size[son[root][1]]*lazy[root];
lazy[root]=0;
}
inline int dir(int root){
return son[fa[root]][1]==root;
}
inline void rotate(int root,int d){
int temp=son[root][d^1];
son[root][d^1]=son[temp][d];
if(son[root][d^1])fa[son[root][d^1]]=root;
fa[temp]=fa[root];
if(fa[root])son[fa[root]][dir(root)]=temp;
fa[root]=temp;
son[temp][d]=root;
push_up(root),push_up(temp);
}
inline void splay(int root,int goal){
push_down(root);
while(fa[root]!=goal){
if(fa[fa[root]]!=goal&&dir(root)==dir(fa[root]))
rotate(fa[fa[root]],dir(root)^1);
rotate(fa[root],dir(root)^1);
}
}
inline int find_left(int x){
splay(x,0);
x=son[x][0];
while(son[x][1])x=son[x][1];
return x;
}
inline int find_right(int x){
splay(x,0);
x=son[x][1];
while(son[x][0])x=son[x][0];
return x;
}
int build(int left,int right){
if(left>right)return 0;
int mid=(left+right)>>1;
if(mid<right)fa[son[mid][1]=build(mid+1,right)]=mid;
if(left<mid)fa[son[mid][0]=build(left,mid-1)]=mid;
val[mid]=(dfn[mid]>0)?a[dfn[mid]]:-a[-dfn[mid]];
mark[mid]=(dfn[mid]>0)?1:-1;
push_up(mid);
return mid;
}
void dfs(int x){
dfn[l[x]=++tot]=x;
for(int i=head[x];i;i=e[i].nxxt)
dfs(e[i].to);
dfn[r[x]=++tot]=-x;
}
int n,x,y,m;
char opt;
int main(){
read(n);
for(int i=2;i<=n;i++) {
read(x);
add(x,i);
}
dfs(1);
for(int i=1;i<=n;i++)read(a[i]);
build(1,tot+1);
read(m);
while(m--) {
opt=getchar();
while(opt!='Q'&&opt!='C'&&opt!='F')
opt=getchar();
read(x);
if(opt=='Q') {
splay(l[x],0);
write(sum[son[l[x]][0]]+val[l[x]]),putchar(10);
}
else if(opt=='C'){
read(y);
int aa=find_left(l[x]),bb=find_right(r[x]);
splay(aa,0),splay(bb,aa);
int temp=son[bb][0];
son[bb][0]=0;
push_up(bb),push_up(aa);
splay(x=find_left(r[y]),0),splay(r[y],x);
fa[temp]=r[y];
son[r[y]][0]=temp;
push_up(r[y]),push_up(x);
}
else{
read(y);
int aa=find_left(l[x]),bb=find_right(r[x]);
splay(aa,0),splay(bb,aa);
lazy[son[bb][0]]+=y,val[son[bb][0]]+=y*mark[son[bb][0]],sum[son[bb][0]]+=(long long)size[son[bb][0]]*y;
}
}
}
assass_cannotin让我转的
还不让我标转载
他写的真的sb