【BZOJ3786】星系探索 | Mrsrz's blog

ETT。

题目大意：

给定一棵以 $1$ 为根的树，带点权，要求支持以下操作：

1. 给定 $u$，询问 $u$ 到根路径的点权和。
2. 给定 $u,v$，将 $u$ 的父亲改成 $v$。
3. 给定 $u,w$，将以 $u$ 为根的子树中的所有点的点权加上 $w$。

题解：

本题有加边、删边操作，但是要求支持对子树的修改，LCT 并不太容易做（据说可以）。

这题比较方便的做法是使用 Euler Tour Tree，其本质上是维护原树的欧拉序，支持子树修改、动态加、删边。但不支持换根操作所以有换根就要 Top Tree 了。

我们对树进行 dfs 遍历，在第一次到这个结点和从这个结点向上返回的时候，分别加在数列末尾。这样得到的就是树的欧拉序。

我们令进入时的贡献为正，离开时的贡献为负。容易发现，一个结点到根路径上的点权和，就是这个结点的入点结尾的前缀的和（不在路径上的点要么左右抵消，要么在后面）。

考虑换父亲的操作，就是把一棵子树整体移到另一个结点下面。

那么对于欧拉序的变化，显然是一段连续的区间移动到另一个位置。

这个操作可以使用平衡树完成。

然后子树加的操作，就对应平衡树的区间修改。前缀查询，就对应平衡树的区间查询。

可以在 $O(n+m\log n)$ 的时间复杂度内完成。

Code：

#include<iostream>
#include<ctime>
using namespace std;
typedef long long LL;
const int N=2e5+6;
int fa[N],n,head[N],cnt,W[N],m;
struct edge{
    int to,nxt;
}e[N];
unsigned sd;
inline unsigned Rand(){sd^=sd<<13,sd^=sd>>17,sd^=sd<<5;return sd;}
namespace ett{
    struct node{
        int ls,rs,sz,tp,fa,ssz;LL val,tag,sum;
    }d[N];
    int sta[N],top,rt;
    inline void pushdown(int x){
        const int ls=d[x].ls,rs=d[x].rs;
        LL&s=d[x].tag;
        if(ls)d[ls].tag+=s,d[ls].val+=s,d[ls].sum+=s*d[ls].ssz;
        if(rs)d[rs].tag+=s,d[rs].val+=s,d[rs].sum+=s*d[rs].ssz;
        s=0;
    }
    inline void update(int x){
        const int ls=d[x].ls,rs=d[x].rs;
        d[x].sz=d[ls].sz+d[rs].sz+1;
        d[x].ssz=d[ls].ssz+d[rs].ssz+d[x].tp;
        d[x].sum=d[ls].sum+d[rs].sum+d[x].val*d[x].tp;
        if(ls)d[ls].fa=x;
        if(rs)d[rs].fa=x;
    }
    int merge(int x,int y){
        if(!x||!y)return x|y;
        pushdown(x),pushdown(y);
        if(Rand()%(d[x].sz+d[y].sz)<d[x].sz){
            d[x].rs=merge(d[x].rs,y),update(x);
            return x;
        }else{
            d[y].ls=merge(x,d[y].ls),update(y);
            return y;
        }
    }
    void split(int u,int k,int&x,int&y){
        if(!u)x=y=0;else
        if(k==0)x=0,y=u;else
        if(k==d[u].sz)x=u,y=0;else{
            pushdown(u);
            if(d[d[u].ls].sz>=k)split(d[u].ls,k,x,d[u].ls),y=u,d[x].fa=0;else
            split(d[u].rs,k-1-d[d[u].ls].sz,d[u].rs,y),x=u,d[y].fa=0;
            update(u);
        }
    }
    int Rank(int x){
        int res=d[d[x].ls].sz+1;
        for(int y=d[x].fa;y;x=y,y=d[y].fa)if(d[y].rs==x)res+=d[d[y].ls].sz+1;
        return res;
    }
    void dfs(int now){
        d[now]=(node){0,0,1,1,0,1,W[now],0,W[now]};
        sta[++top]=now;
        for(int i=head[now];i;i=e[i].nxt)dfs(e[i].to);
        sta[++top]=now+n;
        d[now+n]=(node){0,0,1,-1,0,-1,W[now],0,-W[now]};
    }
    void init(int l=1,int r=top,int&x=rt){
        if(l>r)return;
        const int mid=l+r>>1;
        x=sta[mid];
        init(l,mid-1,d[x].ls),init(mid+1,r,d[x].rs);
        update(x);
    }
    LL ask(int x){
        int a=0,b=0,rk=Rank(x);
        split(rt,rk,a,b);
        LL res=d[a].sum;
        rt=merge(a,b);
        return res;
    }
    void modify(int x,int v){
        int a=0,b=0,c=0,rk1=Rank(x),rk2=Rank(x+n);
        split(rt,rk2,rt,c);
        split(rt,rk1-1,a,b);
        d[b].val+=v,d[b].tag+=v,d[v].sum+=(LL)v*d[b].ssz;
        rt=merge(merge(a,b),c);
    }
    void link_cut(int x,int f){
        int a=0,b=0,c=0,rk1=Rank(x),rk2=Rank(x+n);
        split(rt,rk2,rt,c);
        split(rt,rk1-1,a,b);
        rt=merge(a,c);
        split(rt,Rank(f),a,c);
        rt=merge(merge(a,b),c);
    }
}
int main(){
    sd=time(0)^114514;
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=2;i<=n;++i){
        cin>>fa[i];
        e[++cnt]=(edge){i,head[fa[i]]},head[fa[i]]=cnt;
    }
    for(int i=1;i<=n;++i)cin>>W[i];
    ett::dfs(1);
    ett::init();
    cin>>m;
    while(m--){
        char op[3];
        cin>>op;
        switch(*op){
            case'Q':{
                int x;
                cin>>x;
                cout<<ett::ask(x)<<'\n';
                break;
            }
            case'C':{
                int x,y;
                cin>>x>>y;
                ett::link_cut(x,y);
                break;
            }
            case'F':{
                int x,v;
                cin>>x>>v;
                if(v)ett::modify(x,v);
                break;
            }
        }
    }
    return 0;
}