【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
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
9
13
HINT
对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不
会超过 10^6 。
题解:树剖的模板题，注意要开long long
#include <stdio.h>
#include <string.h>
#include <iostream>
#define lson x<<1
#define rson x<<1|1
using namespace std;
typedef long long ll;
const int maxn=100010;
int n,m,cnt,tot;
ll s[maxn<<2],tag[maxn<<2];
int to[maxn<<1],next[maxn<<1],v[maxn],u[maxn],fa[maxn],head[maxn];
int deep[maxn],size[maxn],son[maxn],p[maxn],top[maxn];
char str[10];
int readin()
{
int ret=0,sig=1; char gc;
while(gc<'0'||gc>'9') sig=(gc=='-')?-1:1,gc=getchar();
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*sig;
}
void add(int a,int b)
{
to[cnt]=b;
next[cnt]=head[a];
head[a]=cnt++;
}
void dfs1(int x)
{
size[x]=1;
for(int i=head[x];i!=-1;i=next[i])
{
if(to[i]!=fa[x])
{
fa[to[i]]=x;
deep[to[i]]=deep[x]+1;
dfs1(to[i]);
size[x]+=size[to[i]];
if(size[to[i]]>size[son[x]]) son[x]=to[i];
}
}
}
void dfs2(int x,int tp)
{
top[x]=tp;
p[x]=++tot;
v[p[x]]=u[x];
if(son[x]) dfs2(son[x],tp);
for(int i=head[x];i!=-1;i=next[i])
if(to[i]!=son[x]&&to[i]!=fa[x])
dfs2(to[i],to[i]);
}
void pushup(int x)
{
s[x]=s[lson]+s[rson];
}
void pushdown(int l,int r,int x)
{
int mid=l+r>>1;
tag[lson]+=tag[x],tag[rson]+=tag[x];
s[lson]+=tag[x]*(long long)(mid-l+1),s[rson]+=tag[x]*(long long)(r-mid);
tag[x]=0;
}
void build(int l,int r,int x)
{
if(l==r)
{
s[x]=v[l];
return ;
}
int mid=l+r>>1;
build(l,mid,lson),build(mid+1,r,rson);
pushup(x);
}
void updata(int l,int r,int x,int a,int b,int c)
{
if(a<=l&&r<=b)
{
s[x]+=c*(long long)(r-l+1),tag[x]+=c;
return ;
}
pushdown(l,r,x);
int mid=l+r>>1;
if(b<=mid) updata(l,mid,lson,a,b,c);
else if(a>mid) updata(mid+1,r,rson,a,b,c);
else updata(l,mid,lson,a,b,c),updata(mid+1,r,rson,a,b,c);
pushup(x);
}
ll query(int l,int r,int x,int a,int b)
{
if(a<=l&&r<=b) return s[x];
pushdown(l,r,x);
int mid=l+r>>1;
if(b<=mid) return query(l,mid,lson,a,b);
if(a>mid) return query(mid+1,r,rson,a,b);
return query(l,mid,lson,a,b)+query(mid+1,r,rson,a,b);
}
void change()
{
int x=readin(),y=readin();
updata(1,n,1,p[x],p[x],y);
}
void Add()
{
int x=readin(),y=readin();
updata(1,n,1,p[x],p[x]+size[x]-1,y); //修改整棵子树
}
void getans()
{
int x=readin();
ll ans=0;
while(top[x]!=1)
{
ans+=query(1,n,1,p[top[x]],p[x]);
x=fa[top[x]];
}
ans+=query(1,n,1,1,p[x]);
printf("%lld
",ans);
}
int main()
{
n=readin(),m=readin();
memset(head,-1,sizeof(head));
int i,a,b;
for(i=1;i<=n;i++) u[i]=readin();
for(i=1;i<n;i++)
{
a=readin(),b=readin();
add(a,b),add(b,a);
}
deep[1]=1;
dfs1(1);
dfs2(1,1);
build(1,n,1);
for(i=1;i<=m;i++)
{
a=readin();
switch(a)
{
case 1:change(); break;
case 2:Add(); break;
case 3:getans(); break;
}
}
return 0;
}