数据结构学习笔记(8) 启发式合并
启发式合并是用来解决子树中的统计问题。
在codeforces上叫做dsu on tree(树上启发式合并)。这里我们主要是来讲在树上进行启发式合并。
实际上之前我有讲过启发式合并严格鸽：启发式合并 看似暴力实则很快的算法
还有利用启发式合并的并查集严格鸽：ACM——可撤销并查集教程
但是没有讲过树上启发式合并。
我们一般需要维护一个 sub[u] ，表示以 u 为根的子树中的点。
下图中 sub[3] = [3,6,7,8,9]
但是如果暴力维护每个 sub[u] 肯定是会爆炸的。
但是
启发式合并就是在合并的时候将size小的那个集合合并到size大的那个集合里面。
比如[1,2,3] 和 [3,5,6,7] 合并，选择遍历前者来把元素放入后者。
void merge(vector<int>& a, vector<int>& b) {
if (a.size() > b.size()) {
for (int x : b)a.push_back(x);
}
else {
for (int x : a)b.push_back(x);
}
}
初看上可能感觉这就是个暴力。但是我们分析一下每个元素被push_back()了多少次。
一个集合中的元素被放入另一个集合中会被push_back()一次。但是这个元素所在的集合的大小至少扩大了一倍。所以一个元素最多被push_back()了 O(log(N)) 次。
也就是用启发式合并，总的时间复杂度为 \rm O(nlogn) 。
对于 \rm sub[u] ，可以从其子节点 \rm v ，利用启发式合并进行转移。
这里考虑下实现，一般的做法是，我们开一个
vector<int>sub[N]
\rm mx_{son} 表示子树最大的子节点。
然后我们把其它的子节点中的 sub 都放到这个 mx_{son} 中。
然后把这个 mx_{son} 复制给 u ，但是因为有个复制操作，所以需要。
id[u] 表示 u 被映射到了哪个位置。
这样有以下代码
vector<int>sub[N];
void dfs(int u, int fa) {
id[u] = ++tot;
int mx_son = -1, mx_sz = 0;
for (int v : g[u]) {
if (v == fa)continue;
dfs(v, u);
if (sub[id[v]].size() > mx_sz) {
mx_sz = sub[id[v]].size();
mx_son = v;
}
}
if (mx_son != -1)id[u] = id[mx_son];//复制操作
for (int v : g[u]) {
if (v == fa)continue;
if (v == mx_son)continue;
for (int son : sub[id[v]])
sub[id[u]].push_back(son);
}
sub[id[u]].push_back(u);
}
当然优化复制操作可以用c++11的move。
其实这样就可以直接做题了
题目链接：
题意：
做法：
我们在记录子树出现了哪些节点之外，还需要记录每种颜色出现的次数。
所以我们直接套一个结构体
struct node {
int mx_cnt = 0;//最多的出现次数
ll mx_sum = 0;//出现次数最多的颜色的编号和
map<int, int>cnt;
vector<int>list;
void add(int u) {
cnt[c[u]]++;
if (cnt[c[u]] > mx_cnt)mx_cnt = cnt[c[u]], mx_sum = c[u];
else if (cnt[c[u]] == mx_cnt)mx_sum += c[u];
list.push_back(u);
}
int size() { return list.size(); }
}sub[N];
这里我们选择直接套一个map，复杂度为 \rm O(nlog^2n) , 10^5 的数据完全够用。
这样我们套一下上面的代码，就可以愉快的做出本题了。
code
const int N = 1e5 + 5;
int n, c[N], id[N], tot = 0;
struct node {
int mx_cnt = 0;//最多的出现次数
ll mx_sum = 0;//出现次数最多的颜色的编号和
map<int, int>cnt;
vector<int>list;
void add(int u) {
cnt[c[u]]++;
if (cnt[c[u]] > mx_cnt)mx_cnt = cnt[c[u]], mx_sum = c[u];
else if (cnt[c[u]] == mx_cnt)mx_sum += c[u];
list.push_back(u);
}
int size() { return list.size(); }
}sub[N];
ll ans[N];
vector<int>g[N];
void dfs(int u, int fa) {
id[u] = ++tot;
int mx_son = -1, mx_sz = 0;
for (int v : g[u]) {
if (v == fa)continue;
dfs(v, u);
if (sub[id[v]].size() > mx_sz) {
mx_sz = sub[id[v]].size();
mx_son = v;
}
}
if(mx_son!=-1)id[u] = id[mx_son];
for (int v : g[u]) {
if (v == fa)continue;
if (v == mx_son)continue;
for (int son : sub[id[v]].list)
sub[id[u]].add(son);
}
sub[id[u]].add(u);
ans[u] = sub[id[u]].mx_sum;
}
void slove() {
cin >> n;
for (int i = 1; i <= n; i++)cin >> c[i];
for (int i = 1; i <= n - 1; i++) {
int u, v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
for (int i = 1; i <= n; i++)cout << ans[i] << " ";
cout << endl;
}
不过这个是一个比较裸的启发式合并的题目，大家可以做做下面两道题目练习。
严格鸽：Codeforces Round #760 (Div. 3) G(离线/并查集/数据结构)
严格鸽：Educational Codeforces Round 132 C(贪心) D E(启发式合并 + 懒标记)
除了启发式合并，我们还可以用线段树合并来解决此类问题。