树上启发式合并学习笔记
最近几天了解到一个很神奇的算法——dsu on tree，看上去没多快实际上很快，这叫低调。
好久不更了，至于反演，5 月再更吧，4 月的最后一天分享一下 dsu on tree。顺便闲话一句，4/26 是我生日，也是历史二模。
重链剖分 dsu on tree
这类 dsu on tree 适用于多次询问，每次询问需要 $O(子树大小)$ 的时间，这时用重链剖分 dsu on tree 可以优化到 $O(q\log n)$
例题1：
CF600E，典中典了。
给一棵以 $1$ 为根的树，每个点都有一个颜色，求出以每个点为根的子树中主导颜色的编号之和。
所谓主导颜色，就是出现次数最多的颜色，可能有多个。
考虑一个朴素的做法：
开一个桶存储每个颜色的出现次数，按照 DFS 序遍历，遍历到一个点时，依次统计子结点的答案，统计完一个就把桶清空。
接着再把它子结点的颜色加到桶里，顺便处理出以当前节点为子树的主导颜色。
这样的做法为 $O(n\times n)$，超时。
但是可以优化，我们定义一个非叶子节点的重儿子是 $size$ 最大的儿子，轻儿子是除了重儿子外的儿子。
对于一个节点 $x$，最后一个儿子算完之后是不用清空桶的，它可以直接记录到以 $x$ 为根的子树的答案中，剩下的依旧是暴力。
显然把最后一个儿子设为重儿子最优了，优化成了 $O(n\log n)$。
下面来证明一下，每个节点被统计的次数为它上面的轻边数量（如果是重边，统计完就会给它的父亲了）。
每经过一个轻边，它的兄弟中就一定有一个 size 比它大的。
所以经过后子树的 $size$ 至少翻倍，$\log n$ 次 到达根，每个节点被统计 $\log n$ 次，$n$ 个就被统计 $n\log n$ 次了，证毕。
注意：清空桶时，如果全清空还是超时，所以只需要清空用过的就行了。
这里使用 $map$，虽然时间复杂度会多一个 $\log$，但是一句 m.clear() 就行了还很快。
代码（$n\log^2 n$ 的）：
#include <map> #include <vector> #include <iostream> #define int long long using namespace std; int n, ma, res; int fa[100005], sz[100005], wson[100005]; int c[100005], ans[100005]; vector <int> v[100005]; map <int, int> m, b; int dfs1 (int x) { for (int i = 0; i < v[x].size (); i ++) if (v[x][i] != fa[x]) { fa[v[x][i] ] = x; int tmp = dfs1 (v[x][i]); sz[x] += tmp; if (sz[wson[x] ] < tmp) wson[x] = v[x][i]; } return ++ sz[x]; } void add (int x) { m[x] ++; if (m[x] > ma) { ma = m[x]; res = x; } else if (m[x] == ma) res += x; } void dfs2 (int x) { add (c[x]); for (int i = 0; i < v[x].size (); i ++) if (v[x][i] != fa[x]) dfs2 (v[x][i]); } void dfs_ans (int x) { for (int i = 0; i < v[x].size (); i ++) { if (v[x][i] != fa[x] && v[x][i] != wson[x]) { dfs_ans (v[x][i]); m.clear (); res = ma = 0; } } if (wson[x] != 0) dfs_ans (wson[x]); add (c[x]); for (int i = 0; i < v[x].size (); i ++) if (v[x][i] != fa[x] && v[x][i] != wson[x]) dfs2 (v[x][i]); ans[x] = res; } signed main () { int x, y; scanf ("%lld", &n); for (int i = 1; i <= n; i ++) cin >> c[i]; for (int i = 1; i < n; i ++) { scanf ("%lld%lld", &x, &y); v[x].push_back (y); v[y].push_back (x); } dfs1 (1); dfs_ans (1); for (int i = 1; i <= n; i ++) printf ("%lld ", ans[i]); return 0; }
例题2：
CF375D
关于询问，我们用一个 vector<pair<int, int> > v[100005] 来记录，v[i] 存的是询问中的第一个参数为 i 的。
pair 的第一个是 $k$，第二个是询问编号，每遍历到一个点，处理完信息后，访问 v[x] 并把询问搞掉。
对于这题，可以用一个桶和一个 $BIT$ 来维护。
桶维护的是颜色出现的次数，$BIT$ 维护的是颜色出现次数的出现次数。
先来考虑询问，假设当前的桶和 $BIT$ 已经维护好了，要求出现次数 $\geq k$ 的颜色数量，query (100000) - query (k - 1) 即可。
每次把 $BIT$ 和桶清空，还是最后一个遍历重儿子。
这里为了方便，两者都用 $map$ 写，所以时间复杂度是 dsu on tree 的一个 $\log$，$BIT$ 的一个 $log$，$map$ 的一个 $\log$。
$n\log^3 n$，但是凭借 $BIT$ 和 dsu on tree的超小常数，过了。
代码：
#include <map> #include <vector> #include <iostream> using namespace std; int n, q; int fa[100005], sz[100005], wson[100005]; int c[100005], ans[100005]; vector <pair <int, int> > v[100005]; vector <int> G[100005]; map <int, int> sum, b;//sum: 树状数组，维护每个数出现次数的出现次数 int dfs1 (int x) {//剖链 for (int i = 0; i < G[x].size (); i ++) if (G[x][i] != fa[x]) { fa[G[x][i] ] = x; int tmp = dfs1 (G[x][i]); sz[x] += tmp; if (sz[wson[x] ] < tmp) wson[x] = G[x][i]; } return ++ sz[x]; } void add (int x, int y) {for (; x <= 100000; x += x & -x) sum[x] += y;} int query (int x) { int ret = 0; for (; x > 0; x -= x & -x) ret += sum[x]; return ret; } void dfs2 (int x) {//重新处理，之前的被清空了。 if (b[c[x] ] != 0) add (b[c[x] ], -1); ++ b[c[x] ]; add (b[c[x] ], 1); for (int i = 0; i < G[x].size (); i ++) if (G[x][i] != fa[x]) dfs2 (G[x][i]); } void dfs_ans (int x) {//统计以 x 为根的子树的答案。 for (int i = 0; i < G[x].size (); i ++) if (G[x][i] != fa[x] && G[x][i] != wson[x]) { dfs_ans (G[x][i]); sum.clear (); b.clear (); } if (wson[x] != 0) dfs_ans (wson[x]); if (b[c[x] ] != 0) add (b[c[x] ], -1); ++ b[c[x] ]; add (b[c[x] ], 1); for (int i = 0; i < G[x].size (); i ++) if (G[x][i] != fa[x] && G[x][i] != wson[x]) dfs2 (G[x][i]); for (int i = 0; i < v[x].size (); i ++) ans[v[x][i].second] = query (100000) - query (v[x][i].first - 1); //second 是询问编号，first 是 k。出现次数在 1 ~ 100000 的减去在 1 ~ k - 1 的得到在 1 ~ k 的。 } int main () { int x, y; scanf ("%d%d", &n, &q); for (int i = 1; i <= n; i ++) scanf ("%d", &c[i]); for (int i = 1; i < n; i ++) { scanf ("%d%d", &x, &y); G[x].push_back (y); G[y].push_back (x); } dfs1 (1); for (int i = 1; i <= q; i ++) { scanf ("%d%d", &x, &y); v[x].push_back (make_pair (y, i) ); } dfs_ans (1); for (int i = 1; i <= q; i ++) printf ("%d\n", ans[i]); return 0; }
长链剖分 dsu on tree
重链剖分 dsu on tree 的题目还有很多，这里不再详解了。长链剖分才是优美中的优美，以 $O(n)$ 解决问题。
它适用于解决这类问题：多次询问，每次询问也是求以 $x$ 为根的子树内的东西，而直接暴力的复杂度是 $depth[x]$ 的。（即以 $x$ 为根的子树的深度）
例题：
CF1009F
大家可以自己先去想一想。