CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:重链剖分 [2020/05/14 09:44]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:重链剖分 [2021/08/04 20:37] (当前版本)
jxm2001 [代码模板]
@@ 行 3: / 行 3: @@
 ===== 算法简介 =====
-一种动态维护树上路径、子树信息的算法，单次操作时间复杂度$O\left(\log^2 n\right)$
+一种动态维护树上路径、子树信息的算法，单次操作时间复杂度 $O\left(\log^2 n\right)$
-===== 算法思想 ====
+===== 算法思想 =====
 重链剖分的关键是把树上修改问题转化为区间修改问题
@@ 行 11: / 行 11: @@
 为方便理解，先考虑点权树问题
-使用dfs序可以把子树查询和修改问题转化区间修改问题，单次操作时间复杂度$O\left(\log n\right)$
+使用 dfs 序可以把子树查询和修改问题转化区间修改问题，单次操作时间复杂度 $O\left(\log n\right)$
-因此重链剖分重点在如何解决树上路径修改问题
+因此重链剖分重点在如何解决树上路径修改问题，考虑将树划分成若干条链，分别对每条链进行修改、查询操作，便可实现树上路径修改
-考虑将树划分成若干条链，分别对每条链进行修改、查询操作，便可实现树上路径修改
+为简化问题，先考虑根结点到某结点的路径，我们不希望看见该路径涉及成过多条链的情况，而将树划分成重路径和轻边可以很好地解决这一问题
-为简化问题，先考虑根结点到某结点的路径
-我们不希望看见该路径涉及成过多条链的情况，而将树划分成重路径和轻边可以很好地解决这一问题
 首先给出重儿子和轻儿子的定义：对于非叶子节点，将所有儿子中以其为根的子树含结点数最多的儿子定义为重儿子，其余为轻儿子
@@ 行 25: / 行 21: @@
 父节点向重儿子连一条重边，每个轻儿子连一条轻边。若干重边组成一条重链
