BZOJ4034：[HAOI2015]树上操作—

BZOJ4034：[HAOI2015]树上操作——题解

阅读量：6619 次

发布时间：2019-06-25

本文共 1981 字，大约阅读时间需要 6 分钟。

有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个

操作，分为三种：

操作 1 ：把某个节点 x 的点权增加 a 。

操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。

操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。

树剖板子。不会写树链剖分的请看：

试图默写结果被1和l搞反然后gg。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long ll;const int N=1e5+5;inline int read(){    int X=0,w=0;char ch=0;    while(ch<'0'||ch>'9'){w|=ch=='-';ch=getchar();}    while(ch>='0'&&ch<='9')X=(X<<3)+(X<<1)+(ch^48),ch=getchar();    return w?-X:X;}struct node{    int to,nxt;}edge[2*N];int head[N],cnt,tot,n,q;inline void add(int u,int v){    edge[++cnt].to=v;edge[cnt].nxt=head[u];head[u]=cnt;}int fa[N],son[N],size[N],val[N],dep[N],idx[N],pos[N],top[N];ll sum[4*N],lazy[4*N];void dfs1(int u){    size[u]=1;    for(int i=head[u];i;i=edge[i].nxt){    int v=edge[i].to;    if(v==fa[u])continue;    fa[v]=u;dep[v]=dep[u]+1;    dfs1(v);    size[u]+=size[v];    if(!son[u]||size[son[u]]
          
           >1; if(lazy[a]){ lazy[a*2]+=lazy[a]; lazy[a*2+1]+=lazy[a]; sum[a*2]+=(mid-l+1)*lazy[a]; sum[a*2+1]+=(r-mid)*lazy[a]; lazy[a]=0; }}void build(int a,int l,int r){ if(l==r){ sum[a]=val[idx[l]]; return; } int mid=(l+r)>>1; build(a*2,l,mid); build(a*2+1,mid+1,r); sum[a]=sum[a*2]+sum[a*2+1];}ll query(int a,int l,int r,int l1,int r1){ if(r1
           
            
             >1; push(a,l,r); return query(a*2,l,mid,l1,r1)+query(a*2+1,mid+1,r,l1,r1);}ll pathquery(int x,int y){ ll res=0; while(top[x]!=top[y]){ if(dep[top[x]]
             
              dep[y])swap(x,y); res+=query(1,1,n,pos[x],pos[y]); return res;}void modify(int a,int l,int r,int l1,int r1,ll p){ if(r1
              
               
                >1; push(a,l,r); modify(a*2,l,mid,l1,r1,p); modify(a*2+1,mid+1,r,l1,r1,p); sum[a]=sum[a*2]+sum[a*2+1];}int main(){ n=read(),q=read(); for(int i=1;i<=n;i++)val[i]=read(); for(int i=1;i