长链剖分是一种将树剖分成若干条链的方法。
重链剖分选择子树大小最大的点作为重儿子点；而长链剖分每次挑选子树深度最大的点作为重儿子点。
算法概述
其实和重链剖分差不多，无非选择重儿子的标准变成了子树深度最大的点。
重链剖分的一些概念也可以直接搬到长链剖分上来：
- 一个点到其重儿子的边称为重边。
- 一个点到其轻儿子的边称为轻边。
- 重儿子相连形成的链称为长链。
性质
长链剖分后，一个点到根节点的路径上，最多经过 \(O(\sqrt n)\) 条轻边。
所以这个东西和重链剖分相比，有什么特别的作用呢？
一个非常经典的应用就是求树上一个点的 \(k\) 级祖先。
树上 k 级祖先
树上一个点的 \(k\) 级祖先可以采用传统的倍增方法求，时间复杂度 \(O(n \log n)-O(\log n)\)。
当然也可以直接重链剖分后，不停在重链上跳，时间复杂度 \(O(n)-O(\log n)\)。
有没有更快的方法呢？
我们对整棵树进行长链剖分，顺带完成以下预处理：
- 倍增求出每个点的 \(2^i\) 级祖先。
- 对于每条重链的链顶节点，设其所在的重链长度为 \(l\)，求出这个点向上的 \(l\) 个祖先和向下的 \(l\) 个儿子。
剖分后，容易发现点 \(u\) 的 \(k\) 级祖先所在的重链长度一定不小于 \(k\)（否则重链可以直接选择经过点 \(u\)，长度还变长了）。
令 \(x=\left \lfloor \log k \right \rfloor\)，我们先跳 \(2^x\) 级。
跳完之后我们还需要再跳 \(k-2^x\) 级（如果是负数的话意味着我们要往下跳，否则还是往上跳）。而这部分在预处理的时候已经求出来了，因此直接利用预处理的信息就可以了。
时间复杂度 \(O(n \log n)-O(1)\)。
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
typedef unsigned ui;
struct gen
{
ui s;
void init(ui seed)
{
s=seed;
}
ui next()
{
ui x=s;
x^=x<<13;
x^=x>>17;
x^=x<<5;
return s=x;
}
}g;
int fa[5000005][25],dep[5000005],maxd[5000005],son[5000005],top[5000005];
vector<int> up[5000005],down[5000005];
vector<int> e[5000005];
void dfs1(int u,int f)
{
dep[u]=maxd[u]=dep[f]+1;
fa[u][0]=f;
for(int k=1;k<=23;k++)
fa[u][k]=fa[fa[u][k-1]][k-1];
for(auto v:e[u])
{
dfs1(v,u);
if(maxd[v]>maxd[son[u]])
son[u]=v,maxd[u]=maxd[v];
}
}
void dfs2(int u,int t)
{
top[u]=t;
if(u==t)
{
for(int i=0,p=u;i<=maxd[u]-dep[u];i++,p=fa[p][0])
up[u].push_back(p);
for(int i=0,p=u;i<=maxd[u]-dep[u];i++,p=son[p])
down[u].push_back(p);
}
if(son[u])dfs2(son[u],t);
for(auto v:e[u])
if(v!=son[u])dfs2(v,v);
}
int get_kth(int x,int k)
{
if(!k)return x;
int t=log2(k);
k-=1<<t,x=fa[x][t];
k-=dep[x]-dep[top[x]],x=top[x];
if(k>=0)return up[x][k];
else return down[x][-k];
}
int main()
{
int n,q,root;
ui s;
cin>>n>>q>>s;
g.init(s);
for(int i=1;i<=n;i++)
{
int f;
cin>>f;
if(f==0)root=i;
else e[f].push_back(i);
}
dfs1(root,0);
dfs2(root,root);
long long ans=0,lastans=0;
for(int i=1;i<=q;i++)
{
int x=(g.next()^lastans)%n+1,k=(g.next()^lastans)%dep[x];
ans^=(i*(lastans=get_kth(x,k)));
}
cout<<ans<<endl;
return 0;
}
长链剖分优化 DP
这个采用了启发式合并的思想。大概思路是对于一个点，先求出其所在重链的信息，随后将其他链的信息合并到这条重链上。
CF1009F 就是一道不错的例题。
题意是给一棵树，对于每个点 \(u\) 求出一个最小深度 \(d\)，使得 \(u\) 的 \(d\) 级子节点最多。
一道非常不错的长链剖分练手题。
首先是常规的 DP：设 \(f_{i,j}\) 表示点 \(i\) 的 \(j\) 级子节点的数量。
转移方程很显然（其中 \(v\) 是 \(i\) 的子节点）：
$$f_{i,j}=\sum f_{v,j-1}$$
边界是 \(f_{i,0}=1\)。
这样做的时间复杂度是 \(O(n^2)\) 的，需要优化。
这时候长链剖分就登场了（实际上是树上启发式合并的思路）。
我们对于一个节点，先遍历它的重儿子，将重儿子的结果合并（说是合并，其实直接继承了重儿子的结果，并添加了当前点的信息）到当前点上。
接下来我们遍历这个点的其他轻儿子，将这些轻儿子的结果并到当前节点上。
每条重链都只合并了一次，故时间复杂度为 \(O(n)\)。
题解区似乎没有非指针版的实现？其实用 vector 也是可以搞的。
思路仍然是用 vector 存下每个点的信息。不过有几个特殊之处：
- 按深度递增的顺序存储的话，因为合并重儿子信息时要在开头插入元素，效率低下。所以考虑按深度递减的顺序存储信息。
- 合并重儿子信息的时候，直接用 swap 交换而不是复制，在时间和空间上都更优（swap 交换 vector 的时间复杂度是 \(O(1)\) 的）。
#include <cstdio>
#include <vector>
using namespace std;
vector<int> e[1000005],f[1000005];
int fa[1000005],len[1000005],son[1000005];
int ans[1000005];
void dfs1(int u,int f)
{
fa[u]=f;
for(auto v:e[u])
if(v!=f)
{
dfs1(v,u);
if(len[v]>=len[son[u]])
son[u]=v,len[u]=len[v]+1;
}
}
void dfs2(int u)
{
if(son[u])
{
dfs2(son[u]);
swap(f[u],f[son[u]]);//直接交换，降低时间空间开销
f[u].push_back(1);//尾部插入深度为零的结果
ans[u]=ans[son[u]];
if(f[u][ans[u]]==1)ans[u]=len[u];
for(auto v:e[u])
{
if(v==fa[u]||v==son[u])continue;
dfs2(v);
for(int i=len[v];i>=0;i--)
{
int tmp=i+len[u]-len[v]-1;
f[u][tmp]+=f[v][i];
if(f[u][tmp]>f[u][ans[u]]||(f[u][tmp]==f[u][ans[u]]&&tmp>ans[u]))
ans[u]=tmp;//这里存储的是最优解在数组对应的位置，结果需要倒过来
}
}
}
else
{
f[u].push_back(1);
ans[u]=0;
}
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
}
dfs1(1,0);
dfs2(1);
for(int i=1;i<=n;i++)
printf("%d\n",len[i]-ans[i]);
return 0;
}