问题描述:
已知一棵包含 n 个节点的树（连通且无环），每个节点上包含一个数值，有以下 4 种操作
1 x y z 修改操作 1；将树从 x 到 y 节点最短路径上所有节点的值都加 z
2 x y 查询操作 2；求树从 x 到 y 节点最短路径上所有节点值之和
3 x z 修改操作 3；将以 x 为根节点的子树内所有节点值都加 z
4 x 查询操作 4；求以 x 为根节点的子树内所有节点值之和
| 输入： 第 1 行输入 4 个正整数 n、m、r、p,分别表示树的节点个数、操作个数、根节点序号、取模数（即所有的输出结果均对此取模） 第 2 行输入 n 个非负整数，表示各节点上初始的数值。 接下来 n – 1 行中，每行输入两个整数 x 和 y，表示点 x 和点 y 之间连有一条边（保证无环且连通） 接下来 m 行中，每行输入若干个正整数，每行表示一个操作 |
| 输出：输出若干行，表示每个操作 2 或操作 4 所得的结果（对 p 取模） |
| 数据范围：1 ≤ n ≤ 105，1 ≤ m ≤ 105，1 ≤ r ≤ n，1 ≤ p ≤ 231 – 1 |
| 输入样例 | 输出样例 |
| 5 5 2 24 7 3 7 8 0 1 2 1 5 3 1 4 1 3 4 2 3 2 2 4 5 1 5 1 3 2 1 3 | 2 21 |
轻重链剖分
#include<bits/stdc++.h>
using namespace std;
const int N=100000+10;
int n,m,r,mod;
//以下是链式前向星
struct Edge{int to, next;}edge[2*N];
int head[2*N], cnt;
void init(){ //链式前向星：初始化
for(int i=0;i<2*N;++i){ edge[i].next = -1; head[i] = -1; }
cnt = 0;
}
void addedge(int u,int v){ //链式前向星：加边
edge[cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt++;
} //以上是链式前向星
//以下是线段树
int ls(int x){ return x<<1; } //定位左儿子：x*2
int rs(int x){ return x<<1|1;} //定位右儿子：x*2 + 1
int w[N],w_new[N]; //w[]、w_new[]初始点权
int tree[N<<2], tag[N<<2]; //线段树数组、lazy-tag操作
void addtag(int p,int pl,int pr,int d){ //给结点p打tag标记，并更新tree
tag[p] += d; //打上tag标记
tree[p] += d*(pr-pl+1); tree[p] %= mod; //计算新的tree
}
void push_up(int p){ //上传标记函数：从下往上传递区间值
tree[p] = tree[ls(p)] + tree[rs(p)]; tree[p] %= mod;
}
void push_down(int p,int pl, int pr){ //下传标记函数
if(tag[p]){ //有标记就像下传
int mid = (pl+pr)>>1;
addtag(ls(p),pl,mid,tag[p]); //把tag标记传给左子树
addtag(rs(p),mid+1,pr,tag[p]); //把tag标记传给右子树
tag[p] = 0;
}
}
void build(int p,int pl,int pr){ //建线段树：w_new
tag[p] = 0;
if(pl==pr){
tree[p] = w_new[pl]; tree[p] %= mod;
return;
}
int mid = (pl+pr) >> 1;
build(ls(p),pl,mid);
build(rs(p),mid+1,pr);
push_up(p);
}
void update(int L,int R,int p,int pl,int pr,int d){ //更新线段函数
if(L<=pl && pr<=R){ addtag(p, pl, pr,d); return; } //在范围区间就标记上
push_down(p,pl,pr);
int mid = (pl+pr) >> 1;
if(L<=mid) update(L,R,ls(p),pl,mid,d);
if(R> mid) update(L,R,rs(p),mid+1,pr,d);
push_up(p);
}
int query(int L,int R,int p,int pl,int pr){ //查询线段函数
if(pl>=L && R >= pr) return tree[p] %= mod;
push_down(p,pl,pr);
int res =0;
int mid = (pl+pr) >> 1;
if(L<=mid) res += query(L,R,ls(p),pl,mid);
if(R> mid) res += query(L,R,rs(p),mid+1,pr);
return res;
}
//以下是树链剖分
int son[N],id[N],fa[N],deep[N],siz[N],top[N]; //非叶子结点的重儿子、时间戳对每个节点记录上编号、父节点、链头、子树大小、深度
void dfs1(int x, int father){ //求出son[N],fa[N],deep[N],siz[N],top[N]数组
deep[x]=deep[father]+1; //深度：比父结点深度多1
fa[x]=father; //标记x的父亲
siz[x]=1; //标记每个结点的子树大小（包括自己）
for(int i=head[x];~i;i=edge[i].next){ //遍历树
int y=edge[i].to;
if(y!=father){ //邻居：除了父亲，都是孩子
fa[y]=x;
dfs1(y,x);
siz[x] += siz[y]; //回溯后，把x的儿子数加到x身上
if(!son[x] || siz[son[x]]<siz[y]) //标记每个非叶子结点的重儿子
son[x]=y; //x的重儿子是y
}
}
}
int num = 0;
void dfs2(int x,int topx){ //x当前结点，topx当前链的最顶端的结点
id[x] = ++num; //对每个结点新编号
w_new[num] = w[x]; //把每个点的初始值赋给新编号
top[x]=topx; //记录x的链头
if(!son[x]) return; //x是叶子，没有儿子，返回
dfs2(son[x],topx); //先dfs重儿子
for(int i=head[x];~i;i=edge[i].next){ //再dfs轻儿子
int y=edge[i].to;
if(y!=fa[x] && y!=son[x]) dfs2(y,y); //每个轻儿子都有一条从它自己开始的链
}
}
void update_range(int x,int y,int z){ //和求LCA(x, y)的过程差不多
while(top[x]!=top[y]){ //非同链
if(deep[top[x]]<deep[top[y]]) swap(x,y); //让x是链头更深的重链
update(id[top[x]],id[x],1,1,n,z); //修改一条重链的内部
x = fa[top[x]]; //x穿过轻边，跳到上一条重链
}
if(deep[x]>deep[y]) swap(x,y);
update(id[x],id[y],1,1,n,z); //修改一条重链的内部
}
int query_range(int x,int y){ //和求LCA(x,y)的过程差不多
int ans=0;
while(top[x]!=top[y]){ //持续往上跳，直到若x和y属于同一条重链
if(deep[top[x]]<deep[top[y]]) swap(x,y); //让x是链头更深的重链
ans += query(id[top[x]],id[x],1,1,n); //加上x到x的链头这一段区间
ans %= mod;
x = fa[top[x]]; //x穿过轻边，跳到上一条重链
}
if(deep[x]>deep[y]) swap(x,y);
//若LCA(x, y) = y，交换x,y,让x更浅，使得id[x] <= id[y]
ans += query(id[x],id[y],1,1,n); //再加上x, y的区间和
return ans % mod;
}
void update_tree(int x,int k){ update(id[x],id[x]+siz[x]-1,1,1,n,k); } //按照DFS的方式标记的x树根节点加上子树大小用update()函数更新
int query_tree(int x){ return query(id[x],id[x]+siz[x]-1,1,1,n) % mod; } //同上用query()更新
int main(){
init(); //链式前向星初始化
scanf("%d%d%d%d",&n,&m,&r,&mod); //结点个数、操作个数、根节点序号和取模数
for(int i=1;i<=n;i++) scanf("%d",&w[i]); //各个节点上初始的数值
for(int i=1;i<n;i++){ //画树
int u,v; scanf("%d%d",&u,&v);
addedge(u,v); addedge(v,u);
}
dfs1(r,0);
dfs2(r,r); //记录链头和记录节点id
build(1,1,n); //建线段树
while(m--){
int k,x,y,z; scanf("%d",&k); //操作序号
switch(k){
case 1:scanf("%d%d%d",&x,&y,&z);update_range(x,y,z); break;
case 2:scanf("%d%d",&x,&y); printf("%d\n",query_range(x,y));break;
case 3: scanf("%d%d",&x,&y); update_tree(x,y); break;
case 4: scanf("%d",&x); printf("%d\n",query_tree(x)); break;
}
}
}
笔记：id[]是时间戳对每个节点记录上编号，当进行树下操作时可以配合siz[]进行修改或查询。重链内部使用线段树标记上，若路径跨过多个路径就跳过重链之间的轻边