首页 > 其他分享 >树链剖分

树链剖分

时间:2024-01-05 17:03:21浏览次数:33  
标签:剖分 ll update 树链 原型 void 节点 op

son[x]表示节点\(x\)的重儿子,若为\(0\),则说明\(x\)为叶子节点

id[x]表示节点\(x\)的dfs序编号

f[x]表示节点\(x\)的父节点

dep[x]表示节点\(x\)的深度

sz[x]表示节点为\(x\)的子树的大小

top[x]表示x所在重链顶部的节点

函数原型void dfs1(ll u,ll fa)

功能:计算dep[]f[]sz[]son[]

函数原型void dfs2(ll u,ll topu)

功能:计算id[]top[]和线段树每个位置的初始值。

函数原型void update_range(ll x,ll y,ll k)

功能:

函数原型ll query_range(ll x,ll y)

功能:

函数原型void update_tree(ll x,ll k)

功能:

函数原型ll query_tree(ll x)

功能:

#include<bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;
const ll N=1e5+10;
ll n,m,r,mod,w[N],a[N];
vector<ll> G[N];
ll dat[N<<2],lazy[N<<2];
ll son[N],id[N],f[N],dep[N],sz[N],top[N],tot;
void down(ll p,ll l,ll r){
	if(lazy[p]==0||l==r)return;
	lazy[p<<1]+=lazy[p],lazy[p<<1]%=mod;
	dat[p<<1]+=(mid-l+1)*lazy[p],dat[p<<1]%=mod;
	lazy[(p<<1)|1]+=lazy[p],lazy[(p<<1)|1]%=mod;
	dat[(p<<1)|1]+=(r-mid)*lazy[p],dat[(p<<1)|1]%=mod;
	lazy[p]=0;
}
void update(ll p,ll l,ll r,ll L,ll R,ll k){
	if(L<=l&&r<=R){
		dat[p]+=(r-l+1)*k,dat[p]%=mod;
		lazy[p]+=k,lazy[p]%=mod;
		return;
	}
	down(p,l,r);
	if(L<=mid)update(p<<1,l,mid,L,R,k);
	if(mid+1<=R)update((p<<1)|1,mid+1,r,L,R,k);
	dat[p]=dat[p<<1]+dat[(p<<1)|1],dat[p]%=mod;
}
ll query(ll p,ll l,ll r,ll L,ll R){
	if(L<=l&&r<=R)return dat[p];
	down(p,l,r);
	ll ret=0;
	if(L<=mid)ret+=query(p<<1,l,mid,L,R),ret%=mod;
	if(mid+1<=R)ret+=query((p<<1)|1,mid+1,r,L,R),ret%=mod;
	return ret;
}
void build(ll p,ll l,ll r){
	if(l==r){
		dat[p]=a[l];
		return;
	}
	build(p<<1,l,mid);
	build((p<<1)|1,mid+1,r);
	dat[p]=dat[p<<1]+dat[(p<<1)|1];
}
void dfs1(ll u,ll fa){
	dep[u]=dep[fa]+1,f[u]=fa,sz[u]=1;
	for(ll i=0;i<G[u].size();i++){
		ll v=G[u][i];
		if(v==fa)continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(sz[son[u]]<sz[v])son[u]=v;
	}
}
void dfs2(ll u,ll topu){
	a[id[u]=++tot]=w[u],top[u]=topu;
	if(!son[u])return;
	dfs2(son[u],topu);
	for(ll i=0;i<G[u].size();i++){
		ll v=G[u][i];
		if(v==f[u]||v==son[u])continue;
		dfs2(v,v);
	}
}
void update_range(ll x,ll y,ll k){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		update(1,1,n,id[top[x]],id[x],k);
		x=f[top[x]];
	}
	update(1,1,n,min(id[x],id[y]),max(id[x],id[y]),k);
}
ll query_range(ll x,ll y){
	ll ret=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		ret+=query(1,1,n,id[top[x]],id[x]),ret%=mod;
		x=f[top[x]];
	}
	ret+=query(1,1,n,min(id[x],id[y]),max(id[x],id[y])),ret%=mod;
	return ret;
}
void update_tree(ll x,ll k){
	update(1,1,n,id[x],id[x]+sz[x]-1,k);
}
ll query_tree(ll x){
	return query(1,1,n,id[x],id[x]+sz[x]-1);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> n >> m >> r >> mod;
	for(ll i=1;i<=n;i++)cin >> w[i],w[i]%=mod;
	for(ll i=1;i<=n-1;i++){
		ll u,v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs1(r,0);
	dfs2(r,r);
	build(1,1,n);
	while(m--){
		ll op,x,y,z;
		cin >> op >> x;
		if(op==1){
			cin >> y >> z;
			update_range(x,y,z);
		}else if(op==2){
			cin >> y;
			cout << query_range(x,y) << endl;
		}else if(op==3){
			cin >> z;
			update_tree(x,z);
		}else if(op==4){
			cout << query_tree(x) << endl;
		}
	}
	return 0;
}

标签:剖分,ll,update,树链,原型,void,节点,op
From: https://www.cnblogs.com/ningziang/p/17947626

相关文章

  • 【动态规划】长链剖分优化树形 dp
    我们在树形dp中经常会遇到这样一个模型:设\(f_{x,i}\)表示节点\(x\)的子树中深度为\(x\)的答案...有递推式:\(f_{x,i}=\sum_{son}f_{son,i-1/i+1}\dots\)。这样直接做是\(\Theta(n^2)\)的,我们考虑去优化这个dp。有一个小优化,就是我们想让\(f_x\)直接继承......
  • 【树链剖分】P3401 洛谷树 题解
    P3401考虑先将路径权值进行转化,因为很难对路径直接进行统计。考虑如何表示出这条路径的权值。记\(s_i=\oplus_{j\in\text{path}(1,i)}w_j\),其中\(\text{path}(i,j)\)表示\(i\)到\(j\)的路径上的边集。则\(u\tov\)的路径的权值为\(s_u\opluss_v\)。现在转变为......
  • 重链剖分的另一个性质
    我们大家都知道树的节点深度和是比树的节点高度和要大的,这个直观感受一下就能理解。什么时候这俩东西一样呢?答案是树形态形如一条链的时候。回忆重链剖分,重链剖分的一个性质是如果说我们把所有重链缩成一个点,形成的新树上节点深度最大是\(\logn\)级别,当然用完全二叉树就能把深......
  • 树链剖分
    树链剖分一、树链剖分的概念和写法1.1概念定义:树链剖分用于将树分割成若干条链的形式,以维护树上路径的信息。具体来说,将整棵树剖分为若干条链,使它组合成线性结构,然后用其他的数据结构维护信息。树链剖分(树剖/链剖)有多种形式,如重链剖分,长链剖分和用于Link/cutTree的剖分(有......
  • 重链剖分
    前置芝士:线段树,或树状数组,越熟练越好。(当然这不是意味着你不会线段树就看不懂这篇博客。)1.何为树链剖分树链剖分,简而言之,就是将树分成一条条链,然后用数据结构去维护这些链,以支持树上两点间的各种询问操作。据我所知,树链剖分大约有三种,分别是重链剖分、长链剖分和实链剖分。其......
  • 点集合的三角剖分
    点集合的三角剖分是指如何将一些离散的点集合组合成不均匀的三角形网格,使得每个点成为三角网中三角面的顶点。这个算法的用处很多,一个典型的意义在于可以通过一堆离散点构建的TIN实现对整个构网区域的线性控制,比如用带高程的离散点构建的TIN来表达地形。在实际工作中,使用最多的三......
  • 树链剖分
    注意事项:线段树中\(modify(),query()\)中\(>=,<=,>,<\)以及\(l,r,L,R\)#include<bits/stdc++.h>#definelsp<<1#definersp<<1|1#definelsonls,l,mid#definersonrs,mid+1,r#defineroot1,1,nusingnamespacestd;constint......
  • 树链剖分 学习心得
    Bug都写在代码开头了,就不复述了。还有一个智障的错误是注释调试代码的时候把同一行的正式代码也给注释掉了(写得非常精彩。/*  bug:1.rev、id要分清!      2.mod()函数的情况不能写一半就跑路!      3.别忘了先给tree build()一下!      4.出界......
  • 重链剖分
    代码思路主体部分:初始化,剖分链,求LCA(也就是dfs1,dfs2,LCA三个函数)辅助部分:structPoint{//节点信息多的时候会习惯开个结构体来存 intdep,siz,son,top,fath; //点的深度子树大小重儿子所在重链的链头父亲节点 //没有重儿子则son=0 intid,l,r;//求lca不......
  • 树链剖分【产品说明书】
    一种暴论:树链剖分=多叉树上分块+线段树适用范围总之就是数据结构的基础问题。总的来说,树链剖分可以在\(O(m\logn)\)的时间复杂度中,解决大多数树上路径问题,包括其修改、维护和查询。例如这样的一道模板题又例如……(请直接跳到本文最后一章)产品简介树链剖分有两种:重......