一个很简单的东西。
- 例题：BZOJ3786
题意：一棵树，有点权。多次操作，支持子树加，单点换父亲，查询到根路径权值和。
\(1\le n\le 10^5,\space 1\le m\le 3\times 10^5\)
考虑维护树的欧拉序，就是一个点访问和回溯的时候往后加入序列末尾。
子树加法就是区间加，换父亲就是区间平移，使用平衡树解决，注意一个点的权值带符号。
写了 treap，随机 merge 没过，只好改成随机堆权，发现常数是原来的 \(\dfrac 13\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define pir pair<ll,ll>
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
using namespace std;
const ll maxn=2e5+10, mod=998244353;
mt19937 rnd(time(0));
struct Treap{
ll lc[maxn],rc[maxn],val[maxn],sum[maxn],siz[maxn],fa[maxn],tag[maxn],cnt[maxn],ff[maxn],rd[maxn];
void pushup(ll p){
sum[p]=sum[lc[p]]+sum[rc[p]]+val[p];
siz[p]=siz[lc[p]]+siz[rc[p]]+1;
cnt[p]=cnt[lc[p]]+cnt[rc[p]]+ff[p];
fa[lc[p]]=fa[rc[p]]=p;
fa[0]=0;
}
void addtag(ll p,ll v){
if(!p) return;
val[p]+=v*ff[p], tag[p]+=v, sum[p]+=v*cnt[p];
}
void pushdown(ll p){
if(!tag[p]) return;
addtag(lc[p],tag[p]), addtag(rc[p],tag[p]);
tag[p]=0;
}
void split(ll p,ll k,ll &x,ll &y){
if(!p){
x=y=0; return;
} pushdown(p);
if(siz[lc[p]]+1<=k){
x=p, fa[rc[p]]=0;
split(rc[p],k-siz[lc[p]]-1,rc[x],y);
pushup(x);
} else{
y=p, fa[lc[p]]=0;
split(lc[p],k,x,lc[y]);
pushup(y);
}
}
ll merge(ll p,ll q){
if(!p||!q) return p|q;
pushdown(p), pushdown(q);
if(rd[p]<rd[q]){
fa[rc[p]]=0;
rc[p]=merge(rc[p],q);
pushup(p); return p;
} else{
fa[lc[q]]=0;
lc[q]=merge(p,lc[q]);
pushup(q); return q;
}
}
void init(ll p,ll v,ll f){
sum[p]=val[p]=v, cnt[p]=ff[p]=f, tag[p]=lc[p]=rc[p]=fa[p]=0, siz[p]=1;
rd[p]=rnd()%(1ll<<31);
}
ll getrk(ll p){
ll res=1+siz[lc[p]];
while(fa[p]){
if(rc[fa[p]]==p) res+=siz[lc[fa[p]]]+1;
p=fa[p];
} return res;
}
void renew(ll p){
if(fa[p]) renew(fa[p]);
pushdown(p);
}
ll query(ll p){
renew(p);
ll res=val[p]+sum[lc[p]];
while(fa[p]){
if(rc[fa[p]]==p) res+=sum[lc[fa[p]]]+val[fa[p]];
p=fa[p];
} return res;
}
}T;
ll n,a[maxn],m,x,y,rt;
char op[4];
vector<ll>to[maxn];
void dfs(ll u){
T.init(u,a[u],1);
rt=T.merge(rt,u);
for(ll v:to[u]){
dfs(v);
}
T.init(u+n,-a[u],-1);
rt=T.merge(rt,u+n);
}
ll s1,s2,s3,s;
int main(){
scanf("%lld",&n);
for(ll i=2,x;i<=n;i++){
scanf("%lld",&x); to[x].pb(i);
}
for(ll i=1;i<=n;i++) scanf("%lld",a+i);
dfs(1);
scanf("%lld",&m);
T.getrk(16932);
while(m--){
scanf("%s%lld",op,&x);
if(op[0]=='Q') printf("%lld\n",T.query(x));
else if(op[0]=='C'){ scanf("%lld",&y);
ll l=T.getrk(x), r=T.getrk(x+n);
ll t=T.getrk(y);
T.split(rt,r,s1,s3);
T.split(s1,l-1,s1,s);
if(t<l){
T.split(s1,t,s1,s2); T.fa[s1]=T.fa[s2]=T.fa[s3]=T.fa[s]=0;
rt=T.merge(T.merge(s1,s),T.merge(s2,s3));
} else{
T.split(s3,t-r,s2,s3); T.fa[s1]=T.fa[s2]=T.fa[s3]=T.fa[s]=0;
rt=T.merge(T.merge(s1,s2),T.merge(s,s3));
}
} else{
scanf("%lld",&y);
ll l=T.getrk(x), r=T.getrk(x+n);
T.split(rt,r,s1,s3);
T.split(s1,l-1,s1,s2);
T.addtag(s2,y);
rt=T.merge(T.merge(s1,s2),s3);// T.fa[rt]=0;
}
}
return 0;
}