半端な生命の関数を / 少々ここらでオーバーライド / …したい所だけど現実は / そうそう上手くはいかないようで
把重链剖分选的 siz 最大的儿子换成高度最大的儿子就是长剖了。同样具有一些美妙的性质。
任意点到根节点经过的链数最劣为 \(\sqrt n\)。
就、挺显然的，考虑构造一条经过了 \(\sqrt n+1\) 条链的路径，会发现无论如何都构造不出来。
这点也决定了长剖和重剖走的不是一条赛道，更多的应该是处理一些和深度有关的神秘场景下的问题？有的博客说可以解决一些子树问题（类似于 dsu on tree 那样的）？（存疑）
任意点 \(x\) 的 \(k\) 级祖先 \(fa\) 所在链长 \(\ge k\)。
考虑反证。若 \(fa\) 所在链长度 \(<k\)，则 \(fa\to x\) 更优，矛盾。故原命题成立。
长剖的一个典型应用是 \(O(n\log n)-O(1)\) 求 \(k\) 级祖先。先考虑相对暴力的做法，可以 \(O(n\sqrt n)\) 预处理每个点的 \(1\sim \sqrt n\) 级祖先然后块间块内随便跳一跳就是 \(O(\sqrt n)\) 的单次查询了。
把这个暴力结合「任意点 \(k\) 级祖先所在链长 \(\ge k\)」的性质，有一个很神奇（疯癫）的做法：令 \(r=\dfrac k2\)，那么有 \(x\) 的 \(r\) 级祖先所在链长 \(\ge r\)，假设我们现在已经知道 \(r\) 级祖先 \(fa_r\)，预处理出链内点序列、链顶向上的链长个祖先（这个摊出来是 \(O(n)\) 的），就可以直接 \(\mathcal O(1)\) 访问到 \(fa_k\)。
那么问题来了，怎么找到 \(fa_r\) 呢？这看似是个递归的问题，实际上我们发现 \(r\) 的取值只需要 \(\ge \dfrac k2\) 即可，所以又有一个很神奇（疯癫）的做法，我们对于 \(1\sim n\) 的每一个 \(k\)，找到其最高二进制位 \(r\)（显然对于所有 \(k\)，不同 \(r\) 的个数为 \(\log n\)），对于每个点，预处理出其 \(\log n\) 个不同的 \(r\) 级祖先。显然这个就是我们很熟悉的倍增了。
for (int i = 1, mx = 0; i <= n; ++i) {
if (i >= (1 << mx) * 2)
++mx;
to[i] = mx;
}
std::vector<std::array<int, 21> > fa(n + 1);
std::vector<int> h(n + 1, 1), son(n + 1), dep(n + 1);
h[0] = 0;
std::function<void(int)> DFS = [&](int x) {
for (auto i : g[x])
if (i != fa[x][0]) {
fa[i][0] = x;
for (int j = 1; j <= 20; ++j)
fa[i][j] = fa[fa[i][j - 1]][j - 1];
dep[i] = dep[x] + 1;
DFS(i);
if (h[i] >= h[son[x]])
son[x] = i, h[x] = h[i] + 1;
}
return;
};
dep[1] = 1, DFS(1);
std::vector<int> top(n + 1), id(n + 1);
std::vector<std::vector<int> > anc(n + 1), des(n + 1, std::vector<int> (1));
std::function<void(int, int)> DFS1 = [&](int x, int toq) {
top[x] = toq;
if (son[x])
DFS1(son[x], toq);
for (auto i : g[x])
if (i != fa[x][0] && i != son[x])
DFS1(i, i);
des[toq].push_back(x);
id[x] = (int)des[toq].size() - 1;
if (x == toq) {
anc[x].push_back(x);
for (int j = 1, now = x; j <= id[x]; ++j, now = fa[now][0])
anc[x].push_back(fa[now][0]);
}
return;
};
DFS1(1, 1);
auto ask = [&](int x, int k) {
int x1 = x;
if (!k)
return x;
x = fa[x][to[k]];
if (dep[x] - dep[top[x]] >= k - (1 << to[k]))
return des[top[x]][id[x] + k - (1 << to[k])];
return anc[top[x]][k - (1 << to[k]) - (dep[x] - dep[top[x]])];
};