长链剖分优化树形DP总结

长链剖分

规定若\(x\)为叶结点，则\(len[x]=1\)。

否则定义\(preferredchild[x]\)（以下简称\(pc[x]\)，称\(pc[x]\)为\(x\)的长儿子）为\(x\)的所有子结点\(ver\)中，\(len[ver]\)最大的一个。\(len[x]=len[pc[x]]+1\)。

这里的\(pc[x]\)相当于树链剖分中的\(heavychild[x]\)，类似地，我们可以认为整棵树被划分为了若干条互不相交的长链。

有什么用？

求LCA。

到底有什么用？

优化树形DP。

通过长链剖分，我们可以将一些状态下标为深度的树形DP优化至线性复杂度。

一道例题

给你一棵\(n\)个结点的树，根结点编号为\(1\)。对于每个结点\(x\)，求出以\(x\)为根的子树中到\(x\)路径的长度（边数）为多少的结点数最多，在结点数最多的条件下最小化路径的长度。

\(n \leq 1000000\)。

不准Dsu on Tree！

题解

先考虑普通的树形DP，设状态\(f[x][j]\)表示以\(x\)为根的子树中，到\(x\)距离为\(j\)的结点数。

转移方程显然：

\[f[x][0]=1
\]

\[f[x][j]=\sum_{ver是x的子结点}{f[ver][j-1]}
\]

时间复杂度\(O(n^2)\)。

但是对于本题，这样的算法无论时间还是空间都是无法接受的。

考虑优化这个树形DP。

定义\(f[x]\)的有效长度为\(len[x]-1\)，因为对于\(j>len[x]-1\)时，\(f[x][j]\)显然为\(0\)。

如果\(x\)只有一个子结点\(ver\)的话，转移显然为：

\[f[x][0]=1
\]

\[f[x][j]=f[ver][j-1]
\]

这样的转移可以使用指针\(O(1)\)地完成。

\[f[x]=f[ver]-1
\]

\[f[x][0]=1
\]

可以想到，如果\(x\)的子结点不止一个的话，我们也可以采取相同的方式，即先从\(x\)的所有子结点中选择一个子结点让\(x\) \(O(1)\)“继承”它的状态，其他子结点仍采用DP方法暴力合并。

可以发现，我们在将\(f[ver]\)合并到\(f[x]\)时，时间复杂度是\(O(len[ver])\)的。

为了使时间复杂度达到最优，我们选择继承的那个子结点必然是\(x\)的长儿子\(pc[x]\)，因为根据长儿子的定义，\(f[pc[x]]\)在所有的\(f[ver]\)中有效长度最长，这样继承可以最大程度地减少合并时遍历所带来的程序运行时间。

并且结合上面关于有效长度的叙述，我们还可以使用指针动态分配每个\(f[x]\)的内存。

考虑进行了以上优化后，时间复杂度是多少？

\(O(n)\)。顺便一提，空间复杂度也是\(O(n)\)。

Why？

考虑到每个结点只属于一条长链，且每一条长链只会在链顶处被\(O(len)\)暴力合并一次，所以时间复杂度为\(O(n)\)。

空间复杂度的话，我们发现任意一条长链链顶\(top\)处的\(f[top]\)被分配到的内存必然包含了这条长链上所有的结点被分配到的内存（换句话说，对于同一条长链上的两个结点\(x,y\)，如果\(y\)是\(x\)的祖先，那么\(y\)被分配到的内存必然包含\(x\)被分配到的内存），且每一个\(f[top]\)的有效长度均为\(len[top]-1\)，结合之前所述\(n\)个结点的树被划分为了若干条互不相交的长链，空间复杂度\(O(n)\)得证。

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <cctype>

#include <algorithm>

#include <vector>

#define rin(i,a,b) for(int i=(a);i<=(b);i++)

#define rec(i,a,b) for(int i=(a);i>=(b);i--)

#define trav(i,a) for(int i=head[(a)];i;i=e[i].nxt)

using std::cin;

using std::cout;

using std::endl;

typedef long long LL;

inline int read(){

	int x=0;char ch=getchar();

	while(ch<'0'||ch>'9') ch=getchar();

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x;

}

const int MAXN=1000005;

int n;

int ecnt,head[MAXN];

int fa[MAXN],len[MAXN],pc[MAXN];

int ans[MAXN];

int Memory[MAXN],*f[MAXN],*ptr;

struct Edge{

	int to,nxt;

}e[MAXN<<1];

