长链剖分是树链剖分的一种，平常我们所说的树链剖分一般默认为轻重链剖分。

轻重链剖分有着很优秀的性质：每个结点跳到链顶的次数至多为 O(\log N)。

但轻重链剖分并不是万能的，遇到某些神奇的问题，它就显得无力了。

引入

[CF1009F]Dominant Indices

给定一棵以 1 为根，n 个节点的树。设 d(u,x) 为 u 子树中到 u 距离为 x 的节点数。

对于每个点，求一个最小的 k，使得 d(u,k) 最大。

显然可以设计出一个最暴力的 DP：

设 f(u,x) 表示 u 子树中到 u 距离为 x 的节点数（其实就是为了好听把原题的 d 改成了 f）

状态转移方程：f(u,x)=\sum\limits_{v\in son_u} f(v,x-1)。

这样做显然时空复杂度均为 O(n^2)，考虑优化。

据说可以 dsu on tree 或者线段树合并，但我不会（

有一个比较经典的结论：状态只跟深度有关的问题一般都可以用长链剖分优化。

让我们看看长链剖分是怎么把这道题优化到时空复杂度 O(n) 的。

长链剖分

如果熟悉轻重链剖分，那听到长链剖分的名字应该就知道怎么做了。

在轻重链剖分中，我们以子树最大的子节点为重儿子，重儿子与父节点的连边称为重边，若干条重边连成一条重链。

长链剖分和它很详细，只不过把“子树最大”变为“子树深度最大”。

把 u 的子节点中子树最大的节点称作长儿子，连边即为长边，若干条长边连成一条长链。

代码：

std::vector<int> G[maxn];
void dfs1(int u,int fa) {
    for(auto& v : G[u]) {
        if(v == fa)continue ;
        dfs1(v , u);
        if(d[v] > d[son[u]])son[u] = v;
    }
    d[u] = d[son[u]] + 1;
    return ;
}

它有一些性质：

性质 1：

所有长链的长度和为 O(n) 级别。

证明：每条边只会在一条长链里出现，显然成立。

性质 2：

证明：反证法，如果 y 所在的长链长度小于 k，那么显然 y\to u 的这条链更优秀，与假设矛盾。

性质 3：

任意一点向上跳跃长链的次数至多为 O(\sqrt{N})。

证明：显然，这个节点跳到的长链的长度大于其原来所在的长链长度。

那么在最劣的情况下，长链长度为 1,2,3,4\ldots \sqrt{N}。结论成立。

应用

在线维护节点的 k 次祖先

[模板]树上 k 级祖先

面对这个问题，如果我们使用倍增，那么时间复杂度预处理 O(N\log N)，单次询问 O(\log N)。

如果询问次数特别多的话，倍增就显得乏力了。

不过，在长链剖分优秀性质的优化下，可以结合倍增做到 O(N\log N) 预处理，O(1) 查询。

首先，还是要预处理出每个结点的 2^j 次祖先，并对整棵树进行长链剖分。

对于每条长链，假设链长为 len，我们记录链头向上的 len 个结点和长链里的 len 的节点。

这显然是 O(N) 的时空复杂度。

对于一次询问 k，我们先走到 u 的 j=2^{\lfloor \log_2 k \rfloor} 次祖先，那么剩下的步数即为 k-j。

根据我们上面提到的性质 2，u 的 j 次祖先所在的长链长度显然 \gt j。

那么我们直接根据上面预处理好的信息 O(1) 查询即可。

代码：太懒了还没写

快速合并以深度为下标的子树信息

会发现，上面提到的例题就是一道典型的满足这种特征的题。

我们如何在没有任何其他方法的帮助下紧靠长链剖分解决这道题呢？

首先我们发现，u 所对应的所有状态和它的子节点 v 都只差一位。

我们可不可以在统计 v 的时候直接把 f(v,\dots) 的信息直接存到 f(u,\dots) 里呢？

答案是可以。我们只对长链的顶点申请内存，其它的节点与它共享内存。

具体地，抛弃静态数组，改用动态数组，即为指针：int *f[maxn];。

对于节点 u 和它的长儿子 v，令 f_v=f_u+1，这样就把 f_v 和 f_u 绑定，每次更新 f_v 的时候顺手更新 f_u。

对于 u 其它不是长儿子的子节点，直接暴力合并。

这样做，由于我们只在每条长链的链头进行合并，时空复杂度就是长链的长度之和，即 O(n)。

Code

// Problem: CF1009F Dominant Indices
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1009F
// Memory Limit: 500 MB
// Time Limit: 4500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
const int maxn = 1e6 + 5;
int n,ans[maxn],d[maxn],son[maxn],g[maxn];
int *f[maxn],*now = g;
vector<int> G[maxn];
void dfs1(int u,int fa) {
    for(auto& v : G[u]) {
        if(v == fa)continue ;
        dfs1(v , u);
        if(d[v] > d[son[u]])son[u] = v;
    }
    d[u] = d[son[u]] + 1;
    return ;
}
void dfs2(int u,int fa) {
    f[u][0] = 1;
    if(!son[u])return ;
    f[son[u]] = f[u] + 1;
    dfs2(son[u] , u);
    ans[u] = ans[son[u]] + 1;
    for(auto& v : G[u]) {
        if(v == fa||v == son[u])continue ;
        f[v] = now;
        now += d[v];
        dfs2(v , u);
        for(int i = 1;i <= d[v];++ i) {
            f[u][i] += f[v][i - 1];
            if(f[u][i] > f[u][ans[u]]||(f[u][i] == f[u][ans[u]]&&i < ans[u]))ans[u] = i;
        }
    }
    if(f[u][ans[u]] == 1)ans[u] = 0;
    return ;
}
int main() {
    scanf("%d",&n);
    for(int i = 1;i < n;++ i) {
        int u,v;
        scanf("%d %d",&u,&v);
        G[u].pb(v);
        G[v].pb(u);
    }
    dfs1(1 , 0);
    f[1] = now;
    now += d[1];
    dfs2(1 , 0);
    for(int i = 1;i <= n;++ i)printf("%d\n",ans[i]);
    return 0;
}

这篇文章中仅列出了长链剖分最基本最基本的操作，至于其它的神仙应用我还没有进行了解，以后会在做题过程中慢慢学习。