zcmimi's blog
avatar
zc
2020-01-05 18:45:00
  • 本文总阅读量
查看原题

点击跳转

换根树链剖分

前置知识:树链剖分

题意:树链加,子树加,需要支持换根,查询树链和,子树和

树链加、查询树链和 与普通的树链剖分一样

主要讲:

需要支持换根,子树加,查询子树和

设当前查询的点为x

情况1: x就是根,直接输出整棵树的和

情况2: 根在x子树内:

找到根到x路径上的x的儿子

int child(int rt,int x){
    while(top[rt]!=top[x]){
        rt=top[rt];
        if(f[rt]==x)return rt;//父亲是x,返回当前点
        rt=f[rt];
    }
    return son[x];//根在x所在的重链上
}

把整棵树除t子树外的部分加上val即可

举个例子

<svg width="300px" height="300px" ="SVGRoot"><g ="EditableGraph"><g ="SVGGroup"><g ="GraphEdge"><path d="M 148.30985915492957 45.774647887323944 L 96.30985915492957 98.87323943661971" fill="none" stroke-width="2" stroke="black" ="SVGPath"></path><path d="M 148.30985915492957 45.774647887323944 L 96.30985915492957 98.87323943661971" opacity="0" fill="none" stroke-width="30" stroke="black" ="SVGPath"></path></g><g ="GraphEdge"><path d="M 148.30985915492957 45.774647887323944 L 226.30985915492957 98.87323943661971" fill="none" stroke-width="2" stroke="black" ="SVGPath"></path><path d="M 148.30985915492957 45.774647887323944 L 226.30985915492957 98.87323943661971" opacity="0" fill="none" stroke-width="30" stroke="black" ="SVGPath"></path></g><g ="GraphEdge"><path d="M 96.30985915492957 98.87323943661971 L 70.30985915492957 151.9718309859155" fill="none" stroke-width="2" stroke="black" ="SVGPath"></path><path d="M 96.30985915492957 98.87323943661971 L 70.30985915492957 151.9718309859155" opacity="0" fill="none" stroke-width="30" stroke="black" ="SVGPath"></path></g><g ="GraphEdge"><path d="M 96.30985915492957 98.87323943661971 L 148.3098591549295 151.9718309859155" fill="none" stroke-width="2" stroke="black" ="SVGPath"></path><path d="M 96.30985915492957 98.87323943661971 L 148.3098591549295 151.9718309859155" opacity="0" fill="none" stroke-width="30" stroke="black" ="SVGPath"></path></g><g ="GraphEdge"><path d="M 226.30985915492957 98.87323943661971 L 200.30985915492954 151.9718309859155" fill="none" stroke-width="2" stroke="black" ="SVGPath"></path><path d="M 226.30985915492957 98.87323943661971 L 200.30985915492954 151.9718309859155" opacity="0" fill="none" stroke-width="30" stroke="black" ="SVGPath"></path></g><g ="GraphEdge"><path d="M 226.30985915492957 98.87323943661971 L 252.30985915492957 151.9718309859155" fill="none" stroke-width="2" stroke="black" ="SVGPath"></path><path d="M 226.30985915492957 98.87323943661971 L 252.30985915492957 151.9718309859155" opacity="0" fill="none" stroke-width="30" stroke="black" ="SVGPath"></path></g><g ="GraphEdge"><path d="M 70.30985915492957 151.9718309859155 L 44.30985915492957 205.07042253521126" fill="none" stroke-width="2" stroke="black" ="SVGPath"></path><path d="M 70.30985915492957 151.9718309859155 L 44.30985915492957 205.07042253521126" opacity="0" fill="none" stroke-width="30" stroke="black" ="SVGPath"></path></g><g ="GraphEdge"><path d="M 70.30985915492957 151.9718309859155 L 96.30985915492955 205.07042253521126" fill="none" stroke-width="2" stroke="black" ="SVGPath"></path><path d="M 70.30985915492957 151.9718309859155 L 96.30985915492955 205.07042253521126" opacity="0" fill="none" stroke-width="30" stroke="black" ="SVGPath"></path></g></g><g ="SVGGroup"><g fixed="false" style="cursor: pointer;" ="GraphNode"><circle stroke-width="5" fill="white" stroke="black" r="19" cx="148.30985915492957" cy="45.774647887323944" ="SVGCircle"></circle><text font-size="14" dy=".35em" text-anchor="middle" stroke-width="1" fill="black" stroke="black" x="148.30985915492957" y="45.774647887323944" style="user-select: none;" ="SVGText">1</text></g><g fixed="false" style="cursor: pointer;" ="GraphNode"><circle stroke-width="5" fill="white" stroke="black" r="19" cx="96.30985915492957" cy="98.87323943661971" ="SVGCircle"></circle><text font-size="14" dy=".35em" text-anchor="middle" stroke-width="1" fill="black" stroke="black" x="96.30985915492957" y="98.87323943661971" style="user-select: none;" ="SVGText">2</text></g><g fixed="false" style="cursor: pointer;" ="GraphNode"><circle stroke-width="5" fill="white" stroke="black" r="19" cx="226.30985915492957" cy="98.87323943661971" ="SVGCircle"></circle><text font-size="14" dy=".35em" text-anchor="middle" stroke-width="1" fill="black" stroke="black" x="226.30985915492957" y="98.87323943661971" style="user-select: none;" ="SVGText">3</text></g><g fixed="false" ="GraphNode" style="cursor: pointer;"><circle stroke-width="5" fill="white" stroke="black" r="19" cx="70.30985915492957" cy="151.9718309859155" ="SVGCircle"></circle><text font-size="14" dy=".35em" text-anchor="middle" stroke-width="1" fill="black" stroke="black" x="70.30985915492957" y="151.9718309859155" ="SVGText" style="user-select: none;">4</text></g><g fixed="false" ="GraphNode" style="cursor: pointer;"><circle stroke-width="5" fill="white" stroke="black" r="19" cx="148.3098591549295" cy="151.9718309859155" ="SVGCircle"></circle><text font-size="14" dy=".35em" text-anchor="middle" stroke-width="1" fill="black" stroke="black" x="148.3098591549295" y="151.9718309859155" ="SVGText" style="user-select: none;">5</text></g><g fixed="false" ="GraphNode" style="cursor: pointer;"><circle stroke-width="5" fill="white" stroke="black" r="19" cx="200.30985915492954" cy="151.9718309859155" ="SVGCircle"></circle><text font-size="14" dy=".35em" text-anchor="middle" stroke-width="1" fill="black" stroke="black" x="200.30985915492954" y="151.9718309859155" ="SVGText" style="user-select: none;">6</text></g><g fixed="false" ="GraphNode" style="cursor: pointer;"><circle stroke-width="5" fill="white" stroke="black" r="19" cx="252.30985915492957" cy="151.9718309859155" ="SVGCircle"></circle><text font-size="14" dy=".35em" text-anchor="middle" stroke-width="1" fill="black" stroke="black" x="252.30985915492957" y="151.9718309859155" ="SVGText" style="user-select: none;">7</text></g><g fixed="false" ="GraphNode" style="cursor: pointer;"><circle stroke-width="5" fill="white" stroke="black" r="19" cx="44.30985915492957" cy="205.07042253521126" ="SVGCircle"></circle><text font-size="14" dy=".35em" text-anchor="middle" stroke-width="1" fill="black" stroke="black" x="44.30985915492957" y="205.07042253521126" style="user-select: none;" ="SVGText">8</text></g><g fixed="false" ="GraphNode" style="cursor: pointer;"><circle stroke-width="5" fill="white" stroke="black" r="19" cx="96.30985915492955" cy="205.07042253521126" ="SVGCircle"></circle><text font-size="14" dy=".35em" text-anchor="middle" stroke-width="1" fill="black" stroke="black" x="96.30985915492955" y="205.07042253521126" style="user-select: none;" _="SVGText">9</text></g></g></g></svg>

