这道题是裸的树链剖分算法

这道题是裸的树链剖分算法

这道题是裸的树链剖分算法

我觉得还可以。因为我读优忘记写负数了。

然后对于点操作,线段树从自己到自己增加就行了。

然后和 P3384 【模板】树链剖分 一模一样的做法,简直就是双倍经验

#include<iostream>
#include<cstdio>
using namespace std;

struct edge{
    long long to,next;
}e[200010];
long long n,m,len,tot;
long long a[100010],tree[400010],lazy[400010];
long long head[100010],real[100010],id[100010],fa[100010],hson[100010],dep[100010],size[100010],top[100010];

long long v_in(){//快读 
    long long sum=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f*=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        sum=sum*10+ch-'0';
        ch=getchar();
    }
    return sum*f;
}

void add(long long u,long long v){//加边 
    e[++len].to=v;
    e[len].next=head[u];
    head[u]=len;
}

/*线段树(Segment Tree)*/ 

void pushup(long long rt){//上推 
    tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}

void pushdown(long long rt,long long ln,long long rn){//下推 
    if (lazy[rt]){
        tree[rt<<1]+=lazy[rt]*ln;
        tree[rt<<1|1]+=lazy[rt]*rn;
        lazy[rt<<1]+=lazy[rt];
        lazy[rt<<1|1]+=lazy[rt];
        lazy[rt]=0;
    }
}

void build(long long l,long long r,long long rt){//建树 
    if (l==r){
        tree[rt]=a[real[l]];
        return;
    }
    long long mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);
}

void update(long long l,long long r,long long rt,long long left,long long right,long long c){//修改操作 
    if (l>=left&&r<=right){
        tree[rt]+=c*(r-l+1);
        lazy[rt]+=c;
        return;
    }
    long long mid=(l+r)>>1;
    pushdown(rt,mid-l+1,r-mid);
    if (mid>=left) update(l,mid,rt<<1,left,right,c);
    if (mid+1<=right) update(mid+1,r,rt<<1|1,left,right,c);
    pushup(rt);
}

long long query(long long l,long long r,long long rt,long long left,long long right){//询问操作 
    if (l>=left&&r<=right) return tree[rt];
    long long mid=(l+r)>>1,ans=0;
    pushdown(rt,mid-l+1,r-mid);
    if (mid>=left) ans+=query(l,mid,rt<<1,left,right);
    if (mid+1<=right) ans+=query(mid+1,r,rt<<1|1,left,right);
    pushup(rt);
    return ans;
}

/*树链剖分*/

void dfs1(long long u,long long f){//第一遍深搜(建树,记录fa,size,dep,hson) 
    fa[u]=f;
    size[u]=1;
    for (long long i=head[u];i!=0;i=e[i].next){
        long long v=e[i].to;
        if (fa[u]!=v){
            dep[v]=dep[u]+1;
            dfs1(v,u);
            if (hson[u]==0||size[hson[u]]<size[v]) hson[u]=v;
            size[u]+=size[v];
        }
    }
}

void dfs2(long long u,long long anc){//第二遍深搜(分链,重新编号,记录top,id,real) 
    top[u]=anc;
    id[u]=++tot;
    real[tot]=u;
    if (hson[u]==0) return;
    dfs2(hson[u],anc);
    for (long long i=head[u];i!=0;i=e[i].next){
        long long v=e[i].to;
        if (v!=fa[u]&&v!=hson[u]) dfs2(v,v);
    }
}

void point_add(){//1操作 
    long long x=v_in(),w=v_in();
    update(1,n,1,id[x],id[x],w);
}

void tree_add(){//2操作 
    long long x=v_in(),w=v_in();
    update(1,n,1,id[x],id[x]+size[x]-1,w);
}

void chain_query(){//3操作 
    long long u=v_in();
    long long tu=top[u],ans=0;
    while (tu!=1){
        ans+=query(1,n,1,id[tu],id[u]);
        u=fa[tu];
        tu=top[u];
    }
    ans+=query(1,n,1,id[1],id[u]);
    printf("%lld\n",ans);
}

main(){
    n=v_in();
    m=v_in();
    for (long long i=1;i<=n;i++) a[i]=v_in();
    for (long long i=1;i<n;i++){
        long long u=v_in(),v=v_in();
        add(u,v);//无向边 
        add(v,u);
    }
    dep[1]=1;
    dfs1(1,0);
    dfs2(1,1);
    build(1,n,1);
    for (long long i=1;i<=m;i++){
        long long q=v_in();
        if (q==1) point_add();
        else if (q==2) tree_add();
        else chain_query();
    }
    return 0;
}