差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:lct [2021/07/08 19:31]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:lct [2021/07/11 16:30] (当前版本)
jxm2001 [子树信息维护]
@@ 行 1: / 行 1: @@
-====== 动态树 ======
+====== LCT ======
 ===== 算法简介 =====
-动态树简称 LCT ，是一种动态维护森林连通性、路径信息的数据结构，时间复杂度为 $O\left(n\log n\right)$
+LCT 是一种动态维护森林连通性、路径信息的数据结构，时间复杂度为 $O\left(n\log n\right)$。
 ===== 算法思想 =====
@@ 行 34: / 行 34: @@
 ===== 代码模板 =====
-<hidden 查看代码>
-<code cpp>
-struct Link_Cut_tree{
-	int ch[MAXN][2],fa[MAXN],w[MAXN],s[MAXN];
-	int Stack[MAXN],top;
-	bool flip[MAXN];
-	#define lch(k) ch[k][0]
-	#define rch(k) ch[k][1]
-	void build(int *a,int n){
-		_rep(i,1,n){
-			ch[i][0]=ch[i][1]=fa[i]=0;
-			s[i]=w[i]=a[i];
-			flip[i]=false;
-		}
-	}
-	void push_up(int k){
-		s[k]=s[lch(k)]^s[rch(k)]^w[k];//自定义
-	}
-	void push_flip(int k){
-		swap(lch(k),rch(k));
-		flip[k]^=1;
-	}
-	void push_down(int k){
-		if(flip[k]){
-			push_flip(lch(k));
-			push_flip(rch(k));
-			flip[k]=0;
-		}
-	}
-	bool isroot(int k){
-		return lch(fa[k])!=k&&rch(fa[k])!=k;
-	}
-	void rotate(int k){
-		int pa=fa[k],ga=fa[pa],dir;
-		dir=ch[pa][0]==k?0:1;
-		if(!isroot(pa))ch[ga][ch[ga][0]==pa?0:1]=k;
-		fa[k]=ga,fa[pa]=k;
-		if(ch[k][dir^1])fa[ch[k][dir^1]]=pa;
-		ch[pa][dir]=ch[k][dir^1],ch[k][dir^1]=pa;
-		push_up(pa);
-	}
-	void splay(int k){
-		Stack[top=1]=k;
-		for(int i=k;!isroot(i);i=fa[i])Stack[++top]=fa[i];
-		while(top)push_down(Stack[top--]);
-		while(!isroot(k)){
-			int pa=fa[k],ga=fa[pa];
-			if(!isroot(pa))rotate((ch[pa][0]==k)^(ch[ga][0]==pa)?k:pa);
-			rotate(k);
-		}
-		push_up(k);
-	}
-	void access(int k){
-		for(int t=0;k;t=k,k=fa[k]){
-			splay(k);
-			ch[k][1]=t;
-			push_up(k);
-		}
-	}
-	void makeroot(int k){
-		access(k);
-		splay(k);
-		push_flip(k);
-	}
-	int findroot(int k){
-		access(k);splay(k);
-		push_down(k);
-		while(ch[k][0])push_down(k=ch[k][0]);
-		splay(k);
-		return k;
-	}
-	void split(int u,int v){
-		makeroot(u);
-		access(v);
-		splay(v);
-	}
-	void link(int u,int v){
-		makeroot(u);
-		if(findroot(v)!=u)fa[u]=v;
-	}
-	void cut(int u,int v){
-		split(u,v);
-		if(ch[v][0]==u&&ch[u][1]==0){
-			ch[v][0]=fa[u]=0;
-			push_up(v);
-		}
-	}
-	void change(int k,int v){
-		access(k);splay(k);
-		w[k]=v;
-		push_up(k);
-	}
-};
-</code>
-</hidden>
-===== 代码练习 =====
-==== 路径信息维护 ====
-=== 例题一 ===
 [[https://www.luogu.com.cn/problem/P3690|洛谷p3690]]
@@ 行 141: / 行 39: @@
 给定 $n$ 个点和权值，接下来 $m$ 个操作。
-操作 $0$ ：询问 $x$ 到 $y$ 路径的权值的异或和，保证 $x$ 与 $y$ 已经连通。
+  - 询问 $x$ 到 $y$ 路径的权值的异或和，保证 $x$ 与 $y$ 已经连通
+  - 连接 $x$ 与 $y$ ，若 $x$ 与 $y$ 已经连通，则无视这个操作
-操作 $1$ ：连接 $x$ 与 $y$ ，若 $x$ 与 $y$ 已经连通，则无视这个操作。
+  - 删除 $x$ 与 $y$ 的连边，若 $x$ 与 $y$ 无连边，则无视这个操作
+  - 把结点 $x$ 的权值改为 $y$
-操作 $2$ ：删除 $x$ 与 $y$ 的连边，若 $x$ 与 $y$ 无连边，则无视这个操作。
-操作 $3$ ：把结点 $x$ 的权值改为 $y$。
-一道LCT裸题，直接上代码。
 <hidden 查看代码>
@@ 行 270: / 行 163: @@
 </hidden>
-=== 例题二 ===
+===== 代码练习 =====
-[[https://www.luogu.com.cn/problem/P1501|洛谷p1501]]
+==== 路径信息维护 ====
-给定一棵 $n$ 个结点的树，每个结点初始权值为 $1$ ，接下来 $q$ 个操作：
+=== 例题一 ===
-操作 $1$ ：将 $u$ 到 $v$ 路径上所有点权值加上 $c$。
+[[https://www.luogu.com.cn/problem/P1501|洛谷p1501]]
-操作 $2$ ：删除 $u_1$ 与 $v_1$ 的连边，添加 $u_2$ 与 $v_2$ 的连边，保证操作后仍然是一棵树。
+给定一棵 $n$ 个结点的树，每个结点初始权值为 $1$ ，接下来 $q$ 个操作：
-操作 $3$ ：将 $u$ 到 $v$ 路径上所有点权值乘上 $c$。
-操作 $4$ ：查询 $u$ 到 $v$ 路径上权值和。
+  - 将 $u$ 到 $v$ 路径上所有点权值加上 $c$
+  - 删除 $u_1$ 与 $v_1$ 的连边，添加 $u_2$ 与 $v_2$ 的连边，保证操作后仍然是一棵树
+  - 将 $u$ 到 $v$ 路径上所有点权值乘上 $c$
+  - 查询 $u$ 到 $v$ 路径上权值和
 一道简单LCT练手题，多加几个懒标记即可。
@@ 行 439: / 行 333: @@
-=== 例题三 ===
+=== 例题二 ===
 [[https://www.luogu.com.cn/problem/P3703|洛谷p3703]]
-**题意**
+给定一棵以 $1$ 为根节点的有根树，初始时每个节点的颜色互不相同，定义路径的权值为路径节点的颜色种数。接下来 $m$ 个操作：
+  - 将根节点到 $u$ 的路径染成一个从未出现的颜色
+  - 查询 $u\to v$ 路径权值
+  - 查询所有以 $u$ 为根的子树节点中到 $1$ 节点的路径的最大权值
+考虑维护每个点 $u$ 到根节点的路径权值，记为 $\text{dis}(u)$，不难发现操作 $2$ 等效于查询 $\text{dis}(u)+\text{dis}(v)-2\text{dis}(\text{lca}(u,v))+1$。
-**题解**
+对于操作 $3$，等价于查询以 $u$ 为根的子树的最大权值。
+接下来重点考虑操作 $1$，联想到 $\text{LCA}$ 的 $\text{access}$ 操作。
+假如一开始所有连边均为虚边，不难发现 $\text{dis}(u)$ 等于 $u$ 到根节点的虚边数 $+1$，然后操作 $1$ 正好等价于 $\text{access}(u)$ 操作。
+然后考虑更新答案，发现 $\text{access}(u)$ 过程中将 $u\to v$ 的实边变成虚边只需要将 $v$ 子树所有点权值加一即可，相对的虚边变实边对应子树点权减一。
+考虑再建一棵线段树维护，另外注意 $\text{access}(u)$ 过程中涉及的节点 $v$ 对应的是 $\text{splay}$ 子树的根节点，不是真正需要的深度最小的点。
+为了找到深度最小的节点可以考虑利用 $\text{splay}$ 的 $\text{push_up}$ 维护。总时间复杂度 $O(n\log n)$。
+ps. 树剖也可做，但比较复杂，需要魔改，可以参考这篇 [[https://www.luogu.com.cn/blog/Feliks-GMYB/solution-p3703|题解]]
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5;
+struct Edge{
+	int to,next;
+}edge[MAXN<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v){
+	edge[++edge_cnt]=Edge{v,head[u]};
+	head[u]=edge_cnt;
+}
+namespace Tree{
+	int d[MAXN],sz[MAXN],f[MAXN],dfn[MAXN],dfs_t;
+	int hson[MAXN],mson[MAXN],p[MAXN],dfw[MAXN];
+	void dfs1(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;
+			dfs1(v,u,depth+1);
+			sz[u]+=sz[v];
+			if(sz[v]>mson[u]){
+				hson[u]=v;
+				mson[u]=sz[v];
+			}
+		}
+	}
+	void dfs2(int u,int top){
+		dfn[u]=++dfs_t,p[u]=top;
+		dfw[dfs_t]=d[u];
+		if(mson[u])
+		dfs2(hson[u],top);
+		for(int i=head[u];i;i=edge[i].next){
+			int v=edge[i].to;
+			if(v==f[u]||v==hson[u])continue;
+			dfs2(v,v);
+		}
+	}
+	int lef[MAXN<<2],rig[MAXN<<2],s[MAXN<<2],tag[MAXN<<2];
+	void push_up(int k){
+		s[k]=max(s[k<<1],s[k<<1|1]);
+	}
+	void push_add(int k,int v){
+		s[k]+=v;
+		tag[k]+=v;
+	}
+	void push_down(int k){
+		if(tag[k]){
+			push_add(k<<1,tag[k]);
+			push_add(k<<1|1,tag[k]);
+			tag[k]=0;
+		}
+	}
+	void build(int k,int L,int R){
+		lef[k]=L,rig[k]=R;
+		int M=L+R>>1;
+		if(L==R){
+			s[k]=dfw[M];
+			return;
+		}
+		build(k<<1,L,M);
+		build(k<<1|1,M+1,R);
+		push_up(k);
+	}
+	void init(int n){
+		dfs1(1,0,1);
+		dfs2(1,1);
+		build(1,1,n);
+	}
+	void update(int k,int L,int R,int v){
+		if(L<=lef[k]&&rig[k]<=R){
+			push_add(k,v);
+			return;
+		}
+		push_down(k);
+		int mid=lef[k]+rig[k]>>1;
+		if(mid>=L)
+		update(k<<1,L,R,v);
+		if(mid<R)
+		update(k<<1|1,L,R,v);
+		push_up(k);
+	}
+	void update(int u,int w){
+		update(1,dfn[u],dfn[u]+sz[u]-1,w);
+	}
+	int query(int k,int pos){
+		if(lef[k]==rig[k])
+		return s[k];
+		push_down(k);
+		int mid=lef[k]+rig[k]>>1;
+		if(mid>=pos)
+		return query(k<<1,pos);
+		else
+		return query(k<<1|1,pos);
+	}
+	int query(int k,int L,int R){
+		if(L<=lef[k]&&rig[k]<=R)
+		return s[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
+		return max(query(k<<1,L,R),query(k<<1|1,L,R));
+	}
+	int lca(int u,int v){
+		while(p[u]!=p[v]){
+			if(d[p[u]]<d[p[v]])swap(u,v);
+			u=f[p[u]];
+		}
+		return d[u]<d[v]?u:v;
+	}
+	int query1(int u,int v){
+		return query(1,dfn[u])+query(1,dfn[v])-2*query(1,dfn[lca(u,v)])+1;
+	}
+	int query2(int u){
+		return query(1,dfn[u],dfn[u]+sz[u]-1);
+	}
+}
+struct Link_Cut_tree{
+	int ch[MAXN][2],fa[MAXN],s[MAXN],dis[MAXN];
+	#define lch(k) ch[k][0]
+	#define rch(k) ch[k][1]
+	void build(int n){
+		_rep(i,1,n){
+			ch[i][0]=ch[i][1]=0;
+			fa[i]=Tree::f[i];
+			s[i]=i;
+			dis[i]=Tree::d[i];
+		}
+	}
+	void push_up(int k){
+		if(lch(k))
+		s[k]=s[lch(k)];
+		else
+		s[k]=k;
+	}
+	bool isroot(int k){
+		return lch(fa[k])!=k&&rch(fa[k])!=k;
+	}
+	void rotate(int k){
+		int pa=fa[k],ga=fa[pa],dir;
+		dir=ch[pa][0]==k?0:1;
+		if(!isroot(pa))ch[ga][ch[ga][0]==pa?0:1]=k;
+		fa[k]=ga,fa[pa]=k;
+		if(ch[k][dir^1])fa[ch[k][dir^1]]=pa;
+		ch[pa][dir]=ch[k][dir^1],ch[k][dir^1]=pa;
+		push_up(pa);
+	}
+	void splay(int k){
+		while(!isroot(k)){
+			int pa=fa[k],ga=fa[pa];
+			if(!isroot(pa))rotate((ch[pa][0]==k)^(ch[ga][0]==pa)?k:pa);
+			rotate(k);
+		}
+		push_up(k);
+	}
+	void access(int k){
+		for(int t=0;k;t=k,k=fa[k]){
+			splay(k);
+			if(ch[k][1])Tree::update(s[ch[k][1]],1);
+			if(t)Tree::update(s[t],-1);
+			ch[k][1]=t;
+			push_up(k);
+		}
+	}
+}LCT;
+int main()
+{
+	int n=read_int(),m=read_int();
+	_for(i,1,n){
+		int u=read_int(),v=read_int();
+		Insert(u,v);
+		Insert(v,u);
+	}
+	Tree::init(n);
+	LCT.build(n);
+	while(m--){
+		int opt=read_int();
+		if(opt==1)
+		LCT.access(read_int());
+		else if(opt==2){
+			int u=read_int(),v=read_int();
+			enter(Tree::query1(u,v));
+		}
+		else
+		enter(Tree::query2(read_int()));
+	}
+	return 0;
+}
+</code>
+</hidden>
 ==== 生成树维护 ====
@@ 行 888: / 行 993: @@
 [[https://www.luogu.com.cn/problem/P3379|洛谷p3379]]
-$\text{LCT}$ 本身支持换根，所以只需要怎么考虑求 $\text{LCA}$(u,v)。
+$\text{LCT}$ 本身支持换根，所以只需要怎么考虑求 $\text{LCA}(u,v)$。
 考虑先 $\text{access}(u)$ 这样根节点到 $u$ 的路径变实边，于是根节点到 $v$ 的路径的第一条虚边一定从 $\text{LCA}(u,v)$ 出发。
@@ 行 997: / 行 1102: @@
 给定一个连通图，接下来两种操作：
-  - 询问 $u,v$ 间的关键路径，定义关键路径为删除改路径讲导致 $u,v$ 不连通的路径。
+  - 询问 $u,v$ 间的关键路径，定义关键路径为删除改路径讲导致 $u,v$ 不连通的路径
   - 删除边 $u,v$，保证删边后图仍然连通
@@ 行 1162: / 行 1267: @@
 ==== 子树信息维护 ====
+[[https://www.luogu.com.cn/problem/P4219|洛谷p4219]]
+**题意**
+给定 $n$ 个点，给定两种操作：
+  - 加边操作，保证加边后不会出现环
+  - 询问经过 $(u,v)$ 边的路径数
+**题解**
 子树信息需要维护虚儿子和实儿子信息和，实儿子利用 $\text{ch}(k,0/1)$ 维护，虚儿子只需要额外记录即可。
@@ 行 1197: / 行 1313: @@
 注意，如果需要维护点权极值等信息时，可以用 $\text{set}$ 维护 $si[k]$。
-[[https://www.luogu.com.cn/problem/P4219|洛谷p4219]]
-**题意**
-给定 $n$ 个点，给定两种操作：
-  - 加边操作，保证加边后不会出现环
-  - 询问经过 $u\to v$ 边的路径数。
-**题解**
 不难发现，对询问操作，可以先断开 $u,v$，则答案为 $\text{sz}(u)\times \text{sz}(v)$。

CVBB ACM Team

用户工具

站点工具

差别

页面工具