Contest7519 - 线段树合并 & 静态链分治
Published:
A 主要颜色
经 典 老 题。
Method 0: 启发式合并 $O(n \log n)$
最简单的思路：给每个节点开值域哈希表，按正常的启发式合并（Small-To-Large Merging）做就行了，$O(n \log n)$。
ll mx[MAXN]; // 众数的出现次数
ll ans[MAXN]; // 众数之和
unordered_map<ll, ll> mp[MAXN];
void dfs(int u, int fa) {
mp[u][c[u]] = 1;
mx[u] = 1;
ans[u] = c[u];
for (auto v : G[u]) if (v != fa) {
dfs(v, u);
if (mp[v].size() > mp[u].size()) {
swap(mp[u], mp[v]);
mx[u] = mx[v];
ans[u] = ans[v];
}
for (auto [col, cnt] : mp[v]) {
mp[u][col] += cnt;
if (mp[u][col] > mx[u]) {
mx[u] = mp[u][col];
ans[u] = col;
} else if (mp[u][col] == mx[u])
ans[u] += col;
}
}
}
Method 1: 线段树合并 $O(n \log n)$
借鉴上面的那一套方法。有的时候问题并非哈希表能够直接解决，需要用线段树，这个时候线段树合并（Segment Tree Merging）的 tech 就有用了。
https://zhuanlan.zhihu.com/p/575513452 https://mzhang2021.github.io/cp-blog/segtree-merging/
动态开点线段树（Sparse Segment Tree）
Method 2: 静态链分治 $O(n \log n)$
Heavy Light Decomposition
B
P3521 [POI 2011] ROT-Tree Rotations
C
P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并