Dyd's Blog

He who has a strong enough why can bear almost any how.

dsu on tree

Posted on In
Symbols count in article: 2.7k Reading time ≈ 2 mins.

树上启发式合并

思想

感觉就是重链剖分，好吧思想如下：

  • 先统计它轻儿子的答案，统计完后删除信息
  • 再统计它重儿子的答案 ，统计完后保留信息
  • 去遍历轻儿子，与保留的信息合并

是不是满满的长链剖分把长链换成重链的感觉

一般用于处理离线问题，而且用于空间无法给每个点存下所以信息的时候（不然就直接调用了合并个寂寞）

复杂度分析

Dyd 太弱所以一开始都没搞懂，后来发现一个简单的分析方法

考虑一个节点会被遍历多少次，在不考虑其它操作的情况下，显然本身有一次，然后它到根的路径上每有一条轻边它就会被遍历 $2$ 次，而我们知道它到根只有 $O(\log n)$ 条轻边（如果 $(u, v)$ 是一条轻边，有 $si[u] < si[v] / 2$ ），所以总次数为 $O(\log n)$ 次；考虑到有 $n$ 个点，时间复杂度为 $O(n \log n)$

例题

直接上题了，本来想上Tree and Queries这个板子题的，但怕和讲树上莫队的人重题，所以看这个：Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths（这好像是 dsu on tree 发明者出的题，还是比较板）

首先，可以重排乘为回文串，就是出现次数为奇数的字符 $\le 1$ 个，我们只关系每个字符的奇偶性，敏锐的观察到字符集大小只有 $22$ ，直接状压一手，一次 $dfs$ 即得每个点到根路径的压缩信息，记作 $ct[x]$

显然对于一条路径 $(u, v)$ ，我们要的信息就是 $ct[u] \oplus ct[v]$ ，然后我们 瞟一眼题解可以 发现合法的状态只有 $23$ 种，而该路径对答案的贡献是 $dep[u] + dep[v] - 2dep[lca(u, v)]$

枚举 $x$ 作为 $lca$ ，将其子树一个个遍历，开个同维护 $2^{22}$ 种信息对应的最大深度，再启发式合并一下，不难做到 $O(23 n \log n)$

另外，一个常用的常数优化思想就是把树转链，这样统计信息就不必 dfs ，但考虑到 CF 一般不卡常 绝对不是 Dyd 懒 就没打

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
#define fi first
#define se second
const int N = 5e5 + 100;
int n, ct[N], dep[N], son[N], si[N];
int h[N], idx = 0, as[24], cnt[(1 << 22) + 100], ans[N], cp, cq;
std::pair<int, int> p[N];
struct Edge{ int ne, ver, w; } e[N << 1];
void add(int x, int y, int z){ e[idx] = {h[x], y, z}, h[x] = idx++; }
void dfs(int x, int fa, int c)
{
    dep[x] = dep[fa] + 1, si[x] = 1, ct[x] = c;
    for (int i = h[x], y; ~i; i = e[i].ne) if (!dep[y = e[i].ver])
    {
        dfs(y, x, c ^ (1 << e[i].w));
        si[x] += si[y];
        if (si[y] > si[son[x]]) son[x] = y;
    }
}
void walk(int x, int fa)
{
    p[++cp] = {ct[x], dep[x]};
    for (int i = h[x]; ~i; i = e[i].ne) if (e[i].ver != fa) walk(e[i].ver, x);
}
void calc(int x, int fa, int is)
{
    for (int i = h[x], y; ~i; i = e[i].ne) if ((y = e[i].ver) != fa && y != son[x])
    {
        calc(y, x, 0);
        ans[x] = std::max(ans[x], ans[y]);
    }
    if (son[x]) calc(son[x], x, 1), ans[x] = std::max(ans[x], ans[son[x]]);
    for (int *t = as; t != as + 23; ++t) if (cnt[ct[x] ^ *t]) ans[x] = std::max(ans[x], cnt[ct[x] ^ *t] - dep[x]); //统计重儿子和自己
    cnt[ct[x]] = std::max(cnt[ct[x]], dep[x]);
    for (int i = h[x], y; ~i; i = e[i].ne) if ((y = e[i].ver) != fa && y != son[x])
    {
        cp = 0;
        walk(y, x);
        for (int j = 1; j <= cp; ++j)
            for (int *t = as; t != as + 23; ++t) if (cnt[p[j].fi ^ *t]) ans[x] = std::max(ans[x], cnt[p[j].fi ^ *t] + p[j].se - (dep[x] << 1));
        for (int j = 1; j <= cp; ++j) cnt[p[j].fi] = std::max(cnt[p[j].fi], p[j].se);
    }
    if (!is)
    {
        cp = 0;
        walk(x, fa);
        for (int i = 1; i <= cp; ++i) cnt[p[i].fi] = 0;
    }
}
int main()
{
    scanf("%d", &n);
    std::memset(h, -1, (n + 1) << 2);
    for (int i = 2, p; i <= n; ++i)
    {
        char c[2];
        scanf("%d %s", &p, c);
        add(i, p, c[0] - 'a'), add(p, i, c[0] - 'a');
    }
    as[0] = 0;
    for (int i = 0; i < 22; ++i) as[i + 1] = 1 << i;
    dfs(1, -1, 0), calc(1, -1, 1);
    for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
    return 0;
}