建树时是以1为根

设当前根为9,x为2

找出的child是4

<svg width="300px" height="300px" ="SVGRoot"><g ="EditableGraph"><g ="SVGGroup"><g ="GraphEdge"><path d="M261,153.39565279298176Q205.162355744426,154.5050546416901,149.32471148885205,155.6144564903984" fill="none" stroke-width="2" stroke="black" ="SVGPath"></path><path d="M261,153.39565279298176Q205.162355744426,154.5050546416901,149.32471148885205,155.6144564903984" opacity="0" fill="none" stroke-width="30" stroke="black" ="SVGPath"></path></g><g ="GraphEdge"><path d="M261,153.39565279298176Q206.91547342716183,207.19782639649088,152.83094685432368,261" fill="none" stroke-width="2" stroke="black" ="SVGPath"></path><path d="M261,153.39565279298176Q206.91547342716183,207.19782639649088,152.83094685432368,261" opacity="0" fill="none" stroke-width="30" stroke="black" ="SVGPath"></path></g><g ="GraphEdge"><path d="M149.32471148885205,155.6144564903984Q151.05132366814587,97.3072282451992,152.7779358474397,39" fill="none" stroke-width="2" stroke="black" ="SVGPath"></path><path d="M149.32471148885205,155.6144564903984Q151.05132366814587,97.3072282451992,152.7779358474397,39" opacity="0" fill="none" stroke-width="30" stroke="black" ="SVGPath"></path></g><g ="GraphEdge"><path d="M 149.32471148885205 155.6144564903984 L 39 148.97409692923225" fill="none" stroke-width="2" stroke="black" ="SVGPath"></path><path d="M 149.32471148885205 155.6144564903984 L 39 148.97409692923225" opacity="0" fill="none" stroke-width="30" stroke="black" ="SVGPath"></path></g><g ="GraphEdge"><path d="M 152.7779358474397 39 L 260.3385416666667 39" fill="none" stroke-width="2" stroke="black" ="SVGPath"></path><path d="M 152.7779358474397 39 L 260.3385416666667 39" opacity="0" fill="none" stroke-width="30" stroke="black" ="SVGPath"></path></g><g ="GraphEdge"><path d="M152.7779358474397,39Q95.88896792371985,39,39,39" fill="none" stroke-width="2" stroke="black" ="SVGPath"></path><path d="M152.7779358474397,39Q95.88896792371985,39,39,39" opacity="0" fill="none" stroke-width="30" stroke="black" ="SVGPath"></path></g><g ="GraphEdge"><path d="M152.83094685432368,261Q95.91547342716184,261,39,261" fill="none" stroke-width="2" stroke="black" ="SVGPath"></path><path d="M152.83094685432368,261Q95.91547342716184,261,39,261" opacity="0" fill="none" stroke-width="30" stroke="black" ="SVGPath"></path></g><g ="GraphEdge"><path d="M 152.83094685432368 261 L 261 261" fill="none" stroke-width="2" stroke="black" ="SVGPath"></path><path d="M 152.83094685432368 261 L 261 261" opacity="0" fill="none" stroke-width="30" stroke="black" ="SVGPath"></path></g></g><g ="SVGGroup"><g fixed="false" style="cursor: pointer;" ="GraphNode"><circle stroke-width="2" fill="white" stroke="black" r="19" cx="261" cy="153.39565279298176" ="SVGCircle"></circle><text font-size="14" dy=".35em" text-anchor="middle" stroke-width="1" fill="black" stroke="black" x="261" y="153.39565279298176" style="user-select: none;" ="SVGText">1</text></g><g fixed="false" style="cursor: pointer;" ="GraphNode"><circle stroke-width="2" fill="white" stroke="black" r="19" cx="149.32471148885205" cy="155.6144564903984" ="SVGCircle"></circle><text font-size="14" dy=".35em" text-anchor="middle" stroke-width="1" fill="black" stroke="black" x="149.32471148885205" y="155.6144564903984" style="user-select: none;" ="SVGText">2</text></g><g fixed="false" ="GraphNode" style="cursor: pointer;"><circle stroke-width="2" fill="white" stroke="black" r="19" cx="152.83094685432368" cy="261" ="SVGCircle"></circle><text font-size="14" dy=".35em" text-anchor="middle" stroke-width="1" fill="black" stroke="black" x="152.83094685432368" y="261" ="SVGText" style="user-select: none;">3</text></g><g fixed="false" ="GraphNode" style="cursor: pointer;"><circle stroke-width="5" fill="white" stroke="black" r="19" cx="152.7779358474397" cy="39" ="SVGCircle"></circle><text font-size="14" dy=".35em" text-anchor="middle" stroke-width="1" fill="black" stroke="black" x="152.7779358474397" y="39" style="user-select: none;" ="SVGText">4</text></g><g fixed="false" ="GraphNode" style="cursor: pointer;"><circle stroke-width="2" fill="white" stroke="black" r="19" cx="39" cy="148.97409692923225" ="SVGCircle"></circle><text font-size="14" dy=".35em" text-anchor="middle" stroke-width="1" fill="black" stroke="black" x="39" y="148.97409692923225" style="user-select: none;" ="SVGText">5</text></g><g fixed="false" ="GraphNode" style="cursor: pointer;"><circle stroke-width="5" fill="white" stroke="black" r="19" cx="260.3385416666667" cy="39" ="SVGCircle"></circle><text font-size="14" dy=".35em" text-anchor="middle" stroke-width="1" fill="black" stroke="black" x="260.3385416666667" y="39" style="user-select: none;" ="SVGText">8</text></g><g fixed="false" ="GraphNode" style="cursor: pointer;"><circle stroke-width="5" fill="white" stroke="black" r="19" cx="39" cy="39" ="SVGCircle"></circle><text font-size="14" dy=".35em" text-anchor="middle" stroke-width="1" fill="black" stroke="black" x="39" y="39" style="user-select: none;" ="SVGText">9</text></g><g fixed="false" ="GraphNode" style="cursor: pointer;"><circle stroke-width="2" fill="white" stroke="black" r="19" cx="39" cy="261" ="SVGCircle"></circle><text font-size="14" dy=".35em" text-anchor="middle" stroke-width="1" fill="black" stroke="black" x="39" y="261" ="SVGText" style="user-select: none;">6</text></g><g fixed="false" ="GraphNode" style="cursor: pointer;"><circle stroke-width="2" fill="white" stroke="black" r="19" cx="261" cy="261" ="SVGCircle"></circle><text font-size="14" dy=".35em" text-anchor="middle" stroke-width="1" fill="black" stroke="black" x="261" y="261" _="SVGText" style="user-select: none;">7</text></g></g></g></svg>

