星系探索 黑暗爆炸 - 3786[LCT][平衡树]

题目

3e5
维护操作：子树加，换父亲、 $u$ 到根路径和

思路

借助欧拉序和平衡树可实现子树平移，具体 $u$ 到 $v$ 就是将 $[i{n}_u,ou{t}_u]$ 接到 $i{n}_v$ 后面
到根路径和类似带修改树上第 $k$ 大， $i{n}_u$ 处 $+$ $ou{t}_u$ 处-
需要维护欧拉序上子树内多少个 $($ 括号
LCT 可用标记永久化

代码

#include<set> 
#include<map> 
#include<stack> 
#include<cmath> 
#include<cstdio> 
#include<queue> 
#include<vector> 
#include<climits> 
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;     
int read(){
         bool f=0;int x=0;char c=getchar();        while(c<'0'||c>'9'){
    if(c=='-')f=1;c=getchar();}       while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();     return !f?x:-x;    
}
const int MAXN=300000;
const int INF=0x3f3f3f3f;
LL sum[MAXN+5],val[MAXN+5],lazy[MAXN+5];
int ncnt,Root,ch[MAXN+5][2],fa[MAXN+5],cnt[MAXN+5],csiz[MAXN+5],siz[MAXN+5];
bool pan(int u){
    return ch[fa[u]][1]==u;}
void Init(){
    Root=0,ncnt=0;return ;
}
int Newnode(int u){
    sum[u]=val[u]=lazy[u]=0,ch[u][0]=ch[u][1]=fa[u]=0,siz[u]=1,csiz[u]=cnt[u];return u;
}
void PushUp(int u){
    siz[u]=siz[ch[u][0]]+siz[ch[u][1]]+1;sum[u]=sum[ch[u][0]]+sum[ch[u][1]]+val[u];csiz[u]=csiz[ch[u][0]]+csiz[ch[u][1]]+cnt[u];return ;
}
void PushDown(int u){
    if(!lazy[u]) return ;lazy[ch[u][0]]+=lazy[u],lazy[ch[u][1]]+=lazy[u];val[ch[u][0]]+=cnt[ch[u][0]]?lazy[u]:-lazy[u],val[ch[u][1]]+=cnt[ch[u][1]]?lazy[u]:-lazy[u];sum[ch[u][0]]+=(2*csiz[ch[u][0]]-siz[ch[u][0]])*lazy[u],sum[ch[u][1]]+=(2*csiz[ch[u][1]]-siz[ch[u][1]])*lazy[u];lazy[u]=0;return ;
}
void Rotate(int x){
    //修改顺序：父亲,儿子int y=fa[x],z=fa[y],dx=pan(x),dy=pan(y);fa[x]=z,fa[y]=x;//此时pan(y)改变if(ch[x][dx^1]!=0) fa[ch[x][dx^1]]=y;if(z!=0) ch[z][dy]=x;ch[y][dx]=ch[x][dx^1],ch[x][dx^1]=y;PushUp(y);return ;
}
void PushAll(int x,int rt){
    if(x!=rt)PushAll(fa[x],rt);PushDown(x);return ;
}
void Splay(int x,int &rt){
    //任何操作完后必加!!!!功能：将x旋转至rtint f=fa[rt];PushAll(x,rt);for(int y=fa[x];y!=f;Rotate(x),y=fa[x])if(fa[y]!=f)Rotate(pan(x)==pan(y)?y:x);PushUp(x);rt=x;return ;
}
void Print(int u);
void Select(int k,int &rt){
    int u=rt;//Print(u),puts("");while(1){
    PushDown(u);if(k==siz[ch[u][0]]+1)break;if(k<=siz[ch[u][0]])u=ch[u][0];elsek-=siz[ch[u][0]]+1,u=ch[u][1];}Splay(u,rt);return ;
}
int Merge(int u,int v){
    if(!u||!v) return u+v;Select(siz[u],u);ch[u][1]=v,fa[v]=u;PushUp(u);return u;
}
void Split(int rt,int k,int &x,int &y){
    if(!k){
    x=0,y=rt;return ;}Select(k,rt);x=rt,y=ch[rt][1];ch[x][1]=fa[y]=0;PushUp(x);return ;
}
void Build(int &u,int L,int R){
    if(L>R) return ;int Mid=(L+R)>>1;u=Newnode(Mid);Build(ch[u][0],L,Mid-1);Build(ch[u][1],Mid+1,R);if(ch[u][0]) fa[ch[u][0]]=u;if(ch[u][1]) fa[ch[u][1]]=u;PushUp(u);return ;
}
int Getrank(int rt,int u){
    int ret=siz[ch[u][0]]+1;while(fa[u]){
    int d=pan(u);if(d) ret+=siz[ch[fa[u]][0]]+1; u=fa[u];}return ret;
}
void Print(int u){
    if(!u) return ;putchar('(');Print(ch[u][0]);printf("%d",u);Print(ch[u][1]);putchar(')');return ;
}
vector<int> G[MAXN+5];
int ocnt,in[MAXN+5],out[MAXN+5];
void DFS(int u){
    in[u]=++ocnt,cnt[in[u]]=1;for(int i=0;i<(int)G[u].size();i++)DFS(G[u][i]);out[u]=++ocnt;return ;
}
char Re[5];
LL w[MAXN+5];
int main(){
    int n=read();for(int i=2;i<=n;i++)G[read()].push_back(i);DFS(1);Init();Build(Root,1,ocnt);for(int i=1;i<=n;i++){
    w[i]=read();Splay(in[i],Root);val[Root]+=w[i],sum[Root]+=w[i];Splay(out[i],Root);val[Root]-=w[i],sum[Root]-=w[i];}int m=read();for(int i=1;i<=m;i++){
    scanf("%s",Re);if(Re[0]=='Q'){
    int u=read(),k=Getrank(Root,in[u]),L,R;Split(Root,k,L,R);printf("%lld\n",sum[L]);Root=Merge(L,R);}else if(Re[0]=='C'){
    int u=read(),f=read();int k1=Getrank(Root,in[u]),k2=Getrank(Root,out[u]),k3,L,Mid,R;Split(Root,k2,Mid,R);Split(Mid,k1-1,L,Mid);Root=Merge(L,R);k3=Getrank(Root,in[f]);Split(Root,k3,L,R);Root=Merge(Merge(L,Mid),R);}else if(Re[0]=='F'){
    int u=read(),q=read();int k1=Getrank(Root,in[u]),k2=Getrank(Root,out[u]),L,Mid,R;Split(Root,k2,Mid,R);Split(Mid,k1-1,L,Mid);lazy[Mid]+=q,val[Mid]+=cnt[Mid]?q:-q;sum[Mid]+=(2*csiz[Mid]-siz[Mid])*q;Root=Merge(Merge(L,Mid),R);}}return 0;
}