【HAOI2015】【树链剖分】树上操作

题目描述

有一棵点数为 N 的树,以点 1 为根,且树点有边权。然后有 M 个操作,分为三种

操作 1 :把某个节点 x 的点权增加 a 。

操作 2 :把某个节点 x 为根的子树中所有点的点权都增加 a 。

操作 3 :询问某个节点 x 到根的路径中所有点的点权和。

输入输出格式

输入格式:

第一行包含两个整数 N, M 。表示点数和操作数。接下来一行 N 个整数,表示树中节点的初始权值。接下来 N-1 行每行两个正整数 from, to , 表示该树中存在一条边 (from, to) 。再接下来 M 行,每行分别表示一次操作。其中第一个数表示该操作的种类( 1-3 ) ,之后接这个操作的参数( x 或者 x a ) 。

输出格式:

对于每个询问操作,输出该询问的答案。答案之间用换行隔开。

输入输出样例

输入样例#1:

5 5
1 2 3 4 5
1 2
1 4
2 3
2 5
3 3
1 2 1
3 5
2 1 2
3 3

输出样例#1:

6
9
13

说明

对于 100% 的数据, $N,M<=100000$ ,且所有输入数据的绝对值都不会超过 $10^6$ 。


题目链接:https://www.luogu.org/problemnew/show/P3178

思路:直接套模板即可

这题是树剖的板子题

需要$define$ $int$ $long$ $long$是它最毒瘤的地方

上代码↓

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long

const int MAXN=1<<17;

int n,m,cnt,x,y,np,p;
int siz[MAXN],tp[MAXN],top[MAXN],sn[MAXN];
int val[MAXN],ren[MAXN],id[MAXN],fa[MAXN];
int h[MAXN];
long long tree[MAXN<<1],pls[MAXN<<1];
struct rpg{
    int li,nx;
}a[MAXN<<1];

void add(int ls,int nx){
    a[++np]=(rpg){h[ls],nx};
    h[ls]=np;
}

void init(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%lld",&val[i]);
    }for(int i=1;i<n;++i){
        scanf("%lld%lld",&x,&y);
        add(x,y);add(y,x);
    }return;
}

void dfs1(int x,int f,int deep){
    tp[x]=deep;
    siz[x]=1;
    fa[x]=f;
    int hwy=0;
    for(int i=h[x];i;i=a[i].li){
        if(a[i].nx!=f){
            dfs1(a[i].nx,x,deep+1);
            siz[x]+=siz[a[i].nx];
            if(siz[a[i].nx]>hwy){
                hwy=siz[a[i].nx];
                sn[x]=a[i].nx;
            }
        }
    }return;
}

void dfs2(int x,int tpx){
    id[x]=++cnt;
    ren[cnt]=val[x];
    top[x]=tpx;
    if(!sn[x]) return;
    dfs2(sn[x],tpx);
    for(int i=h[x];i;i=a[i].li){
        if(a[i].nx!=fa[x]&&a[i].nx!=sn[x]){
            dfs2(a[i].nx,a[i].nx);
        }
    }return;
}

void build(int k,int l,int r){
    if(l==r){
        tree[k]=ren[l];
        return;
    }int i=k<<1,mid=l+r>>1;
    build(i,l,mid);
    build(i|1,mid+1,r);
    tree[k]=tree[i]+tree[i|1];
}

void cadd(int k,int l,int r,int le,int ri,int x){
    if(le<=l&&r<=ri){
        tree[k]+=x*(r-l+1);
        pls[k]+=x;
        return;
    }int i=k<<1,mid=l+r>>1;
    if(le<=mid) cadd(i,l,mid,le,ri,x);
    if(mid<ri) cadd(i|1,mid+1,r,le,ri,x);
    tree[k]=tree[i]+tree[i|1]+pls[k]*(r-l+1);
}

long long ask(int k,int l,int r,int le,int ri,long long x){
    if(le<=l&&r<=ri) return tree[k]+x*(r-l+1);
    int i=k<<1,mid=l+r>>1;
    long long sum=0;
    if(le<=mid) sum+=ask(i,l,mid,le,ri,x+pls[k]);
    if(mid<ri) sum+=ask(i|1,mid+1,r,le,ri,x+pls[k]);
    return sum;
}

long long asks(int x,int y){
    long long sum=0;
    while(top[x]!=top[y]){
        if(tp[top[x]]<tp[top[y]]) swap(x,y);
        sum+=ask(1,1,n,id[top[x]],id[x],0);
        x=fa[top[x]];
    }if(tp[x]>tp[y]) swap(x,y);
    sum+=ask(1,1,n,id[x],id[y],0);
    return sum;
}

void solve(){
    while(m--){
        scanf("%lld",&p);
        if(p==1) scanf("%lld%lld",&x,&y),cadd(1,1,n,id[x],id[x],y);
        else if(p==2) scanf("%lld%lld",&x,&y),cadd(1,1,n,id[x],id[x]+siz[x]-1,y);
        else scanf("%lld",&x),printf("%lld\n",asks(1,x));
    }return;
}

main(){
    init();
    dfs1(1,0,1);
    dfs2(1,1);
    build(1,1,n);
    solve();
}