树上启发式合并学习笔记

· · 个人记录

参考文献：

1 树上启发式合并简介

1.1 理论

先吐槽一句，这个算法只是名字很高级。

本算法可以在较优的时间复杂度内求出不少可以离线的树上问题。

我们不如先带入情景：

洛谷 CF600E Lomsat gelral

题目大意：

给定节点数量为 n 的树，编号为 i 的结点的颜色为 c_i。求出每一颗子树内哪种颜色的结点最多。（1 \le n \le 2 \times 10^5）

首先假设，我们拥有无限的空间，你数组开多大都没事。那么我们不妨定义 cnt_{i,j} 表示以 i 为根节点的子树内，颜色为 j 的节点个数。我们只需要遍历一遍整棵树，每个子树求出答案后向上更新即可。问题就在于，空间并不是无限的。

如果我们定义 cnt_i 表示当前字数内颜色为 i 的个数，那么算法流程变成了以下：

不难发现的是，以上算法时间复杂度会很高，而高就高在你每次统计下一棵子树时就要重置一次 cnt。但是，还是对于 x 这个节点，你可以发现你统计完最后一个儿子节点的答案后，不用清空 cnt，可以直接统计 x 的答案。如果你来手动模拟这个过程，你一定会把这次不用清空 cnt 的机会留给 x 所有儿子的子树中最大的那个（即重儿子），这样你就可以减少清空 cnt 所花费的时间。看上去这个优化很小，对吧。事实上，这个优化可以让这个算法的时间复杂度降低到 O(n\ \log\ n)。证明。

总结：

对于当前节点 i，求出它以及其子树内每个节点的答案。

轻/重儿子的定义参见数链剖分

1.2 实现

参考代码（部分）：

const int N = 1e5 + 5;
int n, a[N], siz[N], son[N], cnt[N], ans[N], mx, mxsum, hson;
// siz[] 为子数大小，son[] 为重儿子是哪个，cnt[] 表示当前的答案，ans[] 是总答案。
vector<int> v[N];
void dfs1(int x, int fa) { // 先维护 siz[], son[]... 之类的东西。
  siz[x] = 1, son[x] = -1;
  for (int i : v[x]) {
    if (i == fa) continue;
    dfs1(i, x);
    siz[x] += siz[i];
    if (son[x] == -1 || siz[i] > siz[son[x]]) {
      son[x] = i;
    }
  }
}
void cnt_ans(int x, int fa, int val) { // 统计答案。
  cnt[a[x]] += val;
  if (cnt[a[x]] > mx) {
    mx = cnt[a[x]], mxsum = a[x];
  } else if (cnt[a[x]] == mx)
    mxsum += a[x];
  for (int i : v[x]) {
    if (i == fa || i == hson) continue;
    cnt_ans(i, x, val);
  }
}
void dfs2(int x, int fa, bool keep) { // 树上启发式合并的关键部分。
  for (int i : v[x]) { // 先遍历其轻儿子。
    if (i == fa || i == son[x]) continue;
    dfs2(i, x, 0);
  }
  if (son[x] != -1) { // 如果这个节点有重儿子结点（也就是非叶子），便利其重儿子。
    dfs2(son[x], x, 1), hson = son[x];
  }
  cnt_ans(x, fa, 1);
  hson = 0, ans[x] = mxsum;
  if (!keep) { // 暴力删除 cnt。
    cnt_ans(x, fa, -1);
    mxsum = 0, mx = 0;
  }
}
signed main() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1, x, y; i < n; i++) {
    cin >> x >> y;
    v[x].pb(y), v[y].pb(x);
  }
  dfs1(1, 0);
  dfs2(1, 0, 0);
  for (int i = 1; i <= n; i++) cout << ans[i] << " ";
  return cout << endl, 0;
}

2 题目

2.1 例题 1

洛谷 CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

题目大意：

给定结点数量为 n 的树，每条边上有一个字符（a-v 共 22 种小写字母），求出每棵子树中最长的 Dokhtar-kosh 路径长度。

Dokhtar-kosh 路径的定义是一条简单路径，且路径上所有结点的字符经过重排列后，可以变成回文字符串。

思路：

不难发现，若经过重排列后能成为回文字符串，出现次数为奇数次的字符数量 \le 1。如果我们把每个字母分别用数字表示出来：0,2^0,2^1,2^2,…,2^{21}，那么如果某条路径是 Dokhtar-kosh，这条路径上的异或和必然为 0 或 2^k（1 \le k \le 21)（因为出现次数为偶数次的都被抵消了，剩下的只有奇数次的）。

