@[JBLee](/space/show?uid=108746) emmm……Update1的pushdown呢？
by x义x @ 2019-07-28 17:27:15
@[JBLee](/space/show?uid=108746) emmm……
给您我封装的线段树，您换进去试试
```cpp
struct Tree{
long long ans[100005<<2],tag[100005<<2],a[100005];
inline long long lson(long long p){return p<<1;}
inline long long rson(long long p){return (p<<1)|1;}
inline void push_up(long long p){ans[p]=ans[lson(p)]+ans[rson(p)];}
inline void build(long long p,long long l,long long r){
if (l==r){ans[p]=a[l];return ;}
long long mid=(l+r)>>1;
build(lson(p),l,mid);
build(rson(p),mid+1,r);
push_up(p);
tag[p]=0;
}
inline void lazy_tag(long long p,long long l,long long r,long long k){ans[p]+=(r-l+1)*k;tag[p]+=k;}
inline void push_down(long long p,long long l,long long r){
long long mid=(l+r)>>1;
lazy_tag(lson(p),l,mid,tag[p]);
lazy_tag(rson(p),mid+1,r,tag[p]);
tag[p]=0;
}
inline void change(long long p,long long nl,long long nr,long long l,long long r,long long k){
if (nl<=l&&nr>=r){ans[p]+=(r-l+1)*k,tag[p]+=k;return;}
if (nl>r||nr<l)return;
long long mid=(l+r)>>1;
push_down(p,l,r);
change(lson(p),nl,nr,l,mid,k);
change(rson(p),nl,nr,mid+1,r,k);
push_up(p);
}
inline long long ask(long long p,long long nl,long long nr,long long l,long long r){
if (nl<=l&&nr>=r)return ans[p];
if (nl>r||nr<l)return 0;
long long mid=(l+r)>>1,res=0;
push_down(p,l,r);
res+=ask(lson(p),nl,nr,l,mid);
res+=ask(rson(p),nl,nr,mid+1,r);
return res;
}
}tree;
```
以及我的AC代码
```cpp
#include<bits/stdc++.h>
#pragma GCC optimize(3)
using namespace std;
#define int long long
const int N=4e5+1;
struct node{
int v,nex;
}t[N<<1];
int las[N],n,m,gg[N<<2],lazy[N<<2],W[N],w[N],dep[N],fa[N],son[N],siz[N],top[N],id[N],cnt,len;
inline void update(int now,int l,int r,int x){
gg[now]+=1LL*(r-l+1)*x;
lazy[now]+=x;
return;
}
inline void down(int now,int l,int r){
int mid=(l+r)>>1;
update(now<<1,l,mid,lazy[now]),update(now<<1|1,mid+1,r,lazy[now]);
lazy[now]=0;
return;
}
inline void dfs1(int x,int d){
dep[x]=d,siz[x]=1;
int maxe=-1;
for(int i=las[x];i;i=t[i].nex){
int v=t[i].v;
if(!dep[v]){
fa[v]=x;
dfs1(v,d+1);
siz[x]+=siz[v];
if(siz[v]>maxe)son[x]=v,maxe=siz[v];
}
}
}
inline void dfs2(int x,int topf){
id[x]=++cnt;
w[cnt]=W[x];
top[x]=topf;
if(!son[x])return;
dfs2(son[x],topf);
for(int i=las[x];i;i=t[i].nex){
int v=t[i].v;
if(dep[v]>dep[x]&&v!=son[x])dfs2(v,v);
}
}
inline void add(int u,int v){
t[++len].v=v;
t[len].nex=las[u],las[u]=len;
t[++len].v=u;
t[len].nex=las[v],las[v]=len;
}
inline void build(int now,int l,int r){
if(l==r){gg[now]=w[l];return;}
int mid=(l+r)>>1;
build(now<<1,l,mid),build(now<<1|1,mid+1,r);
gg[now]=gg[now<<1]+gg[now<<1|1];
}
inline void change_point(int now,int l,int r,int x,int e){
down(now,l,r);
if(l==r){gg[now]+=e;return;}
int mid=(l+r)>>1;
if(x<=mid)change_point(now<<1,l,mid,x,e);
else change_point(now<<1|1,mid+1,r,x,e);
gg[now]=gg[now<<1]+gg[now<<1|1];
}
inline void change(int now,int l,int r,int lc,int rc,int e){
down(now,l,r);
if(lc<=l&&r<=rc){update(now,l,r,e);return;}
int mid=(l+r)>>1;
if(lc<=mid)change(now<<1,l,mid,lc,rc,e);
if(rc>mid)change(now<<1|1,mid+1,r,lc,rc,e);
gg[now]=gg[now<<1]+gg[now<<1|1];
}
inline long long find(int now,int l,int r,int lc,int rc){
down(now,l,r);
if(lc<=l&&r<=rc)return gg[now];
int mid=(l+r)>>1;
if(rc<=mid)return find(now<<1,l,mid,lc,rc);
if(lc>mid)return find(now<<1|1,mid+1,r,lc,rc);
return find(now<<1,l,mid,lc,mid)+find(now<<1|1,mid+1,r,mid+1,rc);
}
inline long long find_to(int x,int y){
long long res=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])x^=y^=x^=y;
res+=find(1,1,n,id[top[x]],id[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y])x^=y^=x^=y;
res+=find(1,1,n,id[x],id[y]);
return res;
}
main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;++i)scanf("%lld",&W[i]);
for(int i=1;i<n;++i){
int u,v;
scanf("%lld%lld",&u,&v);
add(u,v);
}
dfs1(1,1);
dfs2(1,1);
build(1,1,n);
int opt,x,a;
while(m--){
scanf("%lld%lld",&opt,&x);
if(opt==1){
scanf("%lld",&a);
change_point(1,1,n,id[x],a);
continue;
}
if(opt==2){
scanf("%lld",&a);
change(1,1,n,id[x],id[x]+siz[x]-1,a);
continue;
}
printf("%lld\n",find_to(1,x));
}
return 0;
}
```
by 引领天下 @ 2019-07-28 17:34:28
记得取模……
by Smile_Cindy @ 2019-07-28 17:40:13
@[JBLee](/space/show?uid=108746) 你们为什么都问这些代码极其复杂（连我自己都敲了2个小时+的题目），问问A+B不好吗。。。
by AK_Automata @ 2019-07-28 17:44:06