参考资料
例题：P5903 树上 $k$ 级祖先。
例题：CF1009F Dominant Indices。
因为当时写树链剖分详解（重链剖分）时并不会长链剖分，所以只能另开一文了。
「长链剖分」，除「重链剖分」外的另一种树剖方式，与深度相关。
长链剖分
定义「重子节点」表示子树深度最大的子节点，「轻子节点」表示剩余子节点。其余定义同「重链剖分」的定义。（但是也有人称之为「长子节点」和「短子节点」）
长链剖分可以容易地类似于重链剖分实现，只需要在寻找重子节点时稍作修改即可。
性质
没什么用的性质。
从任意节点出发往上跳，跳轻边的次数为 $\mathcal O\left(\sqrt n\right)$。也就是说，长链数量为 $\mathcal O\left(\sqrt n\right)$。
也就是说，使用长链剖分可以得到一个单次操作复杂度 $\mathcal O\left(\sqrt n\log n\right)$ 的算法。
但是长链剖分的实际应用并不是代替重链剖分，而是维护一些与「深度」相关的信息。
简单应用
给定一棵树，确定每一个点 $x$ 的子树内各深度的子节点数量。要求时间复杂度为线性。（重链剖分配合 DSU on tree可以做到 $\mathcal O(n\log n)$）
维护信息与深度正相关，点 $x$ 的信息量为 $\mathcal O(\textit{depth}_x)$，考虑长链剖分。
点 $x$ 可以 $\mathcal O(1)$ 继承重子节点的信息，其余轻子节点 $i$ 以 $\mathcal O(\textit{depth}_i)$ 的代价暴力继承信息即可。
此时时间复杂度为 $\mathcal O(n)$。因为每一条长链都只会被统计一次。
维护诸如此类的深度相关信息，均可以类似地做到 $\mathcal O(n)$。
长链剖分求解树上 $k$ 级祖先
例题：P5903 树上 $k$ 级祖先。
给定一棵 $n$ 个点的有根树，$q$ 次询问，每次询问点 $x$ 的 $k$ 级祖先。
树上 $k$ 级祖先可以通过倍增做到 $\mathcal O(\log n)$ 查询，通过重链剖分配合预处理做到 $\mathcal O(\log\log n)$，重链剖分配合分块做到 $\mathcal O\left(\sqrt{\log n}\right)$。
但是长链剖分可以做到 $\mathcal O(n\log n)$ 预处理，$\mathcal O(1)$ 查询。
首先可以倍增预处理节点的 $2^i$ 级祖先。
求 $x$ 的 $k$ 级祖先，找到一个 $2^i\leq k<2^{i+1}$，跳到 $x$ 的 $2^i$ 级祖先，令 $k\leftarrow k-2^i$。
根据长链剖分的性质，此时有 $x$ 所在链的长度大于等于 $2^i$，进而大于等于 $k$。因此可以预处理链顶节点的 $l$ 级祖先和 $l$ 级重子节点，$l$ 表示链的长度。在预处理出来的结果上查询即可。
证明
注意到：如果 $x$ 所在链链顶节点 $\textit{top}_x$ 的父节点 $y$ 所在链长度一定大于 $x$ 所在链长度。
否则，$x,y$ 将会处于同一条链中。
若 $x$ 的 $k$ 级祖先处于同一条链中，正确性显然。
否则若处于链顶节点的父节点所处链中，则必然 $k$ 被划分为了两部分。父节点所处链的长度大于当前链长度，因此正确。
可以推广到跳了任意条。
注意特判 $k=0$。
参考代码
```cpp
//#include<bits/stdc++.h>
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
constexpr const int N=5e5;
namespace judge{
#define ui unsigned int
ui s;
inline ui get(ui x) {
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
return s = x;
}
#undef ui
}
int n,root,depth[N+1],father[N+1][__lg(N+1)+1];
vectorg[N+1];
namespace hld{
int son[N+1],maxDepth[N+1],top[N+1],len[N+1];
void dfs1(int x){
depth[x]=depth[father[x][0]]+1;
maxDepth[x]=depth[x];
for(int i:g[x]){
if(i==father[x][0]){
continue;
}
dfs1(i);
maxDepth[x]=max(maxDepth[x],maxDepth[i]);
if(maxDepth[i]>maxDepth[son[x]]){
son[x]=i;
}
}
}
vectorup[N+1],down[N+1];
void dfs2(int x,int topx){
top[x]=topx;
if(son[x]){
dfs2(son[x],topx);
}
for(int i:g[x]){
if(i==father[x][0]||i==son[x]){
continue;
}
dfs2(i,i);
}
if(x==topx){
for(int y=x;son[y];y=son[y]){
down[x].push_back(y);
}
for(int i=1,y=x;i<=down[x].size();i++,y=father[y][0]){
up[x].push_back(y);
}
}
}
void pre(){
dfs1(root);
dfs2(root,root);
for(int i=1;(1<<i)<=n;i++){
for(int x=1;x<=n;x++){
father[x][i]=father[father[x][i-1]][i-1];
}
}
}
int query(int x,int k){
if(!k){
return x;
}
x=father[x][__lg(k)];
k-=1<<__lg(k);
k-=depth[x]-depth[top[x]];
x=top[x];
if(k>=0){
return up[x][k];
}else{
return down[x][-k];
}
}
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int q;
cin>>n>>q>>judge::s;
for(int i=1;i<=n;i++){
cin>>father[i][0];
if(!father[i][0]){
root=i;
}else{
g[father[i][0]].push_back(i);
}
}
hld::pre();
ll ans=0,last=0;
for(int i=1;i<=q;i++){
int x=(judge::get(judge::s)^last)%n+1;
int k=(judge::get(judge::s)^last)%depth[x];
last=hld::query(x,k);
ans^=1ll*i*last;
}
cout<<ans<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
```
</details>
## 长链剖分优化 DP
> 例题：[CF1009F Dominant Indices](https://www.luogu.com.cn/problem/CF1009F)。
>
> ***
>
> 给定一棵以 $1$ 作为根的 $n$ 个点的有根树。
>
> 定义 $d_{x,k}$ 表示 $x$ 的 $k$ 级子节点的数量。对于每一个点 $x$，求最小的 $k$ 满足 $d_{x,k}$ 最大。钦定 $d_{x,0}=1$。
设 $v_x$ 表示 $x$ 的子节点集，有：
$$
d_{x,k}=\sum_{i\in v_x}d_{x,k-1}
$$
暴力维护会 TLE 并且 MLE。注意到 DP 是与深度相关的，考虑长链剖分。
考虑如何 $\mathcal O(1)$ 继承重子节点信息。可以采用指针。具体而言，将 $x$ 的重子节点 $\textit{son}_x$ 的信息 $d_{\textit{son}_x,0},d_{\textit{son}_x,1},\cdots,d_{\textit{son}_x,k}$ 直接**映射**到 $d_{x,1},d_{x,2},\cdots,d_{x,k+1}$ 上即可。
这样，每一条长链对应一组存储的 $d$，总空间复杂度为 $\mathcal O(n)$。时间复杂度也为 $\mathcal O(n)$。
同时需要时刻维护当前序列 $d$ 的最大值及其下标。
参考代码
```cpp
//#include<bits/stdc++.h>
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
constexpr const int N=1e6;
int n,ans[N+1];
vectorg[N+1];
struct d{
int max,id;
vectora;
d(){
max=1;
id=0;
}
int size(){
return a.size();
}
void resize(int x){
a.resize(x);
}
int& operator [](int x){
return a[x];
}
}d[N+1];
namespace hld{
int depth[N+1],maxDepth[N+1],son[N+1];
void dfs1(int x,int fx){
depth[x]=depth[fx]+1;
maxDepth[x]=depth[x];
for(int i:g[x]){
if(i==fx){
continue;
}
dfs1(i,x);
maxDepth[x]=max(maxDepth[x],maxDepth[i]);
if(maxDepth[i]>maxDepth[son[x]]){
son[x]=i;
}
}
}
int cnt;
void dfs2(int x,int fx,int id,int pre){
if(d[id].size()<pre+1){
d[id].resize(pre+1);
}
d[id][pre]=1;
if(son[x]){
dfs2(son[x],x,id,pre+1);
}
for(int i:g[x]){
if(i==son[x]||i==fx){
continue;
}
int id2=++cnt;
dfs2(i,x,id2,0);
if(d[id].size()<pre+1+d[id2].size()){
d[id].resize(pre+1+d[id2].size());
}
for(int j=0;j<d[id2].size();j++){
d[id][pre+1+j]+=d[id2][j];
if(d[id][pre+1+j]>d[id].max){
d[id].max=d[id][pre+1+j];
d[id].id=pre+1+j;
}else if(d[id][pre+1+j]==d[id].max){
d[id].id=min(d[id].id,pre+1+j);
}
}
}
ans[x]=max(d[id].id-pre,0);//若小于 0，则说明为 pre。
}
int main(){
dfs1(1,0);
cnt=1;
dfs2(1,0,1,0);
return 0;
}
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
hld::main();
for(int i=1;i<=n;i++){
cout<<ans[i]<<'\n';
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
```
</details>
