P3384 【模板】重链剖分/树链剖分-EW帮帮网

P3384 【模板】重链剖分/树链剖分

题目描述

如题，已知一棵包含 $N$ 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：

1 x y z，表示将树从 $x$ 到 $y$ 结点最短路径上所有节点的值都加上 $z$ 。
2 x y，表示求树从 $x$ 到 $y$ 结点最短路径上所有节点的值之和。
3 x z，表示将以 $x$ 为根节点的子树内所有节点值都加上 $z$ 。
4 x 表示求以 $x$ 为根节点的子树内所有节点值之和

输入格式

第一行包含 $4$ 个正整数 $N, M, R, P$ ，分别表示树的结点个数、操作个数、根节点序号和取模数（即所有的输出结果均对此取模）。

接下来一行包含 $N$ 个非负整数，分别依次表示各个节点上初始的数值。

接下来 $N - 1$ 行每行包含两个整数 $x, y$ ，表示点 $x$ 和点 $y$ 之间连有一条边（保证无环且连通）。

接下来 $M$ 行每行包含若干个正整数，每行表示一个操作。

输出格式

输出包含若干行，分别依次表示每个操作 $2$ 或操作 $4$ 所得的结果（对 $P$ 取模）。

输入输出样例 #1

输入 #1

输出 #1

2
21

说明/提示

【数据规模】

对于 $30\%$ 的数据： $\leq N \leq 10$ ， $\leq M \leq 10$ ；

对于 $70\%$ 的数据： $\leq N \leq {10}^3$ ， $\leq M \leq {10}^3$ ；

对于 $100\%$ 的数据： $1\le N \leq {10}^5$ ， $1\le M \leq {10}^5$ ， $1\le R\le N$ ， $1\le P \le 2^{30}$ 。所有输入的数均在 int 范围内。

【样例说明】

树的结构如下：

各个操作如下：

故输出应依次为 $2$ 和 $21$ 。

解析：

1.线段树：

线段树相关文章（本文默认读者已掌握）

2.重链剖分：

①dfs序

我们将 $u$ 点的dfs序定义为树上 $u$ 点被深搜到的次序，记作 $dfn_u$

如题目图： $dfn_2=1,dfn_1=2,dfn_3=3,dfn_4=4,dfn_5=5$

那么我们稍加思索可以发现任意节点其子树上的节点的 $df n$ 都大于该节点的。
因为想要遍历它的子树就必须先深搜到它，它的dfn自然小于其子树的了。

此外，我们可以发现，dfs持续进行，会有一条或多条链的 $df n$ 是连续的自然数。
因为深搜到某个点 $u$ 设 $dfn_u=x$ ，那么下一步紧接着搜它某儿子 $v$ ，那么 $dfn_v=dfn_u+1=x+1$ ，如此下来，就会有几条链的 $df n$ 是连续的

②重链

3.解题思路：

用树剖将树上问题化成区间问题
用线段树维护区间和。区间 $[i, j]$ 表示的是 $df n$ 分别为 $i, j$ 的两节点之间的点权值和

①操作1、2

找到 $x, y$ 所在重链的顶端分别记为 $top_x,top_y$ 。

如果 $top_x=top_y$ ，则 $x, y$ 处于同条重链， $df n$ 是连续的，直接区间 $dfn_x,dfn_y]$ 修改/查询即可

如果 $top_x≠top_y$ ，使 $deep[top_x]>deep[top_y]$ ( $d ee p [i]$ 为 $i$ 点的深度)，这可以用 $s w a p ()$ 函数实现。
因为 $deep[top_x]>deep[top_y]$ ，所以 $x \to y$ 的路径一定包含了 $x \to t o p [x]$ 的路径，而这条路径的 $df n$ 是连续的，区间 $dfn_x,dfn_{top_x}]$ 修改/查询即可。然后使 $x=fa_{top_x}$ ，来到其父节点，此时来到了一条新的重链上，可以重复上述过程了。最后他们一定会归于同条链，再对此时的 $[x, y]$ 修改/查询即可

②操作3、4

记以某个点 $u$ 为根的子树点数为 $size_u$ ，那么这棵子树上的所有点的 $df n$ 都在 $dfn_u,dfn_u+size_u-1]$ 中，所以修改时对这段区间修改就行了。

为了知道的 $df n$ 为 $i$ 的点的编号为多少，我们还需用一个 $r df n$ 数组来记录。用于线段树的初始化