inline void add_edge(int bg,int ed){

	ecnt++;

	e[ecnt].to=ed;

	e[ecnt].nxt=head[bg];

	head[bg]=ecnt;

}

void dfs1(int x,int pre){

	fa[x]=pre;

	int maxlen=-1;

	trav(i,x){

		int ver=e[i].to;

		if(ver==pre) continue;

		dfs1(ver,x);

		if(len[ver]>maxlen){

			maxlen=len[ver];

			pc[x]=ver;

		}

	}

	len[x]=len[pc[x]]+1;

}

void dfs2(int x,int *ff){

	f[x]=ff;

	if(pc[x]){

		dfs2(pc[x],ff+1);

		ans[x]=ans[pc[x]]+1;

		if(ans[x]==1&&f[x][ans[x]]==1) ans[x]--;

	}

	f[x][0]=1;

	trav(i,x){

		int ver=e[i].to;

		if(ver==fa[x]||ver==pc[x]) continue;

		int *temp=ptr;

		ptr+=len[ver];

		dfs2(ver,temp);

		rin(j,0,len[ver]-1){

			f[x][j+1]+=temp[j];

			if(j+1<ans[x]&&f[x][j+1]>=f[x][ans[x]]) ans[x]=j+1;

			if(j+1>ans[x]&&f[x][j+1]>f[x][ans[x]]) ans[x]=j+1;

		}

	}

}

int main(){

	n=read();

	rin(i,2,n){

		int u=read(),v=read();

		add_edge(u,v);

		add_edge(v,u);

	}

	dfs1(1,0);

	ptr=Memory+len[1];

	dfs2(1,Memory);

	rin(i,1,n) printf("%d\n",ans[i]);

	return 0;

}

还有一种使用\(std::vector\)实现的方法，为了快速继承同样使用了指针。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <cctype>

#include <algorithm>

#include <vector>

#define rin(i,a,b) for(int i=(a);i<=(b);i++)

#define rec(i,a,b) for(int i=(a);i>=(b);i--)

#define trav(i,a) for(int i=head[(a)];i;i=e[i].nxt)

using std::cin;

using std::cout;

using std::endl;

typedef long long LL;

inline int read(){

	int x=0;char ch=getchar();

	while(ch<'0'||ch>'9') ch=getchar();

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x;

}

const int MAXN=1000005;

int n;

int ecnt,head[MAXN];

int fa[MAXN],len[MAXN],pc[MAXN];

int ans[MAXN],realans[MAXN];

std::vector<int> *f[MAXN];

struct Edge{

	int to,nxt;

}e[MAXN<<1];

inline void add_edge(int bg,int ed){

	ecnt++;

	e[ecnt].to=ed;

	e[ecnt].nxt=head[bg];

	head[bg]=ecnt;

}

void dfs1(int x,int pre){

	fa[x]=pre;

	int maxlen=-1;

	trav(i,x){

		int ver=e[i].to;

		if(ver==pre) continue;

		dfs1(ver,x);

		if(len[ver]>maxlen){

			maxlen=len[ver];

			pc[x]=ver;

		}

	}

	len[x]=len[pc[x]]+1;

}

void dfs2(int x){

	if(pc[x]){

		dfs2(pc[x]);

		f[x]=f[pc[x]];

		ans[x]=ans[pc[x]];

		if(ans[x]==(int)(*f[x]).size()-1&&(*f[x])[(int)f[x]->size()-1]==1) ans[x]++;

	}

	else{

		f[x]=new std::vector<int>();

	}

	f[x]->push_back(1);

	trav(i,x){

		int ver=e[i].to;

		if(ver==fa[x]||ver==pc[x]) continue;

		dfs2(ver);

		rin(j,0,(int)f[ver]->size()-1){

			int jj=(int)f[x]->size()-((int)f[ver]->size()+1-j);

			(*f[x])[jj]+=(*f[ver])[j];

			if(jj>ans[x]&&(*f[x])[jj]>=(*f[x])[ans[x]]) ans[x]=jj;

			if(jj<ans[x]&&(*f[x])[jj]>(*f[x])[ans[x]]) ans[x]=jj;

		}

	}

	realans[x]=(int)f[x]->size()-ans[x]-1;

}

int main(){

	n=read();

	rin(i,2,n){

		int u=read(),v=read();

		add_edge(u,v);

		add_edge(v,u);

	}

	dfs1(1,0);

	dfs2(1);

	rin(i,1,n) printf("%d\n",realans[i]);

	return 0;

}

长链剖分优化树形DP总结

长链剖分

有什么用？

到底有什么用？

一道例题

题解

代码