长链剖分

一种不同于重链剖分的剖分方法，就是选子树里链最长的作为重儿子。性质1：长链总和为\(n\)。性质2:从一个节点到根节点的轻边个数不超过\(\sqrt{n}\)。原因，因为是长链，所以从轻边跳上去所在的长链的长度一定比现在这个大，\(1+2+3+4\dots\)，所以是\(\sqrt{n}\)个。

应用：长链剖分优化\(dp\)。核心思想是把重儿子的信息\(O(1)\)给父亲，然后暴力合并轻儿子。复杂度呢？因为一般合并轻儿子是链长，而轻儿子就是一个长链的顶点，并且一个轻儿子只会被暴力合并一次，所以就是\(O(n)\)的复杂度。至于重儿子的信息，这里使用指针做。使用已到例题来说明：CF1009F Dominant Indices。暴力就是 \(f_{i,j}=\sum_{v\in son(i)}f_{v,j-1}\)。但是时间和空间都是\(O(n^2)\)的。所以长剖。设一个\(dp\)数组，表示在所有转移过程中所用的内存都在这里面。然后设\(*f[N],*now\)分别表示\(f_u\)对应\(dp\)数组中的内存的内阁位置，\(now\)表示现在已经用到了多少的内存。为了让我们重儿子可以\(O(1)\)转移，我们期望一条长链上的点对应的内存都在一个连续段里面，所以在遇到一个长链端点的时候我们给他后面开出大小为长链长度的内存。这样，我们只需要让\(f_{hson[u]}=f_{u}+1\)就可以把重儿子\(O(1)\)给父亲了。

代码如下：

int dp[N], dep[N], hson[N], ans[N];
int *f[N], *now;
void dfs2(int u, int fa) {
    f[u][0] = 1;
    if(hson[u]) {
        f[hson[u]] = f[u] + 1;
        dfs2(hson[u], u);
        ans[u] = ans[hson[u]] + 1;
        if(f[u][ans[u]] == 1) ans[u] = min(0, ans[u]);
    }
    for(int i = head[u]; i; i = edge[i].nxt) {
        int v = edge[i].to;
        if(v == fa || v == hson[u]) continue;
        f[v] = now;// 把他指向起点
        now += dep[v];// 多开内存
        dfs2(v, u);
        for(int j = 0; j < dep[v]; j ++) {
            f[u][j + 1] += f[v][j];// *(f[u]+j+1)与f[u][j+1]是等价的，所以能这么访问。
            if(f[u][ans[u]] < f[u][j + 1]) ans[u] = j + 1;
            else if(f[u][ans[u]] == f[u][j + 1]) ans[u] = min(ans[u], j + 1);
        }
    }
}

这样空间复杂度和时间复杂度都降到\(O(n)\)了。

一般长剖的题，状态中都会有一维是深度。

P5904 [POI 2014] HOT-Hotels 加强版
这个也是。