4.代码

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
const int MAXN=800005;
int n,m,root,mod;
struct EDGE{
	int to,nxt;
}edge[MAXN];
int head[MAXN];
int tot;
void add(int u,int v){
	tot++;
	edge[tot].nxt=head[u];
	edge[tot].to=v;
	head[u]=tot;
}
struct ordinary_tree{
	int f,d,wc,c,size,dfn,top;
	//f当前点的父亲，d当前点的深度，wc当前点的重儿子
	//size当前点为根的子树大小，dfn当前点的深搜序，top当前点所在重链的顶端
}a[MAXN];//a[i]表示原编号为i的点的相关信息
void dfs1(int u,int fa){//第一次dfs求每个点的重儿子及子树大小
	a[u].size=1;
	a[u].f=fa;
	a[u].d=a[fa].d+1;
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v==fa) continue;
		dfs1(v,u);
		a[u].size+=a[v].size;
		if(a[v].size>a[a[u].wc].size) a[u].wc=v;
	}
}
int rdfn[MAXN];//rdfn[x]记录dfn为x的点的编号
int vistime;
void dfs2(int u,int Top){
	a[u].dfn=++vistime;//计数器得每个点的dfn
	rdfn[vistime]=u;
	a[u].top=Top;
	if(a[u].wc!=0){//没有重儿子的话就没有儿子，直接返回
		dfs2(a[u].wc,Top);//先搜重儿子，其链顶是从之前延续下来的
		for(int i=head[u];i;i=edge[i].nxt){
			int v=edge[i].to;
			if(v!=a[u].f&&v!=a[u].wc){//搜其他儿子，重儿子不要重复搜
				dfs2(v,v);//其它儿子就只能自起一条新重链
			}
		}
	}
}
/*------线段树相关内容--------*/
struct line_tree{
	int l,r,w,lzy;
}t[MAXN];
void pushup(int u){
	t[u].w=(t[u*2].w+t[u*2+1].w)%mod;
}
void build(int u,int L,int R){
	t[u].l=L;t[u].r=R;
	if(L==R){
		t[u].w=a[rdfn[L]].c;//代表区间为[L,L]的线段树点的初值是 dfn为L的点 的值，即a[rdfn[L]].c
	}
	else{
		int mid=(L+R)/2;
		build(u*2,L,mid);build(u*2+1,mid+1,R);
		pushup(u);
	}
}
bool in(int L,int R,int l,int r){
	return (L<=l)&&(R>=r);
}
bool nocr(int L,int R,int l,int r){
	return (L>r)||(R<l);
}
void maketag(int u,int x){
	int len=(t[u].r-t[u].l+1);
	t[u].w+=len*x%mod;
	t[u].lzy+=x; 
	t[u].w%=mod;
	t[u].lzy%=mod;
}
void pushdown(int u){
	maketag(u*2,t[u].lzy);
	maketag(u*2+1,t[u].lzy);
	t[u].lzy=0;
}
int query(int u,int L,int R){
	if(in(L,R,t[u].l,t[u].r)){
		return t[u].w;
	}
	else if(!nocr(L,R,t[u].l,t[u].r)){
		pushdown(u);
		return (query(u*2,L,R)+query(u*2+1,L,R))%mod; 
	}
	else return 0;
}
void update(int u,int L,int R,int x){
	if(in(L,R,t[u].l,t[u].r)){
		maketag(u,x);
	}
	else if(!nocr(L,R,t[u].l,t[u].r)){
		pushdown(u);
		update(u*2,L,R,x);
		update(u*2+1,L,R,x);
		pushup(u);
	}
}

void upd(int x,int y,int z){
	while(a[x].top!=a[y].top){//如果两top相等，说明此时x,y在同条链上
		if(a[a[x].top].d<a[a[y].top].d) swap(x,y);//保持x的top深度更大
		update(1,a[a[x].top].dfn,a[x].dfn,z);
		x=a[a[x].top].f;
	}
	update(1,min(a[x].dfn,a[y].dfn),max(a[x].dfn,a[y].dfn),z);
}
int qry(int x,int y){
	int ans=0;
	while(a[x].top!=a[y].top){
		if(a[a[x].top].d<a[a[y].top].d) swap(x,y);
		ans+=query(1,a[a[x].top].dfn,a[x].dfn);
		ans%=mod;
		x=a[a[x].top].f;
	}
	return (ans+query(1,min(a[x].dfn,a[y].dfn),max(a[x].dfn,a[y].dfn)))%mod;
}

signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m>>root>>mod;
	for(int i=1;i<=n;i++) cin>>a[i].c;
	int ui,vi;
	for(int i=1;i<n;i++){
		cin>>ui>>vi;
		add(ui,vi);add(vi,ui);
	}
	dfs1(root,0);
	dfs2(root,0);
	build(1,1,n);
	int x,y,z,work;
	while(m--){
		cin>>work;
		if(work==1){
			cin>>x>>y>>z;
			upd(x,y,z);//路径修改
		}
		else if(work==2){
			cin>>x>>y;
			cout<<qry(x,y)%mod<<endl;//路径查询
		}
		else if(work==3){
			cin>>x>>z;
			update(1,a[x].dfn,a[x].dfn+a[x].size-1,z);//子树修改
		}
		else if(work==4){
			cin>>x;
			cout<<query(1,a[x].dfn,a[x].dfn+a[x].size-1)%mod<<endl;//子树查询
		}
	}
	return 0;
}

码字不易，求给个赞吧QAQ

如有错误，欢迎在评论区指出！

P3384 【模板】重链剖分/树链剖分