Note -「Dsu On Tree」学习笔记

前置芝士

树连剖分及其思想,以及优化时间复杂度的原理。

讲个笑话这个东西其实和 Dsu(并查集)没什么关系。

等等好像时间复杂度证明伪了??


算法本身

Dsu On Tree,一下简称 DOT,常用于解决子树间的信息合并问题。

其实本质上可以理解为高维树上 DP 的空间优化,也可以理解为暴力优化。

在这里我们再次明确一些定义:

  • 重儿子 & 轻儿子:一个节点的儿子中子树最大的儿子称为该节点的重儿子,其余的儿子即为轻儿子。特殊的,如果子树最大的有多个,我们任取一个作为重儿子。
  • 重边 & 轻边:连接一个节点与它的重儿子的边称为重边,连接一个节点与它的轻儿子的边称为轻边。
  • 重链 & 轻链:全由重边构成的链称为重链,全由轻边构成的链称为轻链。重链和轻链互不相交。

对于需要统计一个子树的信息的问题,暴力的时间复杂度通常是 \(O(n^2)\) 。

为了优化时间复杂度,DOT 采用了一个非常巧妙的转移方式。

我们利用 \(O(1)\) 的时间复杂度维护并上传每个节点的重儿子及其子树的信息。

在遭遇一次查询时,我们再暴力统计当前节点的所有轻儿子及其子树信息,并和重儿子信息结合得到答案。可以证明到对于每个节点统计轻儿子及其子树的时间复杂度和是 \(O(n \log_2 n)\) 的。具体流程详见代码。

时间复杂度具体口胡证明方法如下。

树上性质 1

结论:如果有一条轻边 \((u, v)\),且 \(u\) 是 \(v\) 的父亲。则一定有 \(size(v) \leq \frac {size(u)} {2}\) 。其中 \(size(x)\) 表示 \(x\) 的子树大小。

不难发现,若 \(size(v) > \frac {size(u)} {2}\) ,则它一定是 \(u\) 的重儿子,这与轻边 \((u, v)\) 矛盾,得证。

树上性质 2

结论:从某一子树的根节点 \(u\) 到该子树上的任意节点 \(v\) 的路径经过的轻边数一定小于等于 \(\log_2(size(u))\)。

由性质 \(1\) 可知,经过一条轻边,至少会将节点个数减半。设总共会经过 \(e\) 条轻边,则有 \(size(v) \leq \frac {size(u)} {2^e}\)。且 \(size(v) \geq 1\),所以有 \(1 \leq \frac {size(u)} {2^e}\)。故 \(2^e \leq size(u)\),即 \(e \leq \log_2(size(u))\),得证。

关于统计轻儿子的时间复杂度

对于当前节点 \(u\),到达其任意子树上的节点经过的轻边数小于等于 \(\log_2(size(u))\)。故可以粗略理解为在这条路径上存在 \(\log_2(size(u))\) 个轻儿子。所以在这个子树上总共有小于等于 \(size(u)\log_2 size(u)\) 个亲儿子。

而所有的重儿子子树我们都是一直向上传递,直到遇到一条轻边,故重儿子部分仍然是 \(O(1)\)。

那么对于 \(u\),得到它完整的信息所需时间复杂度为 \(size(u)\log_2 size(u)\), 故对于根节点,整个树的信息统计仅需耗时 \(n \log_2 n\)。

具体实现

#include <cstdio>
#include <vector>
using namespace std;

typedef long long LL;
int Max(int x, int y) { return x > y ? x : y; }
int Min(int x, int y) { return x < y ? x : y; }
int Abs(int x) { return x < 0 ? -x : x; }

int read() {
    int k = 1, x = 0;
    char s = getchar();
    while (s < '0' || s > '9') {
        if (s == '-')
            k = -1;
        s = getchar();
    }
    while (s >= '0' && s <= '9') {
        x = (x << 3) + (x << 1) + s - '0';
        s = getchar();
    }
    return x * k;
}

