长链剖分

长链剖分

顾名思义就是以深度最大的儿子为长儿子做的剖分。

主要思想在于使用指针，使得同一条长链上的 dp 值共用，以达到优化空间复杂度为 \(O(n)\) ，以及优化时间复杂度。但是前提是 dp 状态中有深度这一维。

上一个例题具体分析一下。

CF1009F Dominant Indices

题目大意：给定一棵以 \(1\) 为根的 \(n\) 个节点的树。现在对于每个点，求出一个最小的\(k\) 使得 \(d(u,k)\) 最大。其中 \(d(u,x)\) 表示以 \(u\) 为根的子树中，距离 \(u\) 为 \(x\) 的节点数。

\(1\le n\le 10^6\)

题解

长链剖分板子题。设 \(f[u][i]\) 表示 \(d(u,v)\) 。容易得到转移式：

发现 \(i\) 枚举的范围是要到深度层的，且dp状态中有深度，可以使用长链剖分。

剖分部分和重链剖分是一样的，不多赘述。我们暴力合并轻儿子的dp，然后考虑直接继承长儿子。这个我们用指针为每个长链分配内存，让 \(f[son[u]\ ]\) 指向 \(f[u]+1\) ，也就是 \(u\) 的dp数组上 \(d(u,1)\) 的位置，这样就可以达到 \(O(n)\) 的空间复杂度。

发现我们只是暴力合并了长链，长链的深度和为 \(n\) ，那么时间复杂度也是 \(O(n)\) 的。

参考代码：

#include
#define ll long long
#define db double
#define filein(a) freopen(#a".in","r",stdin)
#define fileot(a) freopen(#a".out","w",stdout)
#define sky fflush(stdout)
#define gc getchar
#define pc putchar
namespace IO{
	template
	inline void read(T &s){
		s=0;char ch=gc();bool f=0;
		while(ch<'0'||'9'
	inline void read(T &s,A &...a){
		read(s);read(a...);
	}
	inline bool blank(char c){
		return c==' ' or c=='\t' or c=='\n' or c=='\r' or c==EOF;
	}
	inline void gs(std::string &s){
		s+='#';char c=gc();
		while(blank(c) ) c=gc();
		while(!blank(c) ){
			s+=c;c=gc();
		}
	}
};
using IO::read;
using IO::gs;
const int N=1e6+3;
int n;
int head[N],nxt[N<<1];
struct Edge{
	int u,v;
}to[N<<1];
int Etot;
inline void link(int u,int v){
	nxt[++Etot]=head[u];
	head[u]=Etot;
	to[Etot]={u,v};
}
inline void _link1(int u,int v){
	link(u,v);link(v,u);
}
int dep[N],son[N];
int buf[N],*dp[N],*now;
void dfs1(int u,int f){
	for(int i=head[u];~i;i=nxt[i]){
		int v=to[i].v;
		if(v==f) continue;
		dfs1(v,u);
		if(dep[v]>dep[son[u] ]){
			son[u]=v;
		}
	}
	dep[u]=dep[son[u] ]+1;
}
int ans[N];
void dfs2(int u,int f){
	dp[u][0]=1;
	if(son[u]){
		dp[son[u] ]=dp[u]+1;
		//其儿子的答案指向其深度为1的答案
		dfs2(son[u],u);
		ans[u]=ans[son[u] ]+1;
	}
	for(int i=head[u];~i;i=nxt[i]){
		int v=to[i].v;
		if(v==f or v==son[u]) continue;
		dp[v]=now;now+=dep[v];
		dfs2(v,u);
		for(int i=1;i<=dep[v];++i){
			dp[u][i]+=dp[v][i-1];
			if(dp[u][i]>dp[u][ans[u] ]){
				ans[u]=i;
			}else if(dp[u][i]==dp[u][ans[u] ] and i