树的启发式合并可以解决很多不涉及修改的子树查询问题.
每次向上合并时, 轻链并入重链, 可以使得总复杂度由 \(O(n^2)\) 变成 \(O(n\log(n))\). 因为每次加入重链, 子树大小都会翻倍.
例题: codeforces 600E
给定一棵树, 每个节点都有一个颜色值.
定义一种颜色值占领一棵子树, 当且仅当这种颜色是这棵子树中出现最多的颜色.
问每个节点为根的子树中, 占领这棵子树的颜色值之和.
代码
- #include <bits/stdc++.h>
- #define FOPI freopen("in.txt", "r", stdin)
- #define FOPO freopen("out.txt", "w", stdout)
- using namespace std;
- typedef long long LL;
- typedef pair<int, int> pr;
- const int maxn = 1e5 + 100;
- int n;
- vector<int> v[maxn];
- map<int, int> col[maxn];
- LL ans[maxn];
- int maxt[maxn];
- void merge(int x, int y)
- {
- if (col[x].size() <col[y].size()) {
- swap(col[x], col[y]);
- ans[x] = ans[y];
- maxt[x] = maxt[y];
- }
- for (auto val : col[y]) {
- int a = val.first, b = val.second;
- col[x][a] += b;
- if (col[x][a]> maxt[x]) {
- maxt[x] = col[x][a];
- ans[x] = a;
- }
- else if (col[x][a] == maxt[x]) {
- ans[x] += a;
- }
- }
- col[y].clear();
- }
- void dfs(int x, int from)
- {
- for (int y : v[x]) {
- if (y == from) continue;
- dfs(y, x);
- merge(x, y);
- }
- }
- int main()
- {
- //FOPI;
- scanf("%d", &n);
- int x, y;
- for (int i = 1; i <= n; i++) {
- scanf("%d", &x);
- col[i][x] = 1;
- ans[i] = x;
- maxt[i] = 1;
- }
- for (int i = 1; i <= n-1; i++) {
- scanf("%d%d", &x, &y);
- v[x].push_back(y), v[y].push_back(x);
- }
- dfs(1, 0);
- printf("%lld", ans[1]);
- for (int i = 2; i <= n; i++)
- printf("%lld", ans[i]);
- puts("");
- }
来源: http://www.bubuko.com/infodetail-3068920.html