bzoj 4034: [HAOI2015]树上操作—

Description

有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个

操作，分为三种：

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

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

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

Input

第一行包含两个整数 N, M 。表示点数和操作数。接下来一行 N 个整数，表示树中节点的初始权值。接下来 N-1

行每行三个正整数 fr, to ，表示该树中存在一条边 (fr, to) 。再接下来 M 行，每行分别表示一次操作。其中

第一个数表示该操作的种类（ 1-3 ），之后接这个操作的参数（ x 或者 x a ）。

Output

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

Sample Input

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

Sample Output

6
9
13

HINT

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

—————————————————————————————

这道题其实也是裸题QAQ 子树求和就是求个子树内id最大的点从根到这个点的编号刚好包含了整个子树

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

const int M=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int max(int x,int y){return x>y?x:y;}

int n,m;

int first[M],cnt=;

struct node{int to,next;}e[*M];

void ins(int a,int b){e[++cnt]=(node){b,first[a]}; first[a]=cnt;}

void insert(int a,int b){ins(a,b); ins(b,a);}

int top[M],sz[M],son[M],mx[M],fa[M],id[M],idp=;

void f1(int x){

    sz[x]=;

    for(int i=first[x];i;i=e[i].next){

        int now=e[i].to;

        if(now==fa[x]) continue;

        fa[now]=x; f1(now);

        sz[x]+=sz[now];

        if(sz[now]>sz[son[x]]) son[x]=now;

    }

}

void f2(int x,int tp){

    top[x]=tp; mx[x]=id[x]=idp++;

    if(son[x]) f2(son[x],tp),mx[x]=max(mx[x],mx[son[x]]);

    for(int i=first[x];i;i=e[i].next){

        int now=e[i].to;

        if(now!=fa[x]&&now!=son[x]) f2(now,now),mx[x]=max(mx[x],mx[now]);

    }

}

struct pos{int l,r; LL sum,tag;}tr[*M];

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

    tr[x].l=l; tr[x].r=r;

    if(l==r) return ;

    int mid=(l+r)>>;

    build(x<<,l,mid);

    build(x<<^,mid+,r);

}

void up(int x){tr[x].sum=tr[x<<].sum+tr[x<<^].sum;}

void down(int x){

    if(tr[x].tag){

        int ls=x<<,rs=x<<^;

        LL v=tr[x].tag;

        tr[x].tag=; tr[ls].tag+=v; tr[rs].tag+=v;

        tr[ls].sum+=1LL*(tr[ls].r-tr[ls].l+)*v;

        tr[rs].sum+=1LL*(tr[rs].r-tr[rs].l+)*v;

    }

}

void modify(int x,int L,int R,LL s){

    if(L<=tr[x].l&&tr[x].r<=R){tr[x].tag+=s; tr[x].sum+=(tr[x].r-tr[x].l+)*s; return ;}

    down(x);

    int mid=(tr[x].l+tr[x].r)>>;

    if(L<=mid) modify(x<<,L,R,s);

    if(R>mid) modify(x<<^,L,R,s);

    up(x);

}

LL v[M];

LL push_sum(int x,int L,int R){

    if(L<=tr[x].l&&tr[x].r<=R) return tr[x].sum;

    down(x);

    int mid=(tr[x].l+tr[x].r)>>;

    LL ans=;

    if(L<=mid) ans+=push_sum(x<<,L,R);

    if(R>mid)  ans+=push_sum(x<<^,L,R);

    return ans;

}

LL qsum(int x){

    LL sum=;

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

        sum+=push_sum(,id[top[x]],id[x]);

        x=fa[top[x]];

    }

    sum+=push_sum(,id[],id[x]);

    return sum;

}

int main(){

    int k,x,y;

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

    for(int i=;i<=n;i++) v[i]=read();

    for(int i=;i<n;i++) x=read(),y=read(),insert(x,y);

    build(,,n); f1(); f2(,);

    for(int i=;i<=n;i++) modify(,id[i],id[i],v[i]);

    for(int i=;i<=m;i++){

        k=read();

        if(k==) x=read(),y=read(),modify(,id[x],id[x],y);

        else if(k==) x=read(),y=read(),modify(,id[x],mx[x],y);

        else x=read(),printf("%lld\n",qsum(x));

    }

    return ;

}

巴特西

bzoj 4034: [HAOI2015]树上操作——树链剖分