dsu on Tree(树上启发式合并)
当遇到处理子树询问，并且无修改时。可以考虑树上启发式合并。
算法流程：
- step1：处理出每个点的 \(siz_x\) 以及重儿子 \(son_x\)。
void dfs(int x, int fa) {
siz[x] = 1;
int Maxson = 0;
for(int i = 0; i < p[x].size(); i++) {
int y = p[x][i];
if(y == fa) continue;
dfs(y, x);
siz[x] += siz[y];
if(siz[y] > Maxson) {
Maxson = siz[y];
son[x] = y;
}
}
}
- step2：进入它的所有轻儿子，并删除贡献。
- step3：进入它的重儿子，这里不删除贡献。
- step4：将轻儿子加入贡献。
- step5：如果需要删除贡献，就删除贡献。
void add(int x, int fa, int val) { //加入/删除贡献
cnt[a[x]] += val;
if(cnt[a[x]] > Mx) {
Mx = cnt[a[x]];
sum = a[x];
}
else if(cnt[a[x]] == Mx) {
sum += a[x];
}
for(int i = 0; i < p[x].size(); i++) {
int y = p[x][i];
if(y == fa || y == Son) continue;
add(y, x, val);
}
}
void Get(int x, int fa, bool opt) {
for(int i = 0; i < p[x].size(); i++) {
int y = p[x][i];
if(y == fa || y == son[x]) continue;
Get(y, x, 1);
}
if(son[x]) Get(son[x], x, 0), Son = son[x];
add(x, fa, 1); Son = 0;
ans[x] = sum;
if(opt) add(x, fa, -1), sum = 0, Mx = 0;
}
时间复杂度为 \(n \log n\)。
这就是CF600E的代码。
#include<bits/stdc++.h>
#define int long long
#define N 100005
using namespace std;
int n;
int a[N], son[N], siz[N], cnt[N];
vector<int>p[N];
void dfs(int x, int fa) {
siz[x] = 1;
int Maxson = 0;
for(int i = 0; i < p[x].size(); i++) {
int y = p[x][i];
if(y == fa) continue;
dfs(y, x);
siz[x] += siz[y];
if(siz[y] > Maxson) {
Maxson = siz[y];
son[x] = y;
}
}
}
int Son = 0, sum = 0, Mx = 0;
int ans[N];
void add(int x, int fa, int val) {
cnt[a[x]] += val;
if(cnt[a[x]] > Mx) {
Mx = cnt[a[x]];
sum = a[x];
}
else if(cnt[a[x]] == Mx) {
sum += a[x];
}
for(int i = 0; i < p[x].size(); i++) {
int y = p[x][i];
if(y == fa || y == Son) continue;
add(y, x, val);
}
}
void Get(int x, int fa, bool opt) {
for(int i = 0; i < p[x].size(); i++) {
int y = p[x][i];
if(y == fa || y == son[x]) continue;
Get(y, x, 1);
}
if(son[x]) Get(son[x], x, 0), Son = son[x];
add(x, fa, 1); Son = 0;
ans[x] = sum;
if(opt) add(x, fa, -1), sum = 0, Mx = 0;
}
signed main() {
scanf("%lld", &n);
for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
for(int i = 1, u, v; i <= n - 1; i++) {
scanf("%lld %lld", &u, &v);
p[u].push_back(v);
p[v].push_back(u);
}
dfs(1, 0);
Get(1, 0, 0);
for(int i = 1; i <= n; i++) {
printf("%lld ", ans[i]);
}
return 0;
}
后面是一些我做过的简单题：
CF375D
CF208E
CF1009F
CF246E