[文章目录]
Description
有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个
操作，分为三种：
操作 1 ：把某个节点 x 的点权增加 a 。
操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。
N,M<=100000 ，且所有输入数据的绝对值都不会超过 10^6 。
没有子树移动，简单一个线段树维护出栈入栈序就好了吧。
不过这题好像是在树链剖分里的。
（弃掉zkw，开始练习结构体，毕竟有些什么区间染色，还有什么这个那个，zkw实现都很难啊。）不过练完splay之后，细节就清晰了好多。由于lazy[]没开long long WA了一次。然后就一A。开心。
结构体慢了点，但是好在如果是需要多个线段树的题目就方便多了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=101000;
typedef long long ll;
int n,m,in[N],out[N],val[N];
int head[N],to[N<<1],nxt[N<<1],cnt,tot;
int t[N<<1];
void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
void dfs(int x,int pre)
{
in[x]=++tot;
t[tot]=x;
for(int i=head[x];i;i=nxt[i])
if(to[i]!=pre)
dfs(to[i],x);
out[x]=++tot;
t[tot]=-x;
}
struct seg
{
ll sum[N<<3],lazy[N<<3];
int siz[N<<3];
void pushup(int pos)
{
siz[pos]=siz[pos<<1]+siz[pos<<1|1];
sum[pos]=sum[pos<<1]+sum[pos<<1|1];
}
void pushdown(int pos)
{
if(lazy[pos])
{
lazy[pos<<1]+=lazy[pos];
lazy[pos<<1|1]+=lazy[pos];
sum[pos<<1]+=1ll*lazy[pos]*siz[pos<<1];
sum[pos<<1|1]+=1ll*lazy[pos]*siz[pos<<1|1];
lazy[pos]=0;
}
}
void build(int pos,int l,int r)
{
if(l==r)
{
siz[pos]= t[l]>0 ? 1 : -1;
sum[pos]= t[l]>0 ? val[t[l]] : -val[-t[l]];
return ;
}
int mid=l+r>>1;
build(pos<<1,l,mid);
build(pos<<1|1,mid+1,r);
pushup(pos);
}
void fix(int pos,int l,int r,int x,int y,int w)
{
if(x<=l&&y>=r)
{
lazy[pos]+=w;
sum[pos]+=1ll*w*siz[pos];
return ;
}
pushdown(pos);
int mid=l+r>>1;
if(y<=mid) fix(pos<<1,l,mid,x,y,w);
else if(x>mid) fix(pos<<1|1,mid+1,r,x,y,w);
else fix(pos<<1,l,mid,x,y,w),fix(pos<<1|1,mid+1,r,x,y,w);
pushup(pos);
}
ll query(int pos,int l,int r,int x,int y)
{
if(x<=l&&y>=r) return sum[pos];
pushdown(pos);
int mid=l+r>>1;
if(y<=mid) return query(pos<<1,l,mid,x,y);
else if(x>mid) return query(pos<<1|1,mid+1,r,x,y);
else return query(pos<<1,l,mid,x,y)+query(pos<<1|1,mid+1,r,x,y);
}
}tree;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&val[i]);
for(int x,y,z,i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
dfs(1,0);
tree.build(1,1,n<<1);
int sw;
while(m--)
{
scanf("%d",&sw);
switch(sw)
{
case 1:
{
int id,w; scanf("%d%d",&id,&w);
tree.fix(1,1,tot,in[id],in[id],w);
tree.fix(1,1,tot,out[id],out[id],w);
break;
}
case 2:
{
int id,w; scanf("%d%d",&id,&w);
tree.fix(1,1,tot,in[id],out[id],w);break;
}
case 3:
{
int id; scanf("%d",&id);
printf("%lld\n",tree.query(1,1,tot,1,in[id]));break;
}
}
}
return 0;
}