P3178 [HAOI2015]树上操作

思路

板子嘛，其实我感觉树剖没啥脑子

就是debug

代码

#include <bits/stdc++.h>

#define int long long

#define ll long long

#define ls rt<<1

#define rs rt<<1|1

#define FOR(i,a,b) for(int i=a;i<=b;++i)

using namespace std;

const int maxn=1e6+7;

int read() {

    int x=0,f=1;char s=getchar();

    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

    return x*f;

}

int n,m,w[maxn];

int dep[maxn],son[maxn],fa[maxn],siz[maxn];

int a[maxn],idx[maxn],top[maxn],cnt;

struct node {

    int v,nxt;

}e[maxn<<1];

int head[maxn<<1],tot;

void add_edge(int u,int v) {

    e[++tot].v=v;

    e[tot].nxt=head[u];

    head[u]=tot;

}

namespace seg_tree {

    struct node {

        int l,r,siz;

        ll tot,lazy;

    }e[maxn<<2];

    void pushup(int rt) {

        e[rt].tot=e[ls].tot+e[rs].tot;

    }

    void pushdown(int rt) {

        if(e[rt].lazy) {

            e[ls].tot+=e[ls].siz*e[rt].lazy;

            e[rs].tot+=e[rs].siz*e[rt].lazy;

            e[ls].lazy+=e[rt].lazy;

            e[rs].lazy+=e[rt].lazy;

            e[rt].lazy=0;

        }

    }

    void build(int l,int r,int rt) {

        e[rt].l=l,e[rt].r=r,e[rt].siz=r-l+1;

        if(l==r) {

            e[rt].tot=a[l];

            return;

        }

        int mid=(l+r)>>1;

        build(l,mid,ls);

        build(mid+1,r,rs);

        pushup(rt);

    }

    void modify(int L,int R,int k,int rt) {

        if(L<=e[rt].l&&e[rt].r<=R) {

            e[rt].tot+=e[rt].siz*k;

            e[rt].lazy+=k;

            return;

        }

        pushdown(rt);

        int mid=(e[rt].l+e[rt].r)>>1;

        if(L<=mid) modify(L,R,k,ls);

        if(R>mid) modify(L,R,k,rs);

        pushup(rt);

    }

    ll query(int L,int R,int rt) {

        if(L<=e[rt].l&&e[rt].r<=R) return e[rt].tot;

        pushdown(rt);

        int mid=(e[rt].l+e[rt].r)>>1;

        ll ans=0;

        if(L<=mid) ans+=query(L,R,ls);

        if(R>mid) ans+=query(L,R,rs);

        return ans;

    }

}

void dfs1(int u,int f) {

    siz[u]=1;

    fa[u]=f;

    son[u]=0;

    dep[u]=dep[f]+1;

    for(int i=head[u];i;i=e[i].nxt) {

        int v=e[i].v;

        if(v==f) continue;

        dfs1(v,u);

        if(siz[v] > siz[son[u]]) son[u]=v;

        siz[u]+=siz[v];

    }

}

void dfs2(int u,int ttt) {

    idx[u]=++cnt;

    a[cnt]=w[u];

    top[u]=ttt;

    if(!son[u]) return;

    dfs2(son[u],ttt);

    for(int i=head[u];i;i=e[i].nxt) {

        if(!idx[e[i].v])

            dfs2(e[i].v,e[i].v);

    }

}

ll SUM(int x,int y) {// 路径

    ll ans=0;

    while(top[x]!=top[y]) {

        if(dep[top[x]]<dep[top[y]]) swap(x,y);

        ans+=seg_tree::query(idx[top[x]],idx[x],1);

        x=fa[top[x]];

    }

    if(dep[x]>dep[y]) swap(x,y);

    ans+=seg_tree::query(idx[x],idx[y],1);

    return ans;

}

main() {

    n=read(),m=read();

    FOR(i,1,n) w[i]=read();

    FOR(i,2,n) {

        int x=read(),y=read();

        add_edge(x,y);

        add_edge(y,x);

    }

    dfs1(1,0);

    dfs2(1,1);

    seg_tree::build(1,n,1);

    FOR(i,1,m) {

        int opt=read(),x=read(),a;

        if(opt==1) {

            a=read();

            seg_tree::modify(idx[x],idx[x],a,1);

        } else if(opt==2) {

            a=read();

            seg_tree::modify(idx[x],idx[x]+siz[x]-1,a,1);

        } else if(opt==3) {

            cout<<SUM(1,x)<<"\n";

        }

    }

    return 0;

}