UOJ Logo zgjkt的博客

博客

【bzoj4034】T2

2015-10-03 22:29:34 By zgjkt

题目大意

有一棵点数为$n$的树,对于这棵树有$m$个操作,分为三种:

  1. 把节点$x$的点权增加$a$

  2. 把节点$x$为根的子树中所有点的点权都增加$a$

  3. 询问节点$x$到根的路径中所有点的点权和

数据范围

$n,m\leqslant 100000$,且所有输入数据的绝对值都不会超过$10^6$


题解

树链剖分的基础题,连$求lca$都不需要

关于第二个操作要在第二遍搜索中找到每个子树中在数据结构的位置编号最大的一个节点,并将位置编号记录在根节点上,再根据根节点的位置编号是其子树最小的,就可以直接执行区间修改的操作了


程序

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next) 
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;

struct edge{int to,next;}e[200050];
struct tree{ll tag,sum;}t[400050]; 
int last[100050],pos[100050];
int top[100050],size[100050],f[100050],v[100050],rpos[100050]; 
int n,m,et,cnt;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
    return x*f; 
}
inline void addedge(int u,int v){
    e[++et]=(edge){v,last[u]};last[u]=et;
    e[++et]=(edge){u,last[v]};last[v]=et;
}
inline void pushdown(int p,int wl,int wr){
    if (wl==wr) return;
    int mid=(wl+wr)>>1;
    t[p<<1].tag+=t[p].tag;t[p<<1|1].tag+=t[p].tag;
    t[p<<1].sum+=t[p].tag*(mid-wl+1);t[p<<1|1].sum+=t[p].tag*(wr-mid);
    t[p].tag=0;
}

void dfs(int x){
    size[x]=1;
    goedge(i,x)
        if (e[i].to!=f[x]){
            f[e[i].to]=x;
            dfs(e[i].to);
            size[x]+=size[e[i].to]; 
        }
}
void gochain(int x,int chain){
    top[x]=chain;pos[x]=rpos[x]=++cnt;
    int k=0;
    goedge(i,x)
        if (e[i].to!=f[x]&&size[e[i].to]>size[k]) k=e[i].to;
    if (k){gochain(k,chain);rpos[x]=max(rpos[x],rpos[k]);}
    goedge(i,x)
        if (e[i].to!=f[x]&&e[i].to!=k){
            gochain(e[i].to,e[i].to);
            rpos[x]=max(rpos[x],rpos[e[i].to]);
        }
}
void add(int p,int wl,int wr,int l,int r,ll c){
    if (t[p].tag) pushdown(p,wl,wr);
    if (wl==l&&wr==r){t[p].tag+=c;t[p].sum+=(wr-wl+1)*c;return;}
    int mid=(wl+wr)>>1;
    if (l<=mid) add(p<<1,wl,mid,l,min(mid,r),c);
    if (r>=mid+1) add(p<<1|1,mid+1,wr,max(mid+1,l),r,c);
    t[p].sum=t[p<<1].sum+t[p<<1|1].sum; 
}
ll query(int p,int wl,int wr,int l,int r){
    if (t[p].tag) pushdown(p,wl,wr);
    if (wl==l&&wr==r) return t[p].sum;
    int mid=(wl+wr)>>1;ll ans=0;
    if (l<=mid) ans+=query(p<<1,wl,mid,l,min(mid,r));
    if (r>=mid+1) ans+=query(p<<1|1,mid+1,wr,max(mid+1,l),r);
    return ans;
}
ll qsum(int x){
    ll ans=0;
    while (top[x]!=1){
        ans+=query(1,1,n,pos[top[x]],pos[x]);
        x=f[top[x]];
    }
    ans+=query(1,1,n,1,pos[x]);
    return ans; 
}
int main(){
    n=read();m=read();
    For(i,1,n) v[i]=read();
    For(i,1,n-1){int u=read(),v=read();addedge(u,v);}
    dfs(1);gochain(1,1); 
    For(i,1,n) add(1,1,n,pos[i],pos[i],v[i]); 
    For(i,1,m){
        int a=read(),b=read();
        if (a==1){int c=read();add(1,1,n,pos[b],pos[b],c);}
        if (a==2){int c=read();add(1,1,n,pos[b],rpos[b],c);}
        if (a==3) printf("%lld\n",qsum(b));
    }
    return 0;
}

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。