参考资料
例题：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\) 级祖先。
长链剖分优化 DP
例题：CF1009F Dominant Indices。
给定一棵以 \(1\) 作为根的 \(n\) 个点的有根树。
定义 \(d_{x,k}\) 表示 \(x\) 的 \(k\) 级子节点的数量。对于每一个点 \(x\)，求最小的 \(k\) 满足 \(d_{x,k}\) 最大。钦定 \(d_{x,0}=1\)。
设 \(v_x\) 表示 \(x\) 的子节点集，有：
暴力维护会 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\) 的最大值及其下标。
参考代码
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=1e6;
int n,ans[N+1];
vector<int>g[N+1];
struct d{int max,id;vector<int>a;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;
}