树链剖分
概念
重儿子:子树中结点数目最多的结点
轻儿子:父亲节点中除了重结点以外的结点
重边:父亲结点和重结点连成的边
轻边:父亲节点和轻节点连成的边
重链:由多条重边连接而成的路径
轻链:由多条轻边连接而成的路径
上图解释:(图片来自:HT008)
1的重儿子为4,4的重儿子为5,5的重儿子为6.
2的重儿子为3
那么1->4->5->6为一条重链
2->3为一条重链
7为一条重链
思想
把整棵树划分成许多条链,使每个节点都在唯一的链上,对每一条链维护一棵线段树,把在树上的操作转移到线段树上
树链剖分的策略是轻重边路径剖分,这种策略可以保证整棵树上的轻边和链的数量都不超过O(logn)
过程
剖分
剖(pōu)分部(bù)分由两个dfs组成
dfs1
Aim : 求深度deep[],父节点fa[],大小size[],重儿子son[]
dfs2
Aim : 标记编号 更新权值 更新端顶 处理每一条链
端顶:所在重链中,父节点不在重链上的点
dfs2后标记的编号 为 线段树维护时的下标
dfs2 先处理重儿子 再处理轻儿子
查询与修改路径信息
修改或查询 u, v u,v之间路径上的信息,采取以下策略:
首先假设 u 的深度更大,那么修改或查询 u 所在链的链顶结点到 u 这条路径上所有结点的信息,然后将 u 跳到其链顶结点的父节点(即端顶的父节点)重复以上步骤直到 u 与 v 在同一条链上为止。最后修改或查询两点间上结点路径的信息。
扩展
最近公共祖先
不难看出,上述查询或修改路径的过程,实际上是分别修改或查询了 u 到两点间最近公共祖先的路径与 v 到两点间最近公共祖先的路径,所以不难看出,只需去掉查询与修改路径信息的过程,即可求得最近公共祖先
后
注释的时候把线段树的操作也注释了,所以显得有点麻烦。
(不过还是不错的哈~)
#include<iostream>
#include<cstdio>
using namespace std;
const int L = 200000 + 10;
int n,m,s,mod,data[L]; // data[]初始点权
int res;
/* 前向星存图 */
struct edge {
int to , next;
};
edge e[L];
int head[L],cnt = 0;
/* 加边操作 前向星 不解释了 */
void add(int u , int v) {
e[++cnt].next = head[u];
e[cnt].to = v;
head[u] = cnt;
}
/* fa[]父亲节点 size[]子树大小 deep[]深度 son[]重儿子编号 */
int fa[L],size[L],deep[L],son[L];
/* 求deep[] fa[] size[] son[] */
void dfs1(int u , int father , int dep) { // dfs1(当前节点 , 父节点 , 深度)
deep[u] = dep;
fa[u] = father;
size[u] = 1; // 最初只包括 u 一个点
for(int i = head[u] ; i ; i = e[i].next) { // 前向星
int v = e[i].to; // u 所连的子节点 v
if(v == father) // 父节点已被更新 直接continue
continue ;
dfs1(v , u , dep + 1); // 深搜子节点 v
size[u] += size[v]; // 当前节点的子树大小为各子树大小之和
if(size[v] > size[son[u]]) // 当前节点的子树比已经标记重儿子的子树大
son[u] = v; // 标记 v 为 u 的重儿子
}
}
/* id[]编号数组 top[]当前链顶端节点 num[]权值数组 */
int id[L],top[L],num[L],mem = 0;
/* 标记编号 更新权值 更新端顶 处理每一条链 */
void dfs2(int u , int topf) { // dfs2(当前节点 ,所在链端顶)
id[u] = ++mem; // 更新编号
num[mem] = data[u]; // 更新权值
top[u] = topf; // 更新端顶
if(!son[u]) // 没有重儿子(叶节点)
return ;
dfs2(son[u] , topf); // 先处理重儿子
for(int i = head[u] ; i ; i = e[i].next) { // 前向星
int v = e[i].to; // u 的轻儿子 v
if(fa[u] == v || son[u] == v) // 不是父节点 不是重儿子
continue ;
dfs2(v , v); // 后处理轻儿子
}
}
/* 结构体维护线段树 */
struct node {
int sum , lazy; // sum权值和 lazy懒标记
};
node tag[L<<2];// 线段树开4倍空间
/* 标记下放 更新左右儿子节点 */
void pushdown(int u , int len) { // pushdown(当前节点 , 区间长度)
tag[u<<1].lazy += tag[u].lazy; // 懒标记下压到左儿子
tag[u<<1].sum += tag[u].lazy*(len - (len>>1)); // 更新左儿子权值
tag[u<<1].sum %= mod; // 取模
tag[u<<1|1].lazy += tag[u].lazy; // 懒标记下压到右儿子
tag[u<<1|1].sum += tag[u].lazy*(len>>1); // 更新右儿子权值
tag[u<<1|1].sum %= mod; //取模
tag[u].lazy = 0; // 更新父节点懒标记
}
/* 线段树建树 */
void build(int u ,int l, int r) { //build(当前节点 , 左端点 , 右端点)
if(l == r) { // 找到叶节点
tag[u].sum = num[l]; // 更新线段树权值
if(tag[u].sum > mod) //取模
tag[u].sum %= mod;
return ;
}
int mid = (l + r)>>1;
build(u<<1 , l , mid); // 建左子树
build(u<<1|1 , mid + 1 , r); // 建右子树
tag[u].sum=(tag[u<<1].sum + tag[u<<1|1].sum) % mod; // 更新当前节点 并 取模
}
/* 线段树实现区间更新 */
void update(int u ,int l, int r,int nl,int nr,int k) { //update(当前节点 ,左端点 , 右端点 , 被更新的左端 , 被更新的右端点 , 更新值)
if(nl <= l && nr >= r) { // 找到区间
tag[u].lazy += k; // 更新懒标记
tag[u].sum += k*(r - l + 1); // 更新区间权值
}
else {
if(tag[u].lazy) // 下压懒标记
pushdown(u , r - l + 1);
int mid = (l + r)>>1;
if(nl <= mid)
update(u<<1 , l , mid , nl , nr , k); // 更新左子树中的部分
if(nr >mid)
update(u<<1|1 , mid + 1 , r , nl , nr , k); // 更新右子树中的部分
tag[u].sum = (tag[u<<1].sum + tag[u<<1|1].sum) % mod; // 更新当前节点权值 并 取模
}
}
/* 线段树实现区间查询 */
void query(int u , int l , int r, int nl , int nr) { // query(当前节点 ,左端点 , 右端点 , 查找左端点 , 查找右端点)
if(nl <= l && nr >= r) { // 找到区间
res += tag[u].sum; // 答案加当前区间的权值
res %= mod; // 取模
return ;
}
if(tag[u].lazy) // 下压懒标记
pushdown(u , r - l + 1);
int mid = (l + r)>>1;
if(nl <= mid)
query(u<<1 , l , mid , nl , nr); // 查找左子树部分
if(nr > mid)
query(u<<1|1 , mid + 1 , r , nl , nr); // 查找右子树部分
}
/* 树剖实现子树路径更新 */
void upd_road(int x,int y,int z) { //upd_road(起点 , 终点 , 更新值)
z %= mod; // 先取模
while(top[x] != top[y]) { //如果端顶不同
if(deep[top[x]] < deep[top[y]]) // 保证 x端顶 在 y端顶 下
swap(x,y);
update(1,1,n,id[top[x]],id[x],z); // 线段树上更新 x 部分区间
x = fa[top[x]]; // 上爬到端顶的父节点
}
if(deep[x] > deep[y]) // 保证 x 在 y 上
swap(x,y);
update(1,1,n,id[x],id[y],z); // 更新 x 与 y 之间的区间
}
/* 树剖实现查询两点间路径点权和 */
int query_road(int x,int y) { // query_road(起点 , 终点)
int ans = 0;
while(top[x] != top[y]) { // 如果端顶不同
if(deep[top[x]] < deep[top[y]]) // 保证 x端顶 在 y端顶 下
swap(x,y);
res = 0;
query(1,1,n,id[top[x]],id[x]); // 查找 x 部分区间
ans += res; // 更新答案
ans %= mod; // 取模
x = fa[top[x]]; // 上爬到端顶的父节点
}
if(deep[x] > deep[y]) // 保证 x 在 y 上
swap(x,y);
res = 0;
query(1,1,n,id[x],id[y]); // 查找 x 与 y 之间区间
ans += res; // 更新答案
return ans %= mod; // 取模 并 输出
}
/* 树剖实现一点及其子树修改 */
void upd_son(int x,int y) {
update(1,1,n,id[x],id[x]+size[x]-1,y); // 在线段树上实现区间修改
}
/* 树剖实现一点及其子树查询 */
int query_son(int x) {
res = 0;
query(1,1,n,id[x],id[x]+size[x]-1); // 在线段树上实现区间查询
return res;
}
int main() {
scanf("%d%d%d%d",&n,&m,&s,&mod);
for(int i = 1; i <= n; i++)
scanf("%d",&data[i]);
for(int i = 1; i < n; i++) {
int x,y;
scanf("%d%d",&x,&y);
add(x , y); //加边
add(y , x);
}
dfs1(s,0,1); //第一次深搜
dfs2(s,s); //第二次深搜
build(1,1,n); //线段树建树
for(int i = 1; i <= m; i++) {
int p;
scanf("%d",&p);
if(p == 1) { //两点间最短路径所有节点值修改
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
upd_road(x,y,z);
}
if(p == 2) { //查询两点间最短路径所有节点点权和
int x,y,z;
scanf("%d%d",&x,&y);
z = query_road(x,y);
printf("%d\n",z);
}
if(p == 3) { //一个点及其子树点权修改
int x,y;
scanf("%d%d",&x,&y);
upd_son(x,y);
}
if(p == 4) { //查询一个点及其子树所有点权权值和
int x,y;
scanf("%d",&x);
y = query_son(x);
printf("%d\n",y);
}
}
return 0;
}