【题解】「HAOI2015」树上操作（述链剖分）

本文主要是介绍【题解】「HAOI2015」树上操作（述链剖分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面

【题目描述】
有一棵点数为 $N$ 的树，以点 $1$ 为根，且树点有边权。然后有 $M$ 个操作，分为三种：
操作 $1$ ：把某个节点 $x$ 的点权增加 $a$ 。
操作 $2$ ：把某个节点 $x$ 为根的子树中所有点的点权都增加 $a$ 。
操作 $3$ ：询问某个节点 $x$ 到根的路径中所有点的点权和。
【输入】
第一行包含两个整数 $N, M$ 。表示点数和操作数。接下来一行 $N$ 个整数，表示树中节点的初始权值。接下来 $N - 1$ 行每行两个个正整数 $f r, t o$ ，表示该树中存在一条边 $(f r, t o)$ 。再接下来 $M$ 行，每行分别表示一次操作。其中
第一个数表示该操作的种类 $（ 1 - 3 ）$ ，之后接这个操作的参数 $（ x$ 或者 $x a ）$ 。
【输出】
对于每个询问操作，输出该询问的答案。答案之间用换行隔开。
【样例输入】

【样例输出】

6
9
13

【数据范围】
对于 $100\%$ 的数据， $N,M\leq 100000$ ，且所有输入数据的绝对值都不会超过 $10^6$ 。

算法分析

述链剖分模板题目。
对于修改某个节点 $x$ 为根的子树，在 $D F S$ 序中，子树在连续的相邻的位置，因此只需要知道节点 $x$ 的位置和子树总的节点数目即可。

参考程序

#include<bits/stdc++.h>
#define N 200100 
#define ll long long 
using namespace std;
int head[N],nxt[N],to[N],tot;
ll w[N];
int n,m;
int father[N],deep[N],size[N];//父节点，深度，子树结点数 
int son[N],top[N];//重儿子，所在重路径的顶部结点(深度最小的结点)
int id[N],rev[N],t;//在线段树中的下标(dfs序)，线段树中下标的结点,即rev[id[u]]=u ,dfs序号 
ll sum[2*N],add[2*N]; //线段树 
ll ans_sum;
void Add(int u,int v)
{nxt[++tot]=head[u];to[tot]=v;head[u]=tot;
}
void dfs1(int u,int dad)
{size[u]=1;  //本身结点数为1 father[u]=dad;   deep[u]=deep[dad]+1;for(int i=head[u];i!=-1;i=nxt[i]){int v=to[i];if(v!=dad){dfs1(v,u);size[u]+=size[v];if(size[v]>size[son[u]]) son[u]=v;//找重儿子 }}
}
void dfs2(int u,int dad)
{int v=son[u];if(v)  //优先选择重儿子 {id[v]=++t;//dfs序列 top[v]=top[u];rev[t]=v;dfs2(v,u); }for(int i=head[u];i!=-1;i=nxt[i]){v=to[i];if(!top[v]){id[v]=++t;top[v]=v;        rev[t]=v;dfs2(v,u);}}
}
void built(int k,int l,int r)   //线段树建树
{if(l==r)    {sum[k]=w[rev[l]];return;} int mid=(l+r)/2;built(2*k,l,mid);built(2*k+1,mid+1,r);sum[k]=sum[2*k]+sum[2*k+1];
} 
void pushdown(int k,int l,int r)    //标记下传
{int mid=(l+r)/2;if(add[k]==0) return;add[2*k]+=add[k];sum[2*k]+=(ll)(mid-l+1)*add[k];add[2*k+1]+=add[k];sum[2*k+1]+=(ll)(r-mid)*add[k];add[k]=0;   //下传后标记清零 
}
void modify(int k,int l,int r,int x,int y,ll v)    //区间修改
{if(x>r||y<l) return;if(x<=l&&r<=y){add[k]+=v;sum[k]+=(r-l+1)*v;return;}pushdown(k,l,r); //下传标记int mid=(l+r)/2;if(x<=mid) modify(2*k,l,mid,x,y,v);if(y>=mid+1) modify(2*k+1,mid+1,r,x,y,v);sum[k]=sum[2*k]+sum[2*k+1]; //下传后更新 
}
void query(int k,int l,int r,int x,int y)	//区间询问
{//cout<<l<<" "<<r<<" "<<x<<" "<<y<<endl;if(x>r||y<l) return ;if(x<=l&&r<=y) {ans_sum+=sum[k];					//全部变量ans_sum统计return;}pushdown(k,l,r); //下传标记int mid=(l+r)/2;if(x<=mid) query(2*k,l,mid,x,y);if(y>=mid+1) query(2*k+1,mid+1,r,x,y);
} 
void ask(int u,int v)
{       int fu=top[u],fv=top[v];while(fu!=fv)   //不在同一条重链上  {if(deep[fu]<deep[fv]) {swap(u,v);swap(fu,fv);}   //选择深度大的往上跳query(1,1,n,id[fu],id[u]);  //访问路径 fu->u u=father[fu];fu=top[u]; }if(deep[u]>deep[v]) swap(u,v);   //已经跳到同一条重路径上了 query(1,1,n,id[u],id[v]);   //访问路径 u->v 
}
int main()
{memset(head,-1,sizeof(head));scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%lld",&w[i]);for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);Add(x,y);Add(y,x);}dfs1(1,0);id[1]=++t;  //初始化根节点 top[1]=1;rev[1]=1;dfs2(1,0); built(1,1,n); int q;int x;ll y;for(int i=1;i<=m;i++){scanf("%d",&q);  if(q==1)		//单点修改{scanf("%d%lld",&x,&y);modify(1,1,n,id[x],id[x],y);}if(q==2)		//子树修改{scanf("%d%lld",&x,&y);modify(1,1,n,id[x],id[x]+size[x]-1,y);	}if(q==3)		//路径询问{scanf("%d",&x);ans_sum=0;ask(1,x); //路径处理 printf("%lld\n",ans_sum);}}return 0;
}