NC23051 华华和月月种树(树剖+离线)

题目链接

题意：
初始有一零结点，权值为0，根据相应操作维护这棵动态有根树。
操作 1：输入格式 1 i ，表示使节点 i 长出了一个新的儿子节点，权值为0，编号为当前最大编号 +1。
操作 2：输入格式 2 i a ，表示使节点 i 的子树中所有节点（即它和它的所有子孙节点）权值加 a 。
操作 3：输入格式 3 i，输出节点i权值。

题解：
因为树的结点是动态变化的，无法在线维护，先求出总连接情况，然后考虑用特殊方法维护结点值。
对于固定连接情况的树，其权值情况可通过树链剖分维护出来。
通过结点加入的先后顺序关系，容易想到在一结点诞生时记录其权值，待询问时求出此时权值再减去诞生时权值即为该结点的真正权值。

代码如下：

#include<bits/stdc++.h>
#define len (r-l+1)
#define ls p<<1,l,mid
#define rs p<<1|1,mid+1,r
using namespace std;
const int nx=1e5+5;
int h[nx],to[nx<<1],nxt[nx<<1],cnt;
int a[nx<<2],laz[nx<<2];
int son[nx],id[nx],fa[nx],dep[nx],siz[nx],top[nx],df;
struct node{
    int a,b,c;
}s[nx<<2];
inline void add(int u,int v){
    to[++cnt]=v,nxt[cnt]=h[u],h[u]=cnt;
    to[++cnt]=u,nxt[cnt]=h[v],h[v]=cnt;
}
inline void read(int &x){
    x=0;char c=getchar();
    for(;c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
        x=(x<<1)+(x<<3)+(c&15);
}
void pushdown(int p,int tot){
    laz[p<<1]+=laz[p],laz[p<<1|1]+=laz[p];
    a[p<<1]=a[p<<1]+laz[p]*(tot-tot/2);
    a[p<<1|1]=a[p<<1|1]+tot/2*laz[p];
    laz[p]=0;
}
void up(int p,int l,int r,int x,int y,int z){
    if(x<=l&&r<=y){
        laz[p]+=z,a[p]=a[p]+z*len;
        return;
    }
    if(laz[p])pushdown(p,len);
    int mid=(l+r)>>1;
    if(x<=mid)up(ls,x,y,z);
    if(mid<y)up(rs,x,y,z);
    a[p]=a[p<<1]+a[p<<1|1];
}
int get(int p,int l,int r,int x){
    if(l==r)return a[p];
    if(laz[p])pushdown(p,len);
    int mid=l+r>>1;
    if(x<=mid)return get(ls,x);
    return get(rs,x);
}
void dfs1(int x,int f,int deep){
    dep[x]=deep,fa[x]=f,siz[x]=1;
    int mx=-1,y;
    for(int i=h[x];i;i=nxt[i]){
        y=to[i];
        if(y==f)continue;
        dfs1(y,x,deep+1);
        siz[x]+=siz[y];
        if(siz[y]>mx)mx=siz[y],son[x]=y;
    }
}
void dfs2(int x,int gf){
    id[x]=++df,top[x]=gf;
    if(!son[x])return;
    dfs2(son[x],gf);
    for(int i=h[x];i;i=nxt[i]){
        int y=to[i];
        if(y==fa[x]||y==son[x])continue;
        dfs2(y,y);
    }
}
int val[nx];
int main(){
    int n,op,i,d,now=0;
    read(n);
    for(int j=0;j<n;++j){
        read(op),read(i);
        if(op==1)add(++now,i),s[j]={1,i,now};
        else if(op==2)read(d),s[j]={2,i,d};
        else s[j]={3,i,0};
    }
    dfs1(0,-1,1),dfs2(0,0);
    ++now;//含零总结点数 
    for(int j=0;j<n;++j){
        op=s[j].a,i=s[j].b,d=s[j].c;
        if(op==1)val[d]=get(1,1,now,id[d]);
        else if(op==2)up(1,1,now,id[i],id[i]+siz[i]-1,d);
        else printf("%d\n",get(1,1,now,id[i])-val[i]);
    }
}