void write(LL x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

void print(LL x, char s) {
    write(x);
    putchar(s);
}  // 漂亮的输入输出优化及一些模板。

const int MAXN = 1e5 + 5;

struct data {
    int id, x;
    // id 表示这是第几个查询,x 表示是谁的子树信息。
    data() {}
    data(int Id, int X) {
        id = Id;
        x = X;
    }
} vector<data> q[MAXN];
// DOT 虽然解决了时间复杂度,但如果想要保存所有子树的信息还是有平方的空间复杂度。
// 所以我们经常采用边跑 DOT,边在有查询的节点 x 上统计答案的思路。

vector<int> mp[MAXN];

void Add_Edge(int u, int v) {
    mp[u].push_back(v);
    mp[v].push_back(u);
}  // 加边 & 建树。

int Son[MAXN], Size[MAXN];
// Son 代表节点 u 的重儿子节点编号,Size 代表节点 u 的子树大小。
LL ans[MAXN];
// 用于统计答案。

void dfs(int u, int fa) {
    Size[u] = 1;
    Son[u] = -1;
    int ma = -1;  // 用于寻找最大子树。
                  // 一些初始化。
    for (int i = 0, v; i < mp[u].size(); i++) {
        v = mp[u][i];
        if (v == fa)
            continue;
        dfs(v, u);
        Size[u] += Size[v];  // 计算子树大小。
        if (Size[v] > ma) {
            ma = Size[v];
            Son[u] = v;  // 找重儿子。
        }
    }
}

int son = -1;

void calc(int u, int fa, int val) {  // 暴力统计除重儿子及其子树外的残缺子树信息。
    ...;                             // 一些操作因题而异。
    for (int i = 0, v; i < mp[u].size(); i++) {
        v = mp[u][i];
        if (v == fa || v == son)
            continue;
        calc(v, u, val);
    }
}

void dfs2(int u, int fa, bool keep) {
    // u, fa 来自树上遍历的常规变量。
    // 若 keep 为 1,表示当前节点是 fa
    // 的重儿子,当前节点统计的轻儿子加重儿子的信息不需要清空,保留下来直接上传。 若 keep 为 2,表示当前节点是
    // fa 的轻儿子,则当前节点统计的轻儿子加重儿子的信息需要清空,不清空的话,在 fa 上会再统计一次,这一段是
    // DOT 的核心操作,可以借助画图深入理解。
    for (int i = 0, v; i < mp[u].size(); i++) {
        v = mp[u][i];
        if (v == fa || v == Son[u])
            continue;
        dfs2(v, u, false);
    }
    if (Son[u] != -1) {
        dfs2(Son[u], u, true);
        son = Son[u];
    }
    calc(u, fa, 1);  // 统计贡献。
    for (int i = 0; i < q[u].size(); i++) ans[q[u][i].id] = ...;
    son = -1;
    // 注意,清空贡献是整个子树,不止是去除了重儿子及其子树的残缺子树。
    // 当然这里的不会影响到总体的时间复杂度。见补充
    if (!keep)
        calc(u, fa, -1);  // 清空贡献。
}

int main() {
    // 显然主函数因题而异。
    int n = read();
    for (int i = 1, u, v; i < n; i++) {
        u = read(), v = read();
        Add_Edge(u, v);
    }
    int m = read();
    for (int i = 1; i <= m; i++) {
        int x = read();
        q.push_back(data(i, x));
    }
    dfs(1, -1);
    dfs2(1, -1, 1);
    for (int i = 1; i <= m; i++) print(ans[i], ' ');
    return 0;
}

补充

对于每一层,我们需要清空的节点个数大概是 \(\frac n {2^e}\) 个(即当前层轻儿子的子树大小和),所以总需要清空的节点数近似于 \(\sum_{e = 1}^{\lfloor log_2 n \rfloor} \frac n {2^e}\),简单化简发现它等于 \(n \times (\frac 1 2 + \dots + \frac 1 {2^{\lfloor log_2 n \rfloor}})\),即 \(n \times (1 - \frac 1 {2^{\lfloor log_2 n \rfloor}})\),显然它甚至连 \(n\) 都达不到,故其不为算法瓶颈。


应用场景

上一篇:线段树分治 ---- CF1217F - Forced Online Queries Problem(假离线 可撤销并查集 + 线段树分治)详解


下一篇:浅谈dsu on tree