差别

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

--- 2020-2021:teams:legal_string:jxm2001:长链剖分 [2020/05/29 20:44]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:长链剖分 [2020/07/27 22:54] (当前版本)
jxm2001 ↷ 页面2020-2021:teams:legal_string:长链剖分被移动至2020-2021:teams:legal_string:jxm2001:长链剖分
@@ 行 5: / 行 5: @@
 一种可以在线性时间复杂度维护子树中**仅限深度有关的信息**的算法，主要用于一些特殊的 $\text{dp}$
-===== 算法思想 ====
+===== 算法思想 =====
 类似重链剖分，将儿子分为重儿子和轻儿子，重儿子组成的链构成长链
@@ 行 11: / 行 11: @@
 但不同的是重链剖分重儿子是子树结点最多的结点，长链剖分长儿子是子树深度最大的结点
-长链剖分的一个重要性质是一个结点 $x$ 的 $k$ 级祖先所在的长链长度一定 $\ge k$
+长链剖分有两个重要性质
-考虑结点 $x$ 和它的 $k$ 级祖先 $y$，如果 $x$ 和 $y$ 属于同一条长链，上述性质成立
+性质一：所有长链长度和为 $n$
-如果 $x$ 和 $y$ 不属于同一条长链，知 $y$ 的重儿子子树的深度一定大于 $x$ 的深度，所以上述性质也成立
+显然所有点均属于且仅属于一条长链，所以性质一成立
+性质二：长链剖分的一个重要性质是一个结点 $x$ 的 $k$ 级祖先所在的长链长度一定 $\ge k$
+考虑结点 $x$ 和它的 $k$ 级祖先 $y$，如果 $x$ 和 $y$ 属于同一条长链，该情况下性质二成立
+如果 $x$ 和 $y$ 不属于同一条长链，知 $y$ 的重儿子子树的深度一定大于 $x$ 的深度，该情况下性质二也成立
 ===== 算法应用 =====
@@ 行 43: / 行 49: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <algorithm>
-#include <cstring>
-#include <cctype>
-#include <vector>
-#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 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=5e5+5,MAXM=21;
 unsigned int s;
@@ 行 162: / 行 143: @@
 给定一棵 $n$ 个结点的树，问有多少个无序点对 $(i,j,k)$ 满足 $i,j,k$ 两两间距离相等
+树形$\text{dp}$，状态转移方程可以参考这份博客[[https://www.luogu.com.cn/blog/xht37/solution-p3565|详情]]
+利用指针位移使得父结点以 $O(1)$ 时间继承重儿子信息，暴力继承轻儿子信息
+设当前结点为 $u$，$u$ 的儿子结点为 $x$，每次暴力继承时间复杂度为 $O\left(\text{len}\left(x\right)\right)$
+总时间复杂度为 $\sum_u\left(\left(\sum_x \text{len}\left(x\right)\right)-\text{len}\left(u\right)+1\right)$
+每个结点仅在 $\sum_u\left(\left(\sum_x \text{len}\left(x\right)\right)\right)$ 作为它的父结点的子结点出现一次
+所以有 $\sum_u\left(\left(\sum_x \text{len}\left(x\right)\right)\right)=\sum_u \text{len}\left(u\right)-\text{len}(root)$
+所以总时间复杂度为 $O\left(n\right)$
+<hidden 查看代码>
+<code cpp>
+const int MAXN=5e5+5;
+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],Son[MAXN],len[MAXN];
+LL *f[MAXN],*g[MAXN],dp[MAXN<<2],*pos=dp,ans;
+void Malloc(int u){
+	f[u]=pos,pos+=len[u]<<1;
+	g[u]=pos,pos+=len[u]<<1;
+}
+void dfs_1(int u,int depth,int fa){
+	d[u]=depth;Son[u]=0;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)
+		continue;
+		dfs_1(v,depth+1,u);
+		if(len[v]>len[Son[u]])
+		Son[u]=v;
+	}
+	len[u]=len[Son[u]]+1;
+}
+void dfs_2(int u,int fa){
+	if(Son[u]){
+		f[Son[u]]=f[u]+1,g[Son[u]]=g[u]-1;
+		dfs_2(Son[u],u);
+	}
+	f[u][0]=1,ans+=g[u][0];
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa||v==Son[u])
+		continue;
+		Malloc(v);
+		dfs_2(v,u);
+		_for(i,0,len[v]){
+			if(i) ans+=f[u][i-1]*g[v][i];
+			ans+=g[u][i+1]*f[v][i];
+		}
+		_for(i,0,len[v]){
+			g[u][i+1]+=f[u][i+1]*f[v][i];
+			if(i) g[u][i-1]+=g[v][i];
+			f[u][i+1]+=f[v][i];
+		}
+	}
+}
+int main()
+{
+	int n=read_int(),u,v,root=1;
+	_for(i,1,n){
+		u=read_int();v=read_int();
+		Insert(u,v);
+		Insert(v,u);
+	}
+	dfs_1(root,0,0);
+	Malloc(root);
+	dfs_2(root,0);
+	enter(ans);
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具