```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[100010],eid=1,head[200010],id[100010],vis[100010],rev[100010],op,x,A,Size[100010],son[100010],fa[100010],top[100010],tot,lazy[800010];
vector<pair<int,int>> G[100010];
struct node
{
int v,next;
}e[200010];
struct edge
{
int sum,l,r;
}C[800010];
inline void insert(int u,int v)
{
e[eid].v=v;
e[eid].next=head[u];
head[u]=eid++;
}
inline void dfs(int u,int father)
{
Size[u]=1;
fa[u]=father;
int maxn=0;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==father)
{
continue;
}
dfs(v,u);
Size[u]+=Size[v];
if(Size[v]>maxn)
{
maxn=Size[v];
son[u]=v;
}
G[u].push_back({-Size[v],v});
}
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
G[v].push_back({-Size[u],u});
}
sort(G[u].begin(),G[u].end());
}
inline void dfs1(int u,int father)
{
if(vis[u])return;
vis[u]=1;
if(u==son[fa[u]])//该点是他爸的重儿子
{
top[u]=top[fa[u]];
}
else
{
top[u]=u;
}
rev[++tot]=u;
id[u]=tot;
//cout<<u<<" "<<tot<<"\n";
for(auto now:G[u])
{
int v=now.second;
if(v==father)
{
continue;
}
//cout<<v<<" "<<u<<"\n";
dfs1(v,u);
}
}
inline void pushdown(int id)
{
if(lazy[id])
{
lazy[id<<1]+=lazy[id];
lazy[id<<1|1]+=lazy[id];
int mid=C[id].l+C[id].r>>1,l=C[id].l,r=C[id].r;
C[id<<1].sum+=lazy[id]*(mid-l+1);
C[id<<1|1].sum+=lazy[id]*(r-mid);
lazy[id]=0;
}
}
inline void build(int id,int l,int r)
{
C[id].l=l;
C[id].r=r;
if(l==r)
{
C[id].sum=a[rev[l]];
return;
}
int mid=l+r>>1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
C[id].sum=C[id<<1].sum+C[id<<1|1].sum;
}
inline void update(int id,int l,int r,int v)
{
//cout<<C[id].l<<" "<<C[id].r<<"\n";
if(l<=C[id].l&&C[id].r<=r)
{
C[id].sum+=v*(C[id].r-C[id].l+1);
lazy[id]+=v;
return;
}
pushdown(id);
int mid=C[id].l+C[id].r>>1;
if(l<=mid)
{
update(id<<1,l,r,v);
}
if(mid<r)
{
update(id<<1|1,l,r,v);
}
C[id].sum=C[id<<1].sum+C[id<<1|1].sum;
}
inline int Query(int id,int x,int y)
{
if(x<=C[id].l&&C[id].r<=y)
{
return C[id].sum;
}
pushdown(id);
int mid=C[id].l+C[id].r>>1,ans=0;
if(x<=mid)
{
ans+=Query(id<<1,x,y);
}
if(y>mid)
{
ans+=Query(id<<1|1,x,y);
}
return ans;
}
inline int query(int x)
{
int res=0,pre=x,y=top[x];
res=Query(1,id[x],id[y]);
//cout<<"q:"<<x<<" "<<y<<" "<<id[x]<<" "<<id[y]<<"\n";
pre=fa[y];
while(pre)
{
res+=Query(1,id[top[pre]],id[pre]);
//cout<<"q:"<<pre<<" "<<top[pre]<<" "<<id[pre]<<" "<<id[top[pre]]<<"\n";
pre=fa[top[pre]];
}
return res;
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
insert(u,v);
insert(v,u);
}
dfs(1,0);
/*for(int i=1;i<=n;i++){
for(auto v:G[i])
{
cout<<v.second<<" ";
}
puts("");
}*/
dfs1(1,0);
build(1,1,n);
while(m--)
{
cin>>op>>x;
if(op==1)
{
cin>>A;
//cout<<id[x]<<" "<<A<<'\n';
update(1,id[x],id[x],A);
}
if(op==2)
{
cin>>A;
update(1,id[x],id[x]+Size[x]-1,A);
}
if(op==3)
{
cout<<query(x)<<"\n";
}
}
}
```
改了一下，还是不对
by expnoi @ 2022-07-19 20:59:15
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[100010],eid=1,head[200010],id[100010],vis[100010],rev[100010],op,x,A,Size[100010],son[100010],fa[100010],top[100010],tot,lazy[800010];
vector<pair<int,int>> G[100010];
struct node
{
int v,next;
}e[200010];
struct edge
{
int sum,l,r;
}C[800010];
inline void insert(int u,int v)
{
e[eid].v=v;
e[eid].next=head[u];
head[u]=eid++;
}
inline void dfs(int u,int father)
{
Size[u]=1;
fa[u]=father;
int maxn=0;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==father)
{
continue;
}
dfs(v,u);
Size[u]+=Size[v];
if(Size[v]>maxn)
{
maxn=Size[v];
son[u]=v;
}
G[u].push_back({-Size[v],v});
}
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
G[v].push_back({-Size[u],u});
}
sort(G[u].begin(),G[u].end());
}
inline void dfs1(int u,int father)
{
if(vis[u])return;
vis[u]=1;
if(u==son[fa[u]])//该点是他爸的重儿子
{
top[u]=top[fa[u]];
}
else
{
top[u]=u;
}
rev[++tot]=u;
id[u]=tot;
//cout<<u<<" "<<tot<<"\n";
for(auto now:G[u])
{
int v=now.second;
if(v==father)
{
continue;
}
//cout<<v<<" "<<u<<"\n";
dfs1(v,u);
}
}
inline void pushdown(int id)
{
if(lazy[id])
{
lazy[id<<1]+=lazy[id];
lazy[id<<1|1]+=lazy[id];
int mid=C[id].l+C[id].r>>1,l=C[id].l,r=C[id].r;
C[id<<1].sum+=lazy[id]*(mid-l+1);
C[id<<1|1].sum+=lazy[id]*(r-mid);
lazy[id]=0;
}
}
inline void build(int id,int l,int r)
{
C[id].l=l;
C[id].r=r;
if(l==r)
{
C[id].sum=a[rev[l]];
return;
}
int mid=l+r>>1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
C[id].sum=C[id<<1].sum+C[id<<1|1].sum;
}
inline void update(int id,int l,int r,int v)
{
//cout<<C[id].l<<" "<<C[id].r<<"\n";
if(l<=C[id].l&&C[id].r<=r)
{
C[id].sum+=v*(C[id].r-C[id].l+1);
lazy[id]+=v;
return;
}
pushdown(id);
int mid=C[id].l+C[id].r>>1;
if(l<=mid)
{
update(id<<1,l,r,v);
}
if(mid<r)
{
update(id<<1|1,l,r,v);
}
C[id].sum=C[id<<1].sum+C[id<<1|1].sum;
}
inline int Query(int id,int x,int y)
{
if(x<=C[id].l&&C[id].r<=y)
{
return C[id].sum;
}
pushdown(id);
int mid=C[id].l+C[id].r>>1,ans=0;
if(x<=mid)
{
ans+=Query(id<<1,x,y);
}
if(y>mid)
{
ans+=Query(id<<1|1,x,y);
}
return ans;
}
inline int query(int x)
{
int res=0,pre=x,y=top[x];
res=Query(1,id[y],id[x]);
//cout<<"q:"<<x<<" "<<y<<" "<<id[x]<<" "<<id[y]<<"\n";
pre=fa[y];
while(pre)
{
res+=Query(1,id[top[pre]],id[pre]);
//cout<<"q:"<<top[pre]<<" "<<pre<<" "<<id[top[pre]]<<" "<<id[pre]<<"\n";
pre=fa[top[pre]];
}
return res;
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
insert(u,v);
insert(v,u);
}
dfs(1,0);
/*for(int i=1;i<=n;i++){
for(auto v:G[i])
{
cout<<v.second<<" ";
}
puts("");
}*/
dfs1(1,0);
build(1,1,n);
while(m--)
{
cin>>op>>x;
if(op==1)
{
cin>>A;
//cout<<id[x]<<" "<<A<<'\n';
update(1,id[x],id[x],A);
}
if(op==2)
{
cin>>A;
update(1,id[x],id[x]+Size[x]-1,A);
}
if(op==3)
{
cout<<query(x)<<"\n";
}
}
}
```
又改了下，还是不对/kk
by expnoi @ 2022-07-19 21:00:58