長鏈剖分

在長鏈剖分中重兒子的定義為：子樹深度最大的兒子。
其余就和重剖一樣了。
下面是核心代碼：

void dfs(int u){
	mxdep[u]=0;  //子樹內最大深度
	for(int i=head[u];i;i=Next[i]){
		int v=to[i];
		if(v==fa[u]) continue;
		fa[v]=u;
		dfs(v);
		if(mxdep[v]>=mxdep[son[u]]) son[u]=v;
	}
	if(son[u]) mxdep[u]=mxdep[son[u]]+1;
}

應用

長鏈剖分的應用很多，但因為我們放在了 DP 優化合集里，所以我們只介紹他如何優化 DP。

要用他優化 DP 我們只需要知道他的一個性質就夠了：所有長鏈的長度之和為 O(n)。

能用長鏈剖分優化的 DP 滿足其中一維 dp 狀態跟深度有關，此時如果我們對每一個點那一維都開一個 \(O(n)\) 的數組，那么空間和時間起碼就是 \(O(n^2)\) 的了。
但其實對于每個點 \(u\) 他那一維的大小實際上只需要開 \(maxdep_u\) 的大小即可，有很多是浪費的。
所以我們借鑒 dsu on tree 的思想，每個點直接繼承重兒子的 dp 數組，然后暴力合并輕兒子的 dp 數組。
此時每一條長鏈只會在鏈頂向其父親轉移時會被暴力合并，所以總復雜度就是所有長鏈的長度之和 \(O(n)\)。

在實現繼承數組這一操作時，我們往往使用指針，在遍歷到鏈頂時提前為整條長鏈開好空間，然后這條長鏈上的點公用這段空間。
根據 dp 轉移的不同可能會需要用不同的寫法。

下面以一道例題來詳細介紹。

例題

幾乎所有介紹長剖優化 DP 的博客（包括 oi-wiki） 都以 CF1009F 作為例題，所以本博客這里不再以他為例題介紹。

[POI2014] HOT-Hotels 加強版

畫個圖容易發現滿足條件的三個點 \((x,y,z)\) 一定滿足兩者之一：

1. 他們的 \(LCA\) 是同一個，且他們距離 \(LCA\) 的距離都為 \(d\)。
2. 他們其中兩個（不妨設為 \(x,y\)）距離他們的 \(LCA\)（下面記為 \(u\)） 距離都為 \(d\)，并且 \(z\) 和 \(u\) 的距離也為 \(d\)。而且 \(LCA(x,z)=LCA(y,z)=lCA(u,z)=v\)，即要保證他們之間的距離為 \(2d\)。

其實第 \(1\) 種情況是第 \(2\) 種情況的特殊情況。

為了避免算重我們把每個三元組算在最高處，比如在第一種情況里就算在 \(LCA\) 處，在第二種情況里就算在 \(v\) 處。
然后進行 dp：
\(f_{i,j}\) 表示和 \(i\) 子樹內和 \(i\) 距離為 \(j\) 的點的個數。
\(g_{i,j}\) 表示 \(i\) 子樹內的點對 \((x,y)\) 滿足 \(LCA(x,y)=lca，dist(x,lca)=dist(y,lca)=d\)，且 \(dist(i,lca)=d-j\) 的 \((x,y)\) 的個數。

轉移考慮樹形背包，假設現在合并進來 \(u\) 的一個子樹 \(v\)：
\(f\) 的轉移是簡單的（和 CF1009F 一樣）：\(f_{u,j+1} += f_{v,j}\)。
對于 \(g\) 的轉移分兩種：

1. 點對來自 \(v\) 子樹內：\(g_{u,j-1} += g_{v,j}\)
2. 點對分別來自前面的子樹和 \(v\) 子樹，此時他們的 \(lca\) 就是 \(u\)：\(g_{u,j+1} += f_{u,j+1}\times f_{v,j}\)。

