[HAOI2015]树上操作
首先先说一下基本概念：
1.重儿子：一个结点的所有儿子中，大小最大的那个（最重的，所以说只有一个，如果有多个儿子的大小相等那就随便取一个）。
2.轻儿子：一个结点的儿子除了重儿子以外的所有儿子都是轻儿子。（根节点为轻儿子）
3.重链：从一个轻儿子开始，一路往重儿子走，连出来的链叫重链。
4.轻链：除了重链全是轻链。
如下图：
重链即为标染色点连出的边。
dfs序即为即为图中红色标号。
那么我们如何处理出这个dfs序呢？
通过两个dfs.
第一个dfs需要：
1.标记结点的父亲
2.标记结点的重儿子
3.标记结点的深度
4.结点的大小
第二个dfs需要：
为什么要第二遍才可以（因为需要第一遍跑出来的重儿子）
1.标记重链的开始结点。
2.结点权值的dfs序与时间戳。
如下图有两条重链：
第一条重链为FHKL 他们的开始结点都为F
第二条重链为CD 他们的开始结点都为C
这个标记有什么用处，到后面就明白了。
我们再来看轻重链剖分的基本操作：
对于操作一和操作二，我们可以知道，树上点与点之间的路径是唯一的（不重复走的情况下）。
所以我们可以得知：
引理：除根节点外的任何一个结点的父亲结点都一定在一条重链上。
证明：因为父亲结点存在儿子，所以一定存在重儿子，所以一定在一条重链上。
所以：
对于x-y之间的路径：是由重链的一部分和叶子节点组成的。
那么我们对于不同的路径情况分类讨论一下即可。
1.假设x、y在一条重链上，那么情况就变得简单了（因为重链上的序号是连续的）。
我们直接把x和y对应的dfs序拿出来在线段树上操作一下即可。
那么问题是如何判断x、y是否在一条重链上呢？
标记重链的开始结点。 这一个操作用上了，只要查询他们两个值的开始结点相同，那么即为同一重链。
2.如果不在一条重链上呢？
那么我们可以维护两个指针分别指向两个结点。
不停的让所在链的顶部结点深度较深那个指针沿着重链往上跳（直接跳到重链开始结点），顺便在线段树上维护操作（因为重链上的结点是连续的）。
到达顶部结点后，我们让他跳到顶部结点的父亲结点。然后继续循环如上操作，直到两指针相遇（或者到了同一条重链上）。
那么对于本题来说，
操作一的话直接按照dfs的顺序在线段树上给他+a即可
操作二即为上面介绍的操作三
操作三即为1-x结点路径求和即可。
代码：
/*Keep on going Never give up*/
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int maxn=4e6+10;
//int mod=998244353;
struct node{
int to,next;
}edge[maxn];
int tot,head[maxn];
void init(){
memset(head,-1,sizeof head);
}
void adde(int u,int v){
edge[tot].to=v,edge[tot].next=head[u];
head[u]=tot++;
edge[tot].to=u,edge[tot].next=head[v];
head[v]=tot++;
}
int v[maxn];
int fa[maxn],dep[maxn],siz[maxn],son[maxn];
void dfs1(int u,int f){
fa[u]=f;
dep[u]=dep[f]+1;
siz[u]=1;
for(int i=head[u];~i;i=edge[i].next){
int v=edge[i].to;
if(v==f) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]){
son[u]=v;
}
}
}
int cnt,dfn[maxn],top[maxn],w[maxn];
void dfs2(int u,int t){
dfn[u]=++cnt;
top[u]=t;
w[cnt]=v[u];
if(!son[u]) return ;
dfs2(son[u],t);
for(int i=head[u];~i;i=edge[i].next){
int v=edge[i].to;
if(v==fa[u]||v==son[u]) continue ;
dfs2(v,v);
}
}
int tree[maxn],lazy[maxn];
void push_down(int node,int l,int r){
lazy[node*2]+=lazy[node];
lazy[node*2+1]+=lazy[node];
int mid=(l+r)/2;
tree[node*2]+=(mid-l+1)*lazy[node];
tree[node*2+1]+=(r-mid)*lazy[node];
lazy[node]=0;
}
void build(int node,int start,int ends){
if(start==ends){
tree[node]=w[start];
return ;
}
int mid=(start+ends)/2;
build(node*2,start,mid);
build(node*2+1,mid+1,ends);
tree[node]=(tree[node*2]+tree[node*2+1]);
}
void update(int node,int start,int ends,int l,int r,int val){
if(start>=l&&ends<=r){
lazy[node]+=val;
tree[node]+=(ends-start+1)*val;
return ;
}
if(lazy[node]) push_down(node,start,ends);
int mid=(start+ends)/2;
if(l<=mid) update(node*2,start,mid,l,r,val);
if(mid<r) update(node*2+1,mid+1,ends,l,r,val);
tree[node]=(tree[node*2]+tree[node*2+1]);
}
int query(int node,int start,int ends,int l,int r){
if(start>=l&&ends<=r){
return tree[node];
}
if(lazy[node]) push_down(node,start,ends);
int mid=(start+ends)/2;
int res=0;
if(l<=mid) res+=query(node*2,start,mid,l,r);
if(mid<r) res+=query(node*2+1,mid+1,ends,l,r);
return res;
}
int n,m,r;
//void mchain(int x,int y,int z){
// //z%=mod;
// while(top[x]!=top[y]){
// if(dep[top[x]]<dep[top[y]]) swap(x,y);
// update(1,1,n,dfn[top[x]],dfn[x],z);
// x=fa[top[x]];
// }
// if(dep[x]>dep[y]) swap(x,y);
// update(1,1,n,dfn[x],dfn[y],z);
//}
int qchain(int x,int y){
int ret=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ret+=query(1,1,n,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ret+=query(1,1,n,dfn[x],dfn[y]);
return ret;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>v[i];
}
for(int i=1;i<=n-1;i++){
int x,y;
cin>>x>>y;
adde(x,y);
}
dfs1(1,0);
dfs2(1,0);
build(1,1,n);
for(int i=0;i<m;i++){
int opt;
cin>>opt;
if(opt==1){
int x,y;
cin>>x>>y;
update(1,1,n,dfn[x],dfn[x],y);
}
else if(opt==2){
int x,y;
cin>>x>>y;
//mchain(1,x,z);
update(1,1,n,dfn[x],dfn[x]+siz[x]-1,y);
}
else{
int x;
cin>>x;
int ans=qchain(1,x);
cout<<ans<<endl;
}
}
}
主要写一些题目的题解
