qndmx
by 5ab_juruo @ 2020-08-26 10:37:41
没人吗（哭
by 火羽白日生 @ 2020-08-26 10:44:10
dfs2 少了对重儿子的 dfs
by wxwoo @ 2020-08-26 10:47:09
@[wxwoo](/user/116659) 改了后全WA可还行
by 火羽白日生 @ 2020-08-26 10:51:52
qndmx
by Vigna @ 2020-08-26 10:56:18
qndmx
by Error_Eric @ 2020-08-26 10:59:44
```cpp
printf("lld\n",qRange(1,x));
```
？
by wxwoo @ 2020-08-26 11:01:41
@[wxwoo](/user/116659) 这个改了的
by 火羽白日生 @ 2020-08-26 11:13:12
全WA
```
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <stdlib.h>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
//#pragma GCC optimize(2) //吸氧
//#pragma GCC optimize(3,"Ofast","inline") //吸臭氧
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
inline ll read(){
char ch=getchar();
ll x=0,w=1;
while(ch<'0'||ch>'9'){
if(ch=='-')
w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*w;
}
ll n,m;
ll id=0,cnt=0,head[1000005];
ll a[1000005],sum[4000005],tag[4000005];
ll f[1000005],size[1000005],son[1000005],top[1000005],val[1000005],dep[1000005],num[1000005];
struct node{
ll v,next;
}edge[2000005];
void add(ll u,ll v){
edge[++id].v=v;
edge[id].next=head[u];
head[u]=id;
}
inline ll ls(ll p){
return p<<1;
}
inline ll rs(ll p){
return p<<1|1;
}
void pushup(ll p){
sum[p]=sum[ls(p)]+sum[rs(p)];
}
void build(ll p,ll l,ll r){
tag[p]=0;
if(l==r){
sum[p]=a[l];
return;
}
ll mid=(l+r)>>1;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
pushup(p);
}
void fun(ll p,ll l,ll r,ll k){
tag[p]+=k;
sum[p]+=k*(r-l+1);
}
void pushdown(ll p,ll l,ll r){
if(tag[p]){
ll mid=(l+r)>>1;
fun(ls(p),l,mid,tag[p]);
fun(rs(p),mid+1,r,tag[p]);
tag[p]=0;
}
}
void update(ll tl,ll tr,ll p,ll l,ll r,ll k){
if(tl<=l && r<=tr){
fun(p,l,r,k);
return;
}
pushdown(p,l,r);
ll mid=(l+r)>>1;
if(tl<=mid)
update(tl,tr,ls(p),l,mid,k);
if(tr>mid)
update(tl,tr,rs(p),mid+1,r,k);
pushup(p);
}
ll query(ll tl,ll tr,ll p,ll l,ll r){
ll res=0;
if(tl<=l && r<=tr)
return sum[p];
pushdown(p,l,r);
ll mid=(l+r)>>1;
if(tl<=mid)
res+=query(tl,tr,ls(p),l,mid);
if(tr>mid)
res+=query(tl,tr,rs(p),mid+1,r);
return res;
}
void dfs1(ll u,ll fa){
dep[u]=dep[fa]+1;
f[u]=fa;
size[u]=1;
for(ll i=head[u];i;i=edge[i].next){
ll v=edge[i].v;
if(v==fa)
continue;
dfs1(v,u);
size[u]+=size[v];
if(size[v]>size[son[u]])
son[u]=v;
}
}
void dfs2(ll u,ll topf){
top[u]=topf;
num[u]=++cnt;
a[cnt]=val[u];
if(!son[u])
return;
dfs2(son[u],topf);
for(ll i=head[u];i;i=edge[i].next){
ll v=edge[i].v;
if(v==f[u] || v==son[u])
continue;
dfs2(v,v);
}
}
void upSon(ll x,ll w){
update(num[x],num[x]+size[x]-1,1,1,n,w);
}
ll qRange(ll x,ll y){
ll res=0;
if(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])
swap(x,y);
res+=query(num[top[x]],num[x],1,1,n);
x=f[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
res+=query(num[x],num[y],1,1,n);
return res;
}
int main(int argc, const char * argv[]) {
n=read();m=read();
for(ll i=1;i<=n;i++)
val[i]=read();
for(ll i=1;i<=n-1;i++){
ll x=read(),y=read();
add(x,y);
add(y,x);
}
dep[0]=0;
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
for(ll i=1;i<=m;i++){
ll op=read(),x,y;
if(op==1){
x=read();y=read();
update(num[x],num[x],1,1,n,y);
}
if(op==2){
x=read();y=read();
upSon(x,y);
}
if(op==3){
x=read();
printf("%lld\n",qRange(1,x));
}
}
return 0;
}
```
by 火羽白日生 @ 2020-08-26 11:20:00
~~树剖很毒瘤的~~
by Acfboy @ 2020-08-26 11:33:48