情况3: 根不在x子树内: 与普通树链剖分一样

线段树版:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fl(i,x) for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
#define N 100011
int n,cnt=0,RT=1,head[N],c[N];
struct edge{
    int to,nxt;
}e[N];
void add(int x,int y){
    e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;
}
int a[N];
ll s[N<<2],laz[N<<2];
#define ls rt<<1
#define rs rt<<1|1
#define pu s[rt]=s[ls]+s[rs]
void pd(int rt,int ln,int rn){
    if(laz[rt]){
        laz[ls]+=laz[rt];
        laz[rs]+=laz[rt];
        s[ls]+=ln*laz[rt];
        s[rs]+=rn*laz[rt];
        laz[rt]=0;
    }
}
void build(int l,int r,int rt){
    if(l==r){
        s[rt]=a[l];
        return;
    }
    int m=(l+r)>>1;
    build(l,m,ls);build(m+1,r,rs);
    pu;
}
void upd(int L,int R,int v,int l,int r,int rt){
    if(L<=l&&r<=R){
        s[rt]+=v*(r-l+1);
        laz[rt]+=v;
        return;
    }
    int m=(l+r)>>1;
    pd(rt,m-l+1,r-m);
    if(L<=m)upd(L,R,v,l,m,ls);
    if(R>m)upd(L,R,v,m+1,r,rs);
    pu;
}
ll ask(int L,int R,int l,int r,int rt){
    if(L<=l&&r<=R)return s[rt];
    int m=(l+r)>>1;
    ll ans=0;
    pd(rt,m-l+1,r-m);
    if(L<=m)ans=ask(L,R,l,m,ls);
    if(R>m)ans+=ask(L,R,m+1,r,rs);
    return ans;
}
int son[N],siz[N],top[N],id[N],f[N],d[N],sz=0;
void dfs(int x){
    siz[x]=1;
    son[x]=0;
    fl(i,x){
        d[to]=d[x]+1;
        dfs(to);
        siz[x]+=siz[to];
        if(siz[to]>siz[son[x]])son[x]=to;
    }
}
void bt(int x,int tp){
    top[x]=tp;id[x]=++sz;a[id[x]]=c[x];
    if(!son[x])return;
    bt(son[x],tp);
    fl(i,x)if(!top[to])bt(to,to);
}
ll fh(int x,int y){
    ll ans=0;
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]])swap(x,y);
        ans+=ask(id[top[x]],id[x],1,n,1);x=f[top[x]];
    }
    if(id[x]>id[y])swap(x,y);
    return ans+ask(id[x],id[y],1,n,1);
}
void ul(int x,int y,int k){
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]])swap(x,y);
        upd(id[top[x]],id[x],k,1,n,1);x=f[top[x]];
    }
    if(id[x]>id[y])swap(x,y);
    upd(id[x],id[y],k,1,n,1);
}
int child(int x,int y){
    while(top[x]!=top[y]){
        x=top[x];
        if(f[x]==y)return x;
        x=f[x];
    }
    return son[y];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&c[i]);
    int q,x,y,opt,k;
    for(int i=2;i<=n;++i)
        scanf("%d",&f[i]),add(f[i],i);
    dfs(1);bt(1,1);
    build(1,n,1);
    scanf("%d",&q);
    while(q--){
        scanf("%d%d",&opt,&x);
        if(opt==1)RT=x;
        if(opt==2)scanf("%d%d",&y,&k),ul(x,y,k);
        if(opt==3){
            scanf("%d",&k);
            if(x==RT)upd(1,n,k,1,n,1);
            else if(id[x]<=id[RT]&&id[RT]+siz[RT]<=id[x]+siz[x]){
                int t=child(RT,x);
                upd(1,n,k,1,n,1);
                upd(id[t],id[t]+siz[t]-1,-k,1,n,1);
            }
            else upd(id[x],id[x]+siz[x]-1,k,1,n,1);
        }
        if(opt==4)scanf("%d",&y),printf("%lld\n",fh(x,y));
        if(opt==5){
            if(x==RT)printf("%lld\n",s[1]);
            else if(id[x]<=id[RT]&&id[RT]+siz[RT]<=id[x]+siz[x]){
                int t=child(RT,x);
                printf("%lld\n",s[1]-ask(id[t],id[t]+siz[t]-1,1,n,1));
            }
            else printf("%lld\n",ask(id[x],id[x]+siz[x]-1,1,n,1));
        }
    }
}

