Top Tree

· · 算法·理论

用人话来说,簇是 T 的连通子图,至多有两个点与外界相连。

下面展示了一个簇的结构:

将树 T 的根补一条父边,则我们认为任意簇满足 |B|=2。

我们画图理解两种运算:

初始时,我们有 n 个基簇(注意我们补上了根节点的父边),目标为通过若干 Rake 或 Compress 操作,将簇合并为 1 个根簇。

对静态的 T,将合并过程的重构树称作静态 Top Tree,简称 STT。STT 上有两类节点,称作 Rake 节点和 Compress 节点,代表合并过程中的簇。我们记录每个簇的上界点和下界点。显然 STT 是一棵二叉树,故我们记录 STT 节点的左右儿子。

一般地,我们希望 STT 的树高较小。

直接使用分治合并,树高是 O(\log^2 |V|) 的。

这句话的意义是,我们记录每个簇的实际 \text{size}。设权值序列为 w_1 \sim w_k,找到最大的 m 使得 \sum \limits_{i=1}^m w_i < \dfrac{1}{2} \sum \limits_{i=1}^k w_i,将 m 作为分治中心。具体地,对 w_i 做前缀和后可以二分找到 m。

代码

个人认为比较清晰的一份实现。

enum node_type {RAKE, COMPRESS};
struct node {
    node_type type;  // 节点类型
    node *l, *r, *f;  // 左儿子 / 右儿子 / 父亲
    int sz, u, v;   // 簇的大小 / 上界点 / 下界点
    // 其他可合并信息
    node();
    void pushup();  
};
node* merge(node* x, node* y, node_type type) {
    node* z = new node;
    z->type = type, z->l = x, z->r = y, z->sz = x->sz + y->sz;
    x->f = z, y->f = z;
    if (type == RAKE) z->u = x->u, z->v = x->v;
    else z->u = x->u, z->v = y->v;
    return z->pushup(), z;
}

int fa[N], sz[N], son[N], len[N];
void dfs1(int u) {   // 重链剖分
    sz[u] = 1, son[u] = 0;
    for (int v : e[u]) {
        if (v == fa[u]) continue;
        fa[v] = u, dfs1(v), sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v;
    }
    len[u] = len[son[u]] + 1;
}

node* build(node** a, int* pre, int l, int r, node_type type) {  // 带权分治
    if (l == r) return a[l];
    int sum = pre[r] - pre[l - 1];
    int mid = partition_point(pre + l, pre + r + 1, [&](int x) -> bool {
        return 2 * (x - pre[l - 1]) <= sum;
    }) - pre;
    if (mid == r) mid--;  
    return merge(build(a, pre, l, mid, type), build(a, pre, mid + 1, r, type), type);
}

node* T[N];
node* dfs2(int u) {  // 建 u 子树 STT
    node** carr = new node*[len[u] + 5];  // Compress 重链
    int* cpre = new int[len[u] + 5];      // Compress 前缀和
    cpre[0] = 0; int tot = 0;
    for (; u; u = son[u]) {
        T[u] = new node; T[u]->u = fa[u], T[u]->v = u, T[u]->sz = 1; 
        node** rarr = new node*[e[u].size() + 5];  // Rake 轻儿子
        int* rpre = new int[e[u].size() + 5];      // Rake 前缀和
        rarr[1] = T[u], rpre[0] = 0; int cnt = 1; 
        for (int v : e[u]) 
            if (v != fa[u] && v != son[u]) rarr[++cnt] = dfs2(v);
        for (int i = 1; i <= cnt; i++) rpre[i] = rpre[i - 1] + rarr[i]->sz;
        carr[++tot] = build(rarr, rpre, 1, cnt, RAKE);
    }
    for (int i = 1; i <= tot; i++) cpre[i] = cpre[i - 1] + carr[i]->sz;
    return build(carr, cpre, 1, tot, COMPRESS);
}

应用

STT 之于树,就如同线段树之于序列,因此 STT 能维护很多奇特信息。

动态直径

问题 1 给定树 T。支持单点修改边权,查询 T 的直径。

对簇 C=(V,E,B),设其上下界点为 u,v。维护下列信息:

在 pushup 时,分 Rake 节点和 Compress 节点进行讨论,处理直径是否跨过界点。

可以发现半群信息的设计类似于线段树维护最大子段和。复杂度 O(q \log n)。

动态 DP

比较奇妙的半群信息。下面以动态最大权独立集为例。

问题 2 给定树 T。支持单点修改点权,查询 T 的最大权独立集。

对簇 C=(V,E,B),维护 f_{0/1,0/1}(C) 表示两个界点选 / 不选时的最大独立集。

为了避免算重,我们钦定选择上界点时,f_{1,0/1} 不计入上界点的权值。

合并信息时,在界点处进行讨论:

复杂度 O(q\log n)。

链 / 子树修改查询

问题 3(P3384) 维护树 T,支持链加、链求和、子树加、子树求和。

对簇 C=(V,E,B),维护簇路径的权值和 f(u,v),容易进行合并。

邻域数点