我们维护一个 d_i 表示从 1 到 i 路径上的异或和，不难发现，i 与 j 之间的异或和就是 d_i \oplus d_j（实际上是从 i 走到 lca(i,j) 再到 j 的异或和，也就是 d_i \oplus d_{lca(i,j)} \oplus d_j \oplus d_{lca(i,j)} = d_i \oplus d_j）。

最后，我们再维护两个数组 f 和 ans。f_i 表示当前子树中其 dis 为 i 的深度最大的节点，ans_i 表示以 i 为根的子树的答案。我们遍历时枚举如果当前这个点加入到某一条 Dokhtar-kosh 路径之中，这条 Dokhtar-kosh 路径的异或和为多少（设当前枚举到 j），如果其合法（即 f_{dis_x \oplus j} ≠ 0），那么我们用 f_{dis_x \oplus j} + (depth_i - 2 \times depth_x) 更新 ans_i（depth 是深度）。

参考代码（部分）

const int N = 5e5 + 5, M = N * 2, K = 1 << 23;
int n, a[N], siz[N], son[N], cnt[N], ans[N], dfn[2][N], depth[N], dis[N], id[N], idx, f[K], hson;
// dfn[] 记录的是某个结点的子树中，dfs[] 序最大的和最小的，id[] 记录 dfs 序为 i 的节点是多少。depth 是深度，dis、f、ans 见思路部分。
vector<pii> v[M];
void dfs1(int x, int fa) {
  siz[x] = 1, son[x] = -1, depth[x] = depth[fa] + 1;
  dfn[0][x] = ++idx, id[idx] = x;
  for (pii i : v[x]) {
    if (i.fir == fa) continue;
    dis[i.fir] = dis[x] ^ i.sec;
    dfs1(i.fir, x);
    siz[x] += siz[i.fir];
    if (son[x] == -1 || siz[i.fir] > siz[son[x]]) {
      son[x] = i.fir;
    }
  }
  dfn[1][x] = idx;
}
void cnt_ans(int x, int fa) {
  if (f[dis[x]]) {
    ans[x] = max(ans[x], f[dis[x]] - depth[x]);
  }
  for (int i = 0; i <= 21; i++) {
    if (f[dis[x] ^ (1 << i)]) {
      ans[x] = max(ans[x], f[dis[x] ^ (1 << i)] - depth[x]);
    }
  }
  f[dis[x]] = max(f[dis[x]], depth[x]);
  for (pii i : v[x]) {
    if (i.fir == fa || i.fir == hson) {
      continue;
    }
    for (int j = dfn[0][i.fir]; j <= dfn[1][i.fir]; j++) {  // 因为一棵子树内的 dfn 是连续的，可以直接访问。
      if (f[dis[id[j]]]) {
        ans[x] = max(ans[x], f[dis[id[j]]] + (depth[id[j]] - 2 * depth[x]));
      }
      for (int k = 0; k <= 21; k++) {
        if (f[dis[id[j]] ^ (1 << k)]) {
          ans[x] = max(ans[x], f[dis[id[j]] ^ (1 << k)] + (depth[id[j]] - 2 * depth[x]));
        }
      }
    }
    for (int j = dfn[0][i.fir]; j <= dfn[1][i.fir]; j++) {
      f[dis[id[j]]] = max(f[dis[id[j]]], depth[id[j]]);
    }
  }
}
void dfs2(int x, int fa, bool keep) {
  for (pii i : v[x]) {
    if (i.fir == fa || i.fir == son[x]) continue;
    dfs2(i.fir, x, 0);
    ans[x] = max(ans[x], ans[i.fir]);
  }
  if (son[x] != -1) {
    dfs2(son[x], x, 1), hson = son[x];
    ans[x] = max(ans[x], ans[son[x]]);
  }
  cnt_ans(x, fa);
  hson = 0;
  if (!keep) {
    for (int i = dfn[0][x]; i <= dfn[1][x]; i++) {
      f[dis[id[i]]] = 0;
    }
  }
}
signed main() {
  cin >> n;
  for (int i = 1, x; i < n; i++) {
    char c;
    cin >> x >> c;
    v[x].pb({i + 1, 1 << (c - 'a')}), v[i + 1].pb({x, 1 << (c - 'a')});
  }
  dfs1(1, 0);
  dfs2(1, 0, 0);
  for (int i = 1; i <= n; i++) cout << ans[i] << " ";
  return cout << endl, 0;
}

2.2 练习

洛谷 CF375D Tree and Queries

模板题，不讲。

洛谷 CF1009F Dominant Indices

类似于例题 1 的简化版，其实还是模板。

The End

最近写博客可能会暂时到这，所以不要问我我为什么咕咕咕，问就是教练的题单一个接一个（

Thanks

暂无