Lvat_s Blog

树链剖分入门题

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
const int N=100005;
 
int n,m,dep[N],fa[N],son[N],siz[N],en,h[N],pre[N],segn,id[N],top[N];
long long a[N];
 
struct Edge{
int b,next;
}e[N<<1];
 
void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}
 
struct SegTree{
int l,r;
long long sum,tag;
}tree[N<<2];
 
void Pushdown(int rt){
if(tree[rt].tag){
    tree[rt<<1].tag+=tree[rt].tag;
    tree[rt<<1|1].tag+=tree[rt].tag;
    tree[rt<<1].sum+=tree[rt].tag*(tree[rt<<1].r-tree[rt<<1].l+1ll);
    tree[rt<<1|1].sum+=tree[rt].tag*(tree[rt<<1|1].r-tree[rt<<1|1].l+1ll);
    tree[rt].tag=0;
}
}
 
void Pushup(int rt){
tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
}
 
void Build(int rt,int l,int r){
tree[rt].l=l;tree[rt].r=r;
if(l==r){tree[rt].sum=a[pre[l]];return;}
int mid=l+r>>1;
Build(rt<<1,l,mid);Build(rt<<1|1,mid+1,r);
Pushup(rt);
}
 
void Add(int rt,int l,int r,long long val){
if(l<=tree[rt].l && tree[rt].r<=r){tree[rt].sum+=val*(tree[rt].r-tree[rt].l+1);tree[rt].tag+=val;return;}
int mid=tree[rt].l+tree[rt].r>>1;
Pushdown(rt);
if(l<=mid)Add(rt<<1,l,r,val);
if(r>mid)Add(rt<<1|1,l,r,val);
Pushup(rt);
}
 
long long Sum(int rt,int l,int r){
if(l<=tree[rt].l && tree[rt].r<=r)return tree[rt].sum;
int mid=tree[rt].l+tree[rt].r>>1;
long long ans=0;
Pushdown(rt);
if(l<=mid)ans+=Sum(rt<<1,l,r);
if(r>mid)ans+=Sum(rt<<1|1,l,r);
return ans;
}
 
void dfs1(int u,int Fa){
dep[u]=dep[Fa]+1;
fa[u]=Fa;
siz[u]=1;
son[u]=0;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==Fa)continue;
    dfs1(v,u);
    siz[u]+=siz[v];
    if(siz[son[u]]<siz[v])son[u]=v;
}
}
 
void dfs2(int u,int ux){
top[u]=ux;
id[u]=++segn;
pre[segn]=u;
if(!son[u])return;
dfs2(son[u],ux);
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=fa[u] && v!=son[u])dfs2(v,v);
}
}
 
long long Ask(int u){
int Tp=top[u];
long long ans=0;
while(Tp!=top[1]){
    ans+=Sum(1,id[Tp],id[u]);
    u=fa[Tp];
    Tp=top[u];
}
return ans+Sum(1,id[Tp],id[u]);
}
 
int main(){
freopen("4034.in","r",stdin);
freopen("4034.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<n;i++){
    int u,v;
    scanf("%d %d",&u,&v);
    AddEdge(u,v);AddEdge(v,u);
}
dfs1(1,1);
dfs2(1,1);
Build(1,1,n);
while(m--){
    int opt,u;
    long long val;
    scanf("%d %d",&opt,&u);
    if(opt==1){scanf("%lld",&val);Add(1,id[u],id[u],val);}
    if(opt==2){scanf("%lld",&val);Add(1,id[u],id[u]+siz[u]-1,val);}
    if(opt==3)printf("%lld\n",Ask(u));
}
return 0;
}