-这样，根结点到某结点的
+这样，根结点到某结点的路径便被划分成若干条轻边和重链相间的路径
-所有路径分为两种，一种是过根结点的，一种是完全在根结点的某棵子树中的。因此可以考虑分治算法，选取一个点将无根树转换为有根树，然后递归处理每个棵以根节点的儿子为根的子树。如果选取树的重心作为根结点，则每棵子树的结点个数不超过$\frac n2$，因此递归深度不超过$\log n$
+易知每经过一条轻边，子树所含结点数减半，因此一条路径最多经过 $\log n$ 条轻边
-==== 例题 ====
+因此单次修改或查询根结点到某结点的路径的时间复杂度变为 $O\left(\log^2 n\right)$
-[[https://www.luogu.com.cn/problem/P3806|洛谷p3806]]
+而对于端点为两个非根结点的路径，可以考虑像倍增法求 $\text{LCA}$ 那样不断把两个结点往上提，直到两个结点位于同一条链
-题目大意是说给定一棵$n$个结点的正权树，多次查询，每次查询是否存在长度为$k$的路径
+===== 代码实现 =====
-对根结点，先考虑暴力法，用树形dp求出子树上各节点到根结点的距离，然后两两枚举，看看有没有两个结点距离和为$k$，这样每层递归的时间复杂度是$O(n^2)$,显然会T
+先一遍 dfs 处理出每个结点的深度、父结点、重儿子
-考虑用中途相遇法，可以将每层递归的时间复杂度优化到$O(n)$，单次查询时间复杂度$O(n\log n)$
+第二遍 dfs 确定 dfs 序和每条链的起点，注意 dfs 要先重儿子，再轻儿子，确保重链上 dfs 序连续
-但要注意两点
+路径上查询和修改操作需要每次选择路径两端点中所在链的顶端结点的深度较大的结点，线段树查询/修改后跳到所在链的顶端结点的父结点
-一、枚举过根结点的路径时路径两端点显然不能在同一棵子树里，所以要先求出一棵子树所有的$\text{dist}$，全部判断完后再进行标记
+===== 代码模板 =====
-二、题目给定$k\le 10^7$，所以不用标记大于$10^7$的$\text{dist}$
+[[https://www.luogu.com.cn/problem/P3384|洛谷p3384]]
-另一个优化是可以离线处理查询，这样只需要分治一次。
+模板题
-代码
+题目大意是说给定一棵 $n$ 个结点的点权树，每次操作为查询路径或子树上的权值和，或者给路径或子树上的每个点权值加 $v$ ，所有结果取模
+<hidden 查看代码>
 <code cpp>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <cctype>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=1e5+5;
 int mod;
@@ 行 147: / 行 115: @@
 	head[u]=m;
 }
-int d[MAXN],w[MAXN],sz[MAXN],f[MAXN],dfs_id[MAXN],dfs_t;
+int d[MAXN],w[MAXN],sz[MAXN],f[MAXN],dfn[MAXN],dfs_t;
-int h_son[MAXN],mson[MAXN],p[MAXN],dfs_w[MAXN];
+int h_son[MAXN],mson[MAXN],p[MAXN],dfw[MAXN];
 void dfs_1(int u,int fa,int depth){
-	sz[u]=1;f[u]=fa;d[u]=depth;mson[u]=0;
+	sz[u]=1,f[u]=fa,d[u]=depth,mson[u]=0;
 	for(int i=head[u];i;i=edge[i].next){
 		int v=edge[i].to;
@@ 行 164: / 行 132: @@
 }
 void dfs_2(int u,int top){
-	dfs_id[u]=++dfs_t;p[u]=top;dfs_w[dfs_t]=w[u];
+	dfn[u]=++dfs_t,p[u]=top;
+	dfw[dfs_t]=w[u];
 	if(mson[u])
 	dfs_2(h_son[u],top);
@@ 行 174: / 行 143: @@
 	}
 }
-LL query_son(int u){return tree.query(1,dfs_id[u],dfs_id[u]+sz[u]-1);}
+int query_path(int u,int v){
-void update_son(int u,int w){tree.update(1,dfs_id[u],dfs_id[u]+sz[u]-1,w);}
-LL query_path(int u,int v){
 	LL ans=0;
 	while(p[u]!=p[v]){
 		if(d[p[u]]<d[p[v]])
 		swap(u,v);
-		ans=(ans+tree.query(1,dfs_id[p[u]],dfs_id[u]))%mod;
+		ans=(ans+tree.query(1,dfn[p[u]],dfn[u]))%mod;
 		u=f[p[u]];
 	}
 	if(d[u]>d[v])
 	swap(u,v);
-	ans=(ans+tree.query(1,dfs_id[u],dfs_id[v]))%mod;
+	ans=(ans+tree.query(1,dfn[u],dfn[v]))%mod;
 	return ans;
 }
@@ 行 193: / 行 160: @@
 		if(d[p[u]]<d[p[v]])
 		swap(u,v);
-		tree.update(1,dfs_id[p[u]],dfs_id[u],w);
+		tree.update(1,dfn[p[u]],dfn[u],w);
 		u=f[p[u]];
 	}
 	if(d[u]>d[v])
 	swap(u,v);
-	tree.update(1,dfs_id[u],dfs_id[v],w);
+	tree.update(1,dfn[u],dfn[v],w);
 }
+int query_son(int u){return tree.query(1,dfn[u],dfn[u]+sz[u]-1);}
+void update_son(int u,int w){tree.update(1,dfn[u],dfn[u]+sz[u]-1,w);}
 int main()
 {
@@ 行 234: / 行 203: @@
 }
 </code>
+</hidden>
-==== 变式1 ====
+===== 算法习题 =====
-[[https://www.luogu.com.cn/problem/P4178|洛谷p4178]]
+=== 习题一 ===
-给定一棵$n$个结点的正权树和一个正数$k$，统计有多少对结点$(a,b)$满足$\text{dist}(a,b)\le k$
+[[https://www.luogu.com.cn/problem/P3038|洛谷p3038]]
-把中途相遇法换成名次树即可，时间复杂度$O(n\left(\log n\right)^2)$
+给出一棵 $n$ 个结点的边权树，初始边权全为 $0$ ，有 $m$ 个操作，操作为将一条路径上的边权加一或询问某条边的权值
+考虑一个点有唯一的父结点，因此可以把该点与父结点的连边的边权作为该点的点权。根结点权值任意，不影响结果
+而路径修改/查询注意跳过 $\text{LCA}$ 即可
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5;
+#define lowbit(x) ((x)&(-x))
+struct Tree{
+	LL c[2][MAXN],n;
+	void add(int pos,int v){
+		int k=pos;
+		while(pos<=n){
+			c[0][pos]+=v;
+			c[1][pos]+=v*(k-1);
+			pos+=lowbit(pos);
+		}
+	}
+	void update(int lef,int rig,int v){
+		add(lef,v);
+		add(rig+1,-v);
+	}
+	LL sum(int pos){
+		int k=pos;
+		LL ans1=0,ans2=0;
+		while(pos){
+			ans1+=c[0][pos];
+			ans2+=c[1][pos];
+			pos-=lowbit(pos);
+		}
+		return ans1*k-ans2;
+	}
+	int query(int lef,int rig){
+		return sum(rig)-sum(lef-1);
+	}
+}tree;
+struct Edge{
+	int to,next;
+}edge[MAXN<<1];
+int head[MAXN],m;
+void Insert(int u,int v){
+	edge[++m].to=v;
+	edge[m].next=head[u];
+	head[u]=m;
+}
+int d[MAXN],w[MAXN],sz[MAXN],f[MAXN],dfs_id[MAXN],dfs_t;
+int h_son[MAXN],mson[MAXN],p[MAXN],dfs_w[MAXN];
+void dfs_1(int u,int fa,int depth){
+	sz[u]=1;f[u]=fa;d[u]=depth;mson[u]=0;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)
+		continue;
+		dfs_1(v,u,depth+1);
+		sz[u]+=sz[v];
+		if(sz[v]>mson[u]){
+			h_son[u]=v;
+			mson[u]=sz[v];
+		}
+	}
+}
+void dfs_2(int u,int top){
+	dfs_id[u]=++dfs_t;p[u]=top;dfs_w[dfs_t]=w[u];
+	if(mson[u])
+	dfs_2(h_son[u],top);
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==f[u]||v==h_son[u])
+		continue;
+		dfs_2(v,v);
+	}
+}
+//LL query_son(int u){return tree.query(dfs_id[u]+1,dfs_id[u]+sz[u]-1);}
+//void update_son(int u,int w){tree.update(dfs_id[u]+1,dfs_id[u]+sz[u]-1,w);}
+LL query_path(int u,int v){
+	LL ans=0;
+	while(p[u]!=p[v]){
+		if(d[p[u]]<d[p[v]])
+		swap(u,v);
+		ans+=tree.query(dfs_id[p[u]],dfs_id[u]);
+		u=f[p[u]];
+	}
+	if(d[u]>d[v])
+	swap(u,v);
+	ans+=tree.query(dfs_id[u]+1,dfs_id[v]);
+	return ans;
+}
+void update_path(int u,int v,int w){
+	while(p[u]!=p[v]){
+		if(d[p[u]]<d[p[v]])
+		swap(u,v);
+		tree.update(dfs_id[p[u]],dfs_id[u],w);
+		u=f[p[u]];
+	}
+	if(d[u]>d[v])
+	swap(u,v);
+	tree.update(dfs_id[u]+1,dfs_id[v],w);
+}
+int main()
+{
+	int n=read_int(),q=read_int(),root=1,x,y;
+	char opt;
+	tree.n=n;
+	_for(i,1,n){
+		x=read_int(),y=read_int();
+		Insert(x,y);
+		Insert(y,x);
+	}
+	dfs_1(root,-1,0);
+	dfs_2(root,root);
+	while(q--){
+		opt=get_char();
+		x=read_int(),y=read_int();
+		if(opt=='P')
+		update_path(x,y,1);
+		else
+		enter(query_path(x,y));
+	}
+	return 0;
+}
+</code>
+</hidden>
+=== 习题二 ===
+[[https://www.luogu.com.cn/problem/P2486|洛谷p2486]]
+给定一棵个 $n$ 节点的点权树，共有 $m$ 个操作，操作分为两种：
+.将 $a$ 节点到节点 $b$ 的路径上的所有点(包括 $a$ 和 $b$ )都染成颜色 $c$
+.询问节点 $a$ 到节点 $b$ 的路径上的颜色段数量(颜色段的定义是极长的连续相同颜色被认为是一段)
+一道很好的重链剖分练手题，这里仅给出代码
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5;
+int lef_color,rig_color;
+struct Tree{
+	int a[MAXN<<2],lazy[MAXN<<2],lc[MAXN<<2],rc[MAXN<<2],sum[MAXN<<2];
+	int lef[MAXN<<2],rig[MAXN<<2];
+	void init(int n,int *w){
+		_rep(i,1,n)
+		a[i]=w[i];
+		build(1,1,n);
+	}
+	void push_up(int k){
+		sum[k]=sum[k<<1]+sum[k<<1|1];
+		lc[k]=lc[k<<1];
+		rc[k]=rc[k<<1|1];
+		if(rc[k<<1]==lc[k<<1|1])
+		sum[k]--;
+	}
+	void build(int k,int L,int R){
+		lef[k]=L,rig[k]=R;
+		int M=L+R>>1;
+		if(L==R){
+			sum[k]=1;
+			lc[k]=rc[k]=a[M];
+			return;
+		}
+		build(k<<1,L,M);
+		build(k<<1|1,M+1,R);
+		push_up(k);
+	}
+	void push_lazy(int k,int lz){
+		lazy[k]=lc[k]=rc[k]=lz;
+		sum[k]=1;
+	}
+	void push_down(int k){
+		if(lazy[k]){
+			push_lazy(k<<1,lazy[k]);
+			push_lazy(k<<1|1,lazy[k]);
+			lazy[k]=0;
+		}
+	}
+	int query(int k,int L,int R){
+		if(L<=lef[k]&&rig[k]<=R){
+			if(lef[k]==L)
+			lef_color=lc[k];
+			if(rig[k]==R)
+			rig_color=rc[k];
+			return sum[k];
+		}
+		push_down(k);
+		int mid=lef[k]+rig[k]>>1;
+		if(mid>=R)
+		return query(k<<1,L,R);
+		else if(mid<L)
+		return query(k<<1|1,L,R);
+		else{
+			if(rc[k<<1]==lc[k<<1|1])
+			return query(k<<1,L,R)+query(k<<1|1,L,R)-1;
+			else
+			return query(k<<1,L,R)+query(k<<1|1,L,R);
+		}
+	}
+	void update(int k,int L,int R,int c){
+		if(L<=lef[k]&&rig[k]<=R){
+			push_lazy(k,c);
+			return;
+		}
+		push_down(k);
+		int mid=lef[k]+rig[k]>>1;
+		if(mid>=L)
+		update(k<<1,L,R,c);
+		if(mid<R)
+		update(k<<1|1,L,R,c);
+		push_up(k);
+	}
+}tree;
+struct Edge{
+	int to,next;
+}edge[MAXN<<1];
+int head[MAXN],m;
+void Insert(int u,int v){
+	edge[++m].to=v;
+	edge[m].next=head[u];
+	head[u]=m;
+}
+int d[MAXN],w[MAXN],sz[MAXN],f[MAXN],dfs_id[MAXN],dfs_t;
+int h_son[MAXN],mson[MAXN],p[MAXN],dfs_w[MAXN];
+void dfs_1(int u,int fa,int depth){
+	sz[u]=1;f[u]=fa;d[u]=depth;mson[u]=0;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)
+		continue;
+		dfs_1(v,u,depth+1);
+		sz[u]+=sz[v];
+		if(sz[v]>mson[u]){
+			h_son[u]=v;
+			mson[u]=sz[v];
+		}
+	}
+}
+void dfs_2(int u,int top){
+	dfs_id[u]=++dfs_t;p[u]=top;dfs_w[dfs_t]=w[u];
+	if(mson[u])
+	dfs_2(h_son[u],top);
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==f[u]||v==h_son[u])
+		continue;
+		dfs_2(v,v);
+	}
+}
+int query_path(int u,int v){
+	int c1=-1,c2=-1,ans=0;
+	while(p[u]!=p[v]){
+		if(d[p[u]]<d[p[v]]){
+			swap(u,v);
+			swap(c1,c2);
+		}
+		ans+=tree.query(1,dfs_id[p[u]],dfs_id[u]);
+		if(c1==rig_color)
+		ans--;
+		c1=lef_color;
+		u=f[p[u]];
+	}
+	if(d[u]>d[v]){
+		swap(u,v);
+		swap(c1,c2);
+	}
+	ans+=tree.query(1,dfs_id[u],dfs_id[v]);
+	if(c1==lef_color)
+	ans--;
+	if(rig_color==c2)
+	ans--;
+	return ans;
+}
+void update_path(int u,int v,int w){
+	while(p[u]!=p[v]){
+		if(d[p[u]]<d[p[v]])
+		swap(u,v);
+		tree.update(1,dfs_id[p[u]],dfs_id[u],w);
+		u=f[p[u]];
+	}
+	if(d[u]>d[v])
+	swap(u,v);
+	tree.update(1,dfs_id[u],dfs_id[v],w);
+}
+int main()
+{
+	int n=read_int(),q=read_int(),root=1,x,y;
+	char opt;
+	_rep(i,1,n)
+	w[i]=read_int();
+	_for(i,1,n){
+		x=read_int(),y=read_int();
+		Insert(x,y);
+		Insert(y,x);
+	}
+	dfs_1(root,-1,0);
+	dfs_2(root,root);
+	tree.init(n,dfs_w);
+	while(q--){
+		opt=get_char();
+		x=read_int();y=read_int();
+		if(opt=='C')
+		update_path(x,y,read_int());
+		else
+		enter(query_path(x,y));
+	}
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

页面工具