半端な生命の関数を / 少々ここらでオーバーライド / …したい所だけど現実は / そうそう上手くはいかないようで
把重链剖分选的 siz 最大的儿子换成高度最大的儿子就是长剖了。同样具有一些美妙的性质。
任意点到根节点经过的链数最劣为 √n。
就、挺显然的，考虑构造一条经过了 √n+1 条链的路径，会发现无论如何都构造不出来。
这点也决定了长剖和重剖走的不是一条赛道，更多的应该是处理一些和深度有关的神秘场景下的问题？有的博客说可以解决一些子树问题（类似于 dsu on tree 那样的）？（存疑）任意点 x 的 k 级祖先 fa 所在链长 ≥k。
考虑反证。若 fa 所在链长度 <k，则 fa→x 更优，矛盾。故原命题成立。
长剖的一个典型应用是 O(nlogn)−O(1) 求 k 级祖先。先考虑相对暴力的做法，可以 O(n√n) 预处理每个点的 1∼√n 级祖先然后块间块内随便跳一跳就是 O(√n) 的单次查询了。
把这个暴力结合「任意点 k 级祖先所在链长 ≥k」的性质，有一个很神奇（疯癫）的做法：令 r=k2，那么有 x 的 r 级祖先所在链长 ≥r，假设我们现在已经知道 r 级祖先 far，预处理出链内点序列、链顶向上的链长个祖先（这个摊出来是 O(n) 的），就可以直接 O(1) 访问到 fak。
那么问题来了，怎么找到 far 呢？这看似是个递归的问题，实际上我们发现 r 的取值只需要 ≥k2 即可，所以又有一个很神奇（疯癫）的做法，我们对于 1∼n 的每一个 k，找到其最高二进制位 r（显然对于所有 k，不同 r 的个数为 logn），对于每个点，预处理出其 logn 个不同的 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]])];
};