树状数组版:

#include<bits/stdc++.h>
#pragma GCC optimize(3)
#pragma GCC optimize(Ofast)
#define il inline
il void SWAP(int &x,int &y){int t=x;x=y;y=t;}
using namespace std;
namespace IO{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;il char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}il void in(string &ch){ch.clear();if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF){__=1;return;}ch+=c;while((c=gc())!=EOF&&!isspace(c))ch+=c;if(c==EOF)__=1;}il void in(char &ch){if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)__=1;else ch=c;}il void in(char *ch){*ch='\0';if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF){__=1;return;}*ch=c;ch++;while((c=gc())!=EOF&&!isspace(c))*ch=c,ch++;if(c==EOF)__=1;*ch='\0';}template<typename T>il void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>il void in(T &x,arr & ... y){in(x),in(y...);}const char ln='\n';static char out_buf[str],*out_s=out_buf,*out_t=out_buf+str;il void flush(){fwrite(out_buf,1,out_s-out_buf,stdout);out_s=out_buf;}il void pt(char c){(out_s==out_t)?(fwrite(out_s=out_buf,1,str,stdout),*out_s++=c):(*out_s++=c);}il void out(const char* s){while(*s)pt(*s++);}il void out(char* s){while(*s)pt(*s++);}il void out(char c){pt(c);}il void out(string s){for(int i=0;s[i];i++)pt(s[i]);}template<typename T>il void out(T x){if(!x){pt('0');return;}if(x<0)pt('-'),x=-x;char a[50],t=0;while(x)a[t++]=x%10,x/= 10;while(t--)pt(a[t]+'0');}template<typename T,typename ... arr>il void out(T x,arr & ... y){out(x),out(y...);}}using namespace IO;
#define N 100011
#define ll long long
#define fl(i,x) for(int i(head[x]),to;to=e[i].to,i;i=e[i].nxt)
int n,cnt=0,RT=1,head[N],c[N];
struct edge{
    int to,nxt;
}e[N];
il void add(int x,int y){
    e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;
}
ll s[N],S[N];
il void upd(int x,int v){
    if(x<=n)
    for(int i=x;i<=n;i+=i&-i)
        s[i]+=v,
        S[i]+=1ll*v*(x-1);
}
il ll ask(int x){
    ll ans=0;
    for(int i=x;i;i-=i&-i)
        ans+=1ll*x*s[i]-S[i];
    return ans;
}
il void upd(int l,int r,int v){upd(l,v);upd(r+1,-v);}
il ll ask(int l,int r){return ask(r)-ask(l-1);}
int son[N],siz[N],top[N],id[N],f[N],d[N],sz=0;
void dfs(int x){
    siz[x]=1;
    son[x]=0;
    fl(i,x){
        d[to]=d[x]+1;
        dfs(to);
        siz[x]+=siz[to];
        if(siz[to]>siz[son[x]])son[x]=to;
    }
}
void bt(int x,int tp){
    top[x]=tp;id[x]=++sz;
    if(!son[x])return;
    bt(son[x],tp);
    fl(i,x)if(!top[to])bt(to,to);
}
ll fh(int x,int y){
    ll ans=0;
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]])SWAP(x,y);
        ans+=ask(id[top[x]],id[x]);x=f[top[x]];
    }
    if(id[x]>id[y])SWAP(x,y);
    return ans+ask(id[x],id[y]);
}
void ul(int x,int y,int k){
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]])SWAP(x,y);
        upd(id[top[x]],id[x],k);x=f[top[x]];
    }
    if(id[x]>id[y])SWAP(x,y);
    upd(id[x],id[y],k);
}
il int child(int x,int y){
    while(top[x]!=top[y]){
        x=top[x];
        if(f[x]==y)return x;
        x=f[x];
    }
    return son[y];
}
int main(){
    in(n);
    for(int i=1;i<=n;++i)in(c[i]);
    int q,x,y,opt,k;
    for(int i=2;i<=n;++i)
        in(f[i]),add(f[i],i);
    dfs(1);bt(1,1);
    for(int i=1;i<=n;++i)upd(id[i],id[i],c[i]);
    in(q);
    while(q--){
        in(opt,x);
        if(opt==1)RT=x;
        if(opt==2)in(y,k),ul(x,y,k);
        if(opt==3){
            in(k);
            if(x==RT)upd(1,n,k);
            else if(id[x]<=id[RT]&&id[RT]+siz[RT]<=id[x]+siz[x]){
                int t=child(RT,x);
                upd(1,k);
                upd(id[t],id[t]+siz[t]-1,-k);
            }
            else upd(id[x],id[x]+siz[x]-1,k);
        }
        if(opt==4)in(y),out(fh(x,y),ln);
        if(opt==5){
            if(x==RT)out(ask(n),ln);
            else if(id[x]<=id[RT]&&id[RT]+siz[RT]<=id[x]+siz[x]){
                int t=child(RT,x);
                out(ask(n)-ask(id[t],id[t]+siz[t]-1),ln);
            }
            else out(ask(id[x],id[x]+siz[x]-1),ln);
        }
    }
    flush();
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fl(i,x) for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
#define N 100011
int n,cnt=0,RT=1,head[N],c[N];
struct edge{
    int to,nxt;
}e[N];
void add(int x,int y){
    e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;
}
int a[N];
ll s[N<<2],laz[N<<2];
#define ls rt<<1
#define rs rt<<1|1
#define pu s[rt]=s[ls]+s[rs]
void pd(int rt,int ln,int rn){
    if(laz[rt]){
        laz[ls]+=laz[rt];
        laz[rs]+=laz[rt];
        s[ls]+=ln*laz[rt];
        s[rs]+=rn*laz[rt];
        laz[rt]=0;
    }
}
void build(int l,int r,int rt){
    if(l==r){
        s[rt]=a[l];
        return;
    }
    int m=(l+r)>>1;
    build(l,m,ls);build(m+1,r,rs);
    pu;
}
void upd(int L,int R,int v,int l,int r,int rt){
    if(L<=l&&r<=R){
        s[rt]+=v*(r-l+1);
        laz[rt]+=v;
        return;
    }
    int m=(l+r)>>1;
    pd(rt,m-l+1,r-m);
    if(L<=m)upd(L,R,v,l,m,ls);
    if(R>m)upd(L,R,v,m+1,r,rs);
    pu;
}
ll ask(int L,int R,int l,int r,int rt){
    if(L<=l&&r<=R)return s[rt];
    int m=(l+r)>>1;
    ll ans=0;
    pd(rt,m-l+1,r-m);
    if(L<=m)ans=ask(L,R,l,m,ls);
    if(R>m)ans+=ask(L,R,m+1,r,rs);
    return ans;
}
int son[N],siz[N],top[N],id[N],f[N],d[N],sz=0;
void dfs(int x){
    siz[x]=1;
    son[x]=0;
    fl(i,x){
        d[to]=d[x]+1;
        dfs(to);
        siz[x]+=siz[to];
        if(siz[to]>siz[son[x]])son[x]=to;
    }
}
void bt(int x,int tp){
    top[x]=tp;id[x]=++sz;a[id[x]]=c[x];
    if(!son[x])return;
    bt(son[x],tp);
    fl(i,x)if(!top[to])bt(to,to);
}
ll fh(int x,int y){
    ll ans=0;
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]])swap(x,y);
        ans+=ask(id[top[x]],id[x],1,n,1);x=f[top[x]];
    }
    if(id[x]>id[y])swap(x,y);
    return ans+ask(id[x],id[y],1,n,1);
}
void ul(int x,int y,int k){
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]])swap(x,y);
        upd(id[top[x]],id[x],k,1,n,1);x=f[top[x]];
    }
    if(id[x]>id[y])swap(x,y);
    upd(id[x],id[y],k,1,n,1);
}
int child(int x,int y){
    while(top[x]!=top[y]){
        x=top[x];
        if(f[x]==y)return x;
        x=f[x];
    }
    return son[y];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&c[i]);
    int q,x,y,opt,k;
    for(int i=2;i<=n;++i)
        scanf("%d",&f[i]),add(f[i],i);
    dfs(1);bt(1,1);
    build(1,n,1);
    scanf("%d",&q);
    while(q--){
        scanf("%d%d",&opt,&x);
        if(opt==1)RT=x;
        if(opt==2)scanf("%d%d",&y,&k),ul(x,y,k);
        if(opt==3){
            scanf("%d",&k);
            if(x==RT)upd(1,n,k,1,n,1);
            else if(id[x]<=id[RT]&&id[RT]+siz[RT]<=id[x]+siz[x]){
                int t=child(RT,x);
                upd(1,n,k,1,n,1);
                upd(id[t],id[t]+siz[t]-1,-k,1,n,1);
            }
            else upd(id[x],id[x]+siz[x]-1,k,1,n,1);
        }
        if(opt==4)scanf("%d",&y),printf("%lld\n",fh(x,y));
        if(opt==5){
            if(x==RT)printf("%lld\n",s[1]);
            else if(id[x]<=id[RT]&&id[RT]+siz[RT]<=id[x]+siz[x]){
                int t=child(RT,x);
                printf("%lld\n",s[1]-ask(id[t],id[t]+siz[t]-1,1,n,1));
            }
            else printf("%lld\n",ask(id[x],id[x]+siz[x]-1,1,n,1));
        }
    }
}
LOJ 139 树链剖分
comment评论
Search
search