半端な生命の関数を / 少々ここらでオーバーライド
内容 & 性质
把重链剖分选的 siz 最大的儿子换成高度最大的儿子就是长剖了。同样具有一些美妙的性质。
任意点到根节点经过的链数最劣为 \(\sqrt n\)。
考虑构造一条经过了 \(\sqrt n+1\) 条链的路径，发现构造不出来。得证。（？）
这点也决定了长剖和重剖走的不是一条赛道，更多的是处理一些和深度有关的场景下的问题。用法有点像 dsu on tree。任意点 \(x\) 的 \(k\) 级祖先 \(fa\) 所在链长 \(\ge k\)。
考虑反证。若 \(fa\) 所在链长度 \(<k\)，则 \(fa\to x\) 更优，矛盾。故原命题成立。
求 k 级祖先
长剖的一个典型应用是 \(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)\)），就可以 \(O(1)\) 访问 \(fa_k\)。
怎么找到 \(fa_r\) 呢？这看似是递归的问题，实际上发现 \(r\) 的取值只需 \(\ge \dfrac k2\)，对于 \(1\sim n\) 的每一个 \(k\)，找到其最高二进制位 \(r\)（显然 \(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]])];
};优化 DP
yly：管它这那的，只要是有关深度直接上长剖就是了。
和 DSU on tree 类似，主要利用每条链只会被算一次实现 \(O(n)\) DP。具体地，尽可能地『继承』长链的信息，『短链』则暴力合并。
值得注意的是，一般『深度』这一维信息会以『与 \(u\) 的距离』的形式，结合指针来维护（因为直接记录深度会更史）。
具体地，用一个全局大数组容纳所有信息，为每个点分配相应的数组头指针。正常情况下需要用到的元素最多为 \(2n\)，但如果存在一些诡异的前移后移操作就另当别论了。
P5904 [POI 2014] HOT-Hotels 加强版
https://www.luogu.com.cn/problem/P5904
首先 不难 得到 \(O(n^2)\) 做法：显然存在一个点到三个点距离相等。这个点既可能是它们的 LCA，也可能是其中一个点的子孙，另外两个点的 LCA。综上，在 LCA 处统计答案是可行的。
令 \(f_{i,j}\) 表示 \(i\) 子树中距离 \(i\) 为 \(j\) 的点数；\(g_{i,j}\) 表示 \(i\) 子树中距离 \(i\) 为 \(j\)、或者距 LCA 为 \(d\) 且 LCA 距离 \(i\) 为 \(d-j\) 的点对数；随便做就可以了。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n;
std::cin >> n;
std::vector<std::vector<int> > g1(n + 1);
for (int i = 1, x, y; i < n; ++i) {
std::cin >> x >> y;
g1[x].push_back(y), g1[y].push_back(x);
}
auto res(0ll);
std::vector<int> h(n + 1);
std::vector<std::vector<long long> > f(n + 1), g(n + 1);
std::function<void(int, int)> DFS = [&](int x, int fa) {
h[x] = 1;
for (auto i : g1[x])
if (i != fa) {
DFS(i, x);
h[x] = std::max(h[x], h[i] + 1);
}
f[x].resize(h[x] + 1), g[x].resize(h[x] + 1);
f[x][0] = 1ll;
for (auto i : g1[x])
if (i != fa) {
for (int j = 0; j <= h[i]; ++j) {
if (j >= 1)
res += g[x][j] * f[i][j - 1];
if (j >= 1 && j + 1 <= h[i])
res += f[x][j] * g[i][j + 1];
if (j >= 1) {
g[x][j] += f[x][j] * f[i][j - 1];
f[x][j] += f[i][j - 1];
}
if (j + 1 <= h[i])
g[x][j] += g[i][j + 1];
}
std::vector<long long>().swap(f[i]);
std::vector<long long>().swap(g[i]);
}
res += g[x][0];
return;
};
DFS(1, -1);
std::cout << res << '\n';
return 0;
}然后对于每个 \(u\)，类似 DSU on tree，继承其长儿子的数据（整体前移 / 后移一位，使用指针实现），再把短儿子暴力合并上来。
每次合并短儿子，数组长为短儿子链长；\(u\) 向上合并时，数组长为长儿子链长。故所有链被合并恰好一次，复杂度 \(O(n)\)。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n;
std::cin >> n;
std::vector<std::vector<int> > g1(n + 1);
for (int i = 1, x, y; i < n; ++i) {
std::cin >> x >> y;
g1[x].push_back(y), g1[y].push_back(x);
}
std::vector<int> h(n + 1), son(n + 1);
std::vector<long long> df(5 * n + 1), dg(5 * n + 1);
std::function<void(int, int)> DFS = [&](int x, int fa) {
h[x] = 1;
for (auto i : g1[x])
if (i != fa) {
DFS(i, x);
h[x] = std::max(h[x], h[i] + 1);
if (h[i] > h[son[x]])
son[x] = i;
}
return;
};
DFS(1, -1);
auto pos(dg.begin() + 3 * n);
std::vector<decltype(df.begin())> f(n + 1), g(n + 1);
auto res(0ll);
DFS = [&](int x, int fa) {
f[x][0] = 1ll;
if (son[x]) {
f[son[x]] = std::next(f[x]), g[son[x]] = std::prev(g[x]);
DFS(son[x], x);
}
for (auto i : g1[x])
if (i != fa && i != son[x]) {
f[i] = std::next(f[x], h[x] + 1);
std::fill(f[i], f[i] + h[i] + 2, 0ll);
g[i] = std::next(pos, h[i]), pos = std::next(g[i], h[i]);
std::fill(std::prev(g[i]), g[i] + h[i] + 2, 0ll);
DFS(i, x);
for (int j = 0; j <= h[i]; ++j) {
if (j >= 1)
res += g[x][j] * f[i][j - 1];
if (j >= 1 && j + 1 <= h[i])
res += f[x][j] * g[i][j + 1];
if (j >= 1) {
g[x][j] += f[x][j] * f[i][j - 1];
f[x][j] += f[i][j - 1];
}
if (j + 1 <= h[i])
g[x][j] += g[i][j + 1];
}
}
res += g[x][0];
return;
};
f[1] = df.begin(), g[1] = dg.begin() + 2 * n;
DFS(1, -1);
std::cout << res << '\n';
return 0;
}CF1585G Poachers
https://codeforces.com/problemset/problem/1585/G
公平博弈。我们现在要算每个根的 SG 值。设 \(f_{u,j}\) 表示在点 \(u\)，删了距离它为 \(j\) 这一层的 SG 值，那么有：
\[ f_{u,j}= \begin{cases} \text{mex}\{f_{v,0}\}&j=0\\ \bigoplus f_{v,j-1}&\text{otherwise} \end{cases} \]
然后发现有深度维。大力长剖。
#include <bits/stdc++.h>
const int inf = 0x3f3f3f3f;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int T;
for (std::cin >> T; T--; ) {
int n;
std::cin >> n;
std::vector<int> rt;
std::vector<std::vector<int> > g(n + 1);
for (int i = 1, x; i <= n; ++i) {
std::cin >> x;
if (x)
g[x].push_back(i);
else
rt.push_back(i);
}
std::vector<int> h(n + 1), son(n + 1), to(n + 1, inf);
std::function<void(int)> DFS = [&](int x) {
h[x] = 1;
for (auto i : g[x]) {
DFS(i);
h[x] = std::max(h[x], h[i] + 1);
to[x] = std::min(to[x], to[i] + 1);
if (h[i] > h[son[x]])
son[x] = i;
}
to[x] = std::min(to[x], h[x]);
return;
};
for (auto i : rt)
DFS(i);
std::vector<int> _f(5 * n + 1), top(n + 1);
std::vector<decltype(_f.begin())> f(n + 1);
std::vector<std::unordered_set<int> > s(n + 1);
auto p(_f.begin());
DFS = [&](int x) {
if (son[x]) {
f[son[x]] = std::next(f[x]);
top[son[x]] = top[x], DFS(son[x]);
}
if ((int)g[x].size() == 1) {
s[top[x]].insert(f[son[x]][0]);
for (int now = f[son[x]][0] + 1; ; ++now)
if (!s[top[x]].count(now)) {
f[x][0] = now;
break;
}
return;
}
for (auto i : g[x])
if (i != son[x]) {
f[i] = p, p = std::next(p, h[i] + 1);
top[i] = i, DFS(i);
for (int j = 1; j <= to[i] + 1; ++j)
f[x][j] ^= f[i][j - 1];
}
std::unordered_set<int>().swap(s[top[x]]);
for (int j = 1; j <= to[x]; ++j)
s[top[x]].insert(f[x][j]);
for (int now = 0; ; ++now)
if (!s[top[x]].count(now)) {
f[x][0] = now;
break;
}
return;
};
int res = 0;
for (auto i : rt) {
f[i] = p, p = std::next(p, h[i] + 1);
DFS(i), res ^= f[i][0];
}
std::cout << (res ? "YES" : "NO") << '\n';
}
return 0;
}