@[bellmanford](/space/show?uid=116015)
by 清远学会 @ 2019-10-13 18:15:58
你的change1里赋值出错了
by 清远学会 @ 2019-10-13 18:16:36
```cpp
void change1(int u,int l,int r,int x,int d){
pushdown(u);
if(l==r){
tr[u].sum+=d;
tr[u].maxn+=d;
return ;
}
int mid=(l+r)>>1;
if(x<=mid) change1(u<<1,l,mid,x,d);
else change1(u<<1|1,mid+1,r,x,d);
pushup(u);
}
```
by 清远学会 @ 2019-10-13 18:16:53
放上刚A的代码，有点改动：
```cpp#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
const int M=2e5+5;
int n,m,cnt=0,tot=0,a[M],first[M];
int de[M],fa[M],son[M],top[M],num[M],pre[M],size[M];
struct Edge{
int nxt,to;
}e[M];
struct Tree{
int len,sum,maxn,lazy;
}tr[M<<2];
int read(){
int x=0,y=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') y=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*y;
}
void add(int x,int y){
tot++;
e[tot].nxt=first[x];
first[x]=tot;
e[tot].to=y;
}
void dfs1(int u,int f){
de[u]=de[f]+1;
fa[u]=f;
size[u]=1;
for(int i=first[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==f) continue;
dfs1(v,u);
size[u]+=size[v];
if(size[v]>size[son[u]]) son[u]=v;
}
}
void dfs2(int u,int tp){
num[u]=++cnt;
pre[cnt]=u;
top[u]=tp;
if(son[u]) dfs2(son[u],tp);
for(int i=first[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
void pushup(int u){
tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
tr[u].maxn=max(tr[u<<1].maxn,tr[u<<1|1].maxn);
}
void pushdown(int u){
if(tr[u].lazy){
tr[u<<1].lazy+=tr[u].lazy;
tr[u<<1|1].lazy+=tr[u].lazy;
tr[u<<1].sum+=tr[u<<1].len*tr[u].lazy;
tr[u<<1|1].sum+=tr[u<<1|1].len*tr[u].lazy;
}
tr[u].lazy=0;
}
void build(int u,int l,int r){
tr[u].len=r-l+1;
tr[u].lazy=0;
if(l==r){
tr[u].maxn=tr[u].sum=a[pre[l]];
return ;
}
int mid=(l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
void change1(int u,int l,int r,int x,int d){
pushdown(u);
if(l==r){
tr[u].sum+=d;
tr[u].maxn+=d;
return ;
}
int mid=(l+r)>>1;
if(x<=mid) change1(u<<1,l,mid,x,d);
else change1(u<<1|1,mid+1,r,x,d);
pushup(u);
}
void change2(int u,int l,int r,int L,int R,int d){
pushdown(u);
if(L<=l&&R>=r){
tr[u].sum+=tr[u].len*d;
tr[u].lazy+=d;
return ;
}
int mid=(l+r)>>1;
if(L <= mid) change2(u<<1,l,mid,L,R,d);
if(R > mid)change2(u<<1|1,mid+1,r,L,R,d);
pushup(u);
}
int query(int u,int l,int r,int L,int R){
pushdown(u);
if(L <= l && r <= R) return tr[u].sum;
int mid = (l + r) >> 1,res = 0;
if(L <= mid) res += query(u << 1,l,mid,L,R);
if(R > mid) res += query(u << 1 | 1,mid + 1,r,L,R);
return res;
}
int qsum(int x,int y){
int res=0;
while(top[x]!=top[y]){
if(de[top[x]]<de[top[y]]) swap(x,y);
res+=query(1,1,n,num[top[x]],num[x]);
x=fa[top[x]];
}
if(num[x]<num[y]) swap(x,y);
res+=query(1,1,n,num[y],num[x]);
return res;
}
signed main(){
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n-1;i++){
int x=read(),y=read();
add(x,y),add(y,x);
}
dfs1(1,1),dfs2(1,1),build(1,1,n);
while(m--){
int opt=read();
if(opt==1){
int x=read(),d=read();
change1(1,1,n,num[x],d);
}
if(opt==2){
int x=read(),d=read();
change2(1,1,n,num[x],num[x]+size[x]-1,d);
}
if(opt==3){
int x=read();
printf("%lld\n",qsum(1,x));
}
}
}
```
by 清远学会 @ 2019-10-13 18:17:32
@[清远学会](/space/show?uid=153839) 太感谢了
抱歉现在才看到
by bellmanford @ 2019-10-13 20:42:27