【BZOJ4034】【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 。

题解：
无脑树剖，就当练手。
当然dfs序+线段树也可以。

代码如下：

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<vector>
#define ll long long
#define inf 0x7f7f7f7f
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define N 100005
using namespace std;
ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while(ch>'9' || ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m; 
ll a[N];
int e[N<<1],nex[N<<1],hd[N],tot;
int siz[N],fa[N],bl[N],pos[N],mx[N],idx;
ll tag[N*3],sum[N*3];
void add(int a,int b)
{
    e[++tot]=b,nex[tot]=hd[a],hd[a]=tot;
    e[++tot]=a,nex[tot]=hd[b],hd[b]=tot;
}
void dfs(int u)
{
    siz[u]=1;
    for(int i=hd[u];i;i=nex[i])
    {
        if(e[i]==fa[u]) continue;
        fa[e[i]]=u;
        dfs(e[i]);
        siz[u]+=siz[e[i]];
    }
}
void dfs2(int u,int top)
{
    bl[u]=top;pos[u]=mx[u]=++idx;
    int son=0;
    for(int i=hd[u];i;i=nex[i])
    if(e[i]!=fa[u] && siz[e[i]]>siz[son]) son=e[i];
    if(son) dfs2(son,top),mx[u]=max(mx[u],mx[son]);
    for(int i=hd[u];i;i=nex[i])
    {
        if(e[i]==fa[u] || e[i]==son) continue;
        dfs2(e[i],e[i]);
        mx[u]=max(mx[u],mx[e[i]]);
    }
}
void pushdown(int rt,int l,int r)
{
    if(l==r) return;
    tag[ls]+=tag[rt],tag[rs]+=tag[rt];
    sum[ls]+=tag[rt]*(mid-l+1),sum[rs]+=tag[rt]*(r-mid);
    tag[rt]=0;
}
void ins(int rt,int l,int r,int L,int R,ll v)
{
    if(tag[rt]) pushdown(rt,l,r);
    if(l==L && r==R)
    {
        tag[rt]+=v;
        sum[rt]+=v*(r-l+1);
        return ;
    }
    if(L<=mid) ins(ls,l,mid,L,min(mid,R),v);
    if(R>mid) ins(rs,mid+1,r,max(mid+1,L),R,v);
    sum[rt]=sum[ls]+sum[rs];
}
ll query(int rt,int l,int r,int L,int R)
{
    if(tag[rt]) pushdown(rt,l,r);
    if(l==L && r==R) return sum[rt];
    ll ans=0;
    if(L<=mid) ans+=query(ls,l,mid,L,min(mid,R));
    if(R>mid) ans+=query(rs,mid+1,r,max(mid+1,L),R); 
    return ans;
}
ll query(int x)
{
    ll ans=0;
    while(bl[x]!=1)
    {
        ans+=query(1,1,n,pos[bl[x]],pos[x]);
        x=fa[bl[x]];
    }
    ans+=query(1,1,n,1,pos[x]);
    return ans;
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<n;i++) add(read(),read());
    dfs(1);
    dfs2(1,1);
    for(int i=1;i<=n;i++) ins(1,1,n,pos[i],pos[i],a[i]);
    for(int i=1;i<=m;i++)
    {
        int opt=read(),u=read();
        if(opt==3) printf("%lld\n",query(u));
        else
        {
            ll v=read();
            if(opt==1) ins(1,1,n,pos[u],pos[u],v);
            else ins(1,1,n,pos[u],mx[u],v);
        }
    }
    return 0;
}