然后考慮對 \(ans\) 的貢獻：

1. 最后加上 \(g_{u,0}\)：此時 \(u\) 就是那第三個點。
2. 還是考慮在合并進 \(v\) 子樹的時候，此時的貢獻分為 \(v\) 子樹提供單點和 \(v\) 子樹提供點對：\(g_{u,j+1} \times f_{v,j} + f_{u,j-1} \times g_{v,j}\)。

但其實當 \(j=1\) 時，\(f_{u,j-1}\times g_{v,j}\) 就是第 \(1\) 種情況的貢獻。
所以不需要額外把第 \(1\) 種情況算進去。

第二維跟子樹最大深度同階，可以長剖優化成 \(O(n)\)。
要注意的是 \(g\) 數組在繼承重兒子的時候是 \(g_{u,j-1}=g_{son_u,j}\)，而不是像 \(f\) 那樣 \(f_{u,j+1}=f_{son_u,j}\)，所以內存分配的方式有所不同。

code

#include<bits/stdc++.h>
#define int long long  
using namespace std;
const int N=1e5+5;

inline int read(){
	int w=1,s=0;
	char c=getchar();
	for(;c<'0'||c>'9';w*=(c=='-')?-1:1,c=getchar());
	for(;c>='0'&&c<='9';s=s*10+c-'0',c=getchar());
	return w*s;
}
int n,tot,head[N],to[N<<1],Next[N<<1];
void add(int u,int v){
	to[++tot]=v,Next[tot]=head[u],head[u]=tot;
}
int mxdep[N],son[N],fa[N],*f[N],*g[N],ans,tmp1[N<<2],tmp2[N<<2],*id1=tmp1,*id2=tmp2;  //f,g 只是指向內存開頭的指針，tmp1,tmp2 是用來分配內存的數組
void dfs(int u){
	mxdep[u]=0;
	for(int i=head[u];i;i=Next[i]){
		int v=to[i];
		if(v==fa[u]) continue;
		fa[v]=u;
		dfs(v);
		if(mxdep[v]>=mxdep[son[u]]) son[u]=v;
	}
	if(son[u]) mxdep[u]=mxdep[son[u]]+1;
}
void dfs1(int u){
	if(son[u]){
		f[son[u]]=f[u]+1;  // 此時對于 son[u] 來講的 dp 數組的第 i 位，就是對于 u 來講的 dp 數組的第 i+1 位，下同
		g[son[u]]=g[u]-1;
		dfs1(son[u]);
		ans += g[son[u]][1];
	}
	f[u][0]=1;
	for(int i=head[u];i;i=Next[i]){
		int v=to[i];
		if(v==fa[u] || v==son[u]) continue;
		f[v]=id1; id1+=mxdep[v]+1;  //在鏈頂分配內存，對于 f 只需要往后分配 maxdep[v] 的長度即可
		id2+=mxdep[v]; g[v]=id2; id2+=mxdep[v]+1;   //對于 g 不僅需要往后分配還需要往前分配（因為重兒子 dp 數組的開頭在他的開頭前面）
		dfs1(v);
		for(int j=0;j<=mxdep[v];j++) ans += g[u][j+1] * f[v][j] + ((j>0) ? (f[u][j-1] * g[v][j]) : 0); 
		for(int j=0;j<=mxdep[v];j++){
			g[u][j+1]+=f[u][j+1]*f[v][j];
			if(j>0) g[u][j-1]+=g[v][j];
		}
		for(int j=0;j<=mxdep[v];j++) f[u][j+1]+=f[v][j];
	}
}
signed main(){
	n=read();	
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		add(u,v),add(v,u); 
	}
	
	dfs(1);
	f[1]=id1; id1+=mxdep[1]+1;
	id2+=mxdep[1]; g[1]=id2; id2+=mxdep[1]+1; 
	dfs1(1);
	
	printf("%lld\n",ans);
	return 0;
}