简单的还有吓人的树论

· · 算法·理论

24 年的 Ice_lift 和 26 年的 Ice_lift 的笔记的整合,可能还不够完善后续还会继续更新。难的可能并不难,但是简单的确实挺简单的,笔者本质很菜。

使用了 Deepseek 进行了部分段落公式规范化,保证人类贡献大于 AI。

1 最近公共祖先 - \text{LCA}

定义:最近公共祖先简称 \text{LCA}(Lowest Common Ancestor)。两个节点的最近公共祖先,就是这两个点的公共祖先里面,离根最远的那个。为了方便,我们记某点集 S=\{v_1,v_2,\ldots,v_n\} 的最近公共祖先为 \text{LCA}(v_1,v_2,\ldots,v_n) 或 \text{LCA}(S)。

性质:

1.0 常用算法

1.1 应用

1.1.1 树上差分

对于一颗树进行树上链进行可差分操作且询问在操作之后的问题可以用树上差分求解。

联系序列差分,区间修相当于将 C_l \gets C_l + x,C_r \gets C_r - x,最后每个元素的值相当于 a_i + \sum_{j = 1}^{i} C_j。

不妨假设对于一个点的最后的增量为 \Delta_x = \sum_{v\in \text{subtree}(u)} C_v。

记根为 \text{rt}。那么如果 C_i \gets C_i + x,那么对于 \forall v, v \in \text{path}(i \leftrightsquigarrow \text{rt}), \Delta_v \gets \Delta_v + x。

此时我们实现了对于一个点到根节点的路径上所有点的修改操作。

那么怎么实现两点间的路径操作?

考虑容斥,我们先对于 u, v 进行点到根节点的路径上所有点的修改操作,发现 \text{LCA}(u, v) 到根节点的路径上的点被多修改了两次,所以考虑 C_{\text{LCA}(u, v)} \gets C_{\text{LCA}(u, v)} - 2x,达到抵消的状态,但是此时本来应该修改的 \text{LCA}(u, v) 却没有修改了,那么考虑 C_{\text{LCA}(u, v)} \gets C_{\text{fa}_{\text{LCA}(u, v)}} - x, C_{\text{fa}_{\text{LCA}(u, v)}} \gets C_{\text{LCA}(u, v)} - x,此时就达到了仅修改 u \leftrightsquigarrow v 上的点的效果了。

如果对于边进行可差分操作,可以将边转化到两个端点中深度较深的点上,然后同点操作一样,不过此时 \text{LCA}(u, v) 所对应的边并不在 u \leftrightsquigarrow v 路径上,所以直接 C_{\text{LCA}(u, v)} \gets C_{\text{LCA}(u, v)} - 2x 即可。

【例题】

2 dfs 序

dfs 序指对树进行 dfs 时的访问顺序,OI 中存在几种定义不同的 dfs 序,其性质和作用效果也不相同。

2.1 朴素 dfs 序

仅在 dfs 进入节点时加入序列。

void dfs (int u) {
    dfn[u] = ++ idx;
    for (int v : g[u]) dfs(v);
}

有以下性质:

  1. 子树在 dfs 序上呈一段连续区间,u 子树内所有点在 dfs 序上对应 [\text{dfn}_u,\ \text{dfn}_u + \text{siz}_u - 1]。
  2. 一个节点的祖先节点的 dfs 序一定小于该点 dfs 序。
  3. 若 \text{dfn}_u < \text{dfn}_v,则要么 u 是 v 的祖先,要么 \text{subtree}(u) 整体排在 \text{subtree}(v) 之前——子树区间是嵌套或相离的,绝不交叉。

2.1.1 序列化

把 \text{subtree}(u) 看成区间 [\text{dfn}_u,\ \text{dfn}_u + \text{siz}_u - 1] 之后,转化为序列上区间问题,可以用扫描线+数据结构等算法解决复杂问题。

2.1.2 换根

把根换成 r 之后,u 的“子树”在原来的 \text{dfn} 上仍然至多是两段区间(\text{dfn} 不必重算):

2.2 括号序

在进入节点和退出节点的时候都记录:

void dfs(int u) {
    in[u] = ++idx;
    for (int v : g[u]) dfs(v);
    out[u] = ++idx;
}

性质:

  1. 区间内出现奇数次的点恰好是路径点集。设 \text{in}_u < \text{in}_v:
    • 若 u 是 v 的祖先(即 \text{LCA}(u, v) = u):路径点集 = [\text{in}_u, \text{in}_v] 中出现奇数次的点;
    • 否则:取区间 [\text{out}_u, \text{in}_v],路径点集 = 该区间内出现奇数次的点 \cup\ \{u\}。此时 \text{LCA}(u, v) 在区间内出现 0 次,需要单独补上。

2.2.1 树上莫队

拍成括号序后,路径询问变成序列上的区间询问,直接套莫队:维护 \text{vis}_u 表示 u 当前是否在路径上,指针移动时遇到 \text{dfn}_p = u 就 \text{vis}_u \gets \text{vis}_u \oplus 1(进入则加入贡献,离开则撤销贡献)。

void add (int p) {
    int u = dfn[p];
    if (!vis[u]) { if (!cnt[c[u]] ++) ans ++; }
    else { if (!-- cnt[c[u]]) ans --; }
    vis[u] ^= 1;
}

【例题】

2.2.2 路径和问题

在 \text{in}_u 放 +a_u,在 \text{out}_u 放 -a_u,对这个长度为 2n 的序列做区间和。设 \text{in}_u < \text{in}_v:

子树整体加 x 在括号序上只是 \text{in} 段区间加 x、\text{out} 段区间加 -x,用线段树维护即可 O(\log n) 求路径点权和 / 路径点数。

2.3 欧拉序

在进入节点和回溯到节点时记录。

void dfs (int u) {
    dfn[++ idx] = u, fst[u] = idx;
    for (int v : g[u]) {
        dfs(v);
        dfn[++ idx] = u;
    }
}

序列长度为 2n - 1:n 个点在“进入”时各记一次,n - 1 条边在“回溯”时各记一次。

性质(其中 \text{fst}_u 为 u 第一次出现的下标,不妨设 \text{fst}_u < \text{fst}_v):

  1. 因为 \text{LCA}(u, v) 在区间内至少出现一次,所以“取最小深度”一定取得到它。

这正是 3.1.0 中“括号序 + RMQ”法的依据:把欧拉序上的深度建成 ST 表,即可 O(n \log n) 预处理、O(1) 查询。

:::info[Code]

int mi[N << 1][20], dep[N], log_2[N << 1];
int pos[N << 1][20];
vector<pi> g[N];
void dfs0 (int u, int fa) {
    dfn[fst[u] = ++ idx] = u, mi[idx][0] = dep[u] = dep[fa] + 1;
    for (auto [v, w] : g[u])
        if (v != fa) {
            dis[v] = dis[u] + w;
            dfs0(v, u);
            dfn[++ idx] = u, mi[idx][0] = dep[u];
        }
}
void build () {
    dfs0(1, 0);
    for(int i = 1; i <= idx; i ++) pos[i][0]=i;
    for(int i = 2; i <= idx; i ++) log_2[i] = log_2[i >> 1] + 1;
    for(int k = 1; k <= 20; k ++)
        for(int i = 1; i + (1 << k) - 1 <= idx; i ++){
            int x = mi[i][k - 1], y = mi[i + (1 << k - 1)][k - 1];
            if(x < y) mi[i][k] = x, pos[i][k] = pos[i][k-1];
            else mi[i][k] = y, pos[i][k] = pos[i + (1 << k - 1)][k - 1];
        }
}
int lca(int l,int r){
    int _ = log_2[r - l + 1];
    return mi[l][_] < mi[r - (1 << _) + 1][_] ? pos[l][_] : pos[r - (1 << _) + 1][_];
}

:::

优势:O(1) 单次查询,适合需要海量查询 \text{LCA} 的题(例如虚树,单次询问要做 O(k) 次 \text{LCA},倍增会多一个 \log)。

劣势:预处理常数大。

复杂度:O(n \log n) 预处理,O(1) 查询。

相关其他应用:欧拉环游树,详见动态树部分。

3 \text{dfn} 排序与虚树

给定关键点集 S,虚树是只保留 S、\text{LCA}(S) 以及它们之间的分叉点,并把边压缩成“原树上的距离”得到的树,规模 O(|S|)。

3.1 单调栈建虚树

按 \text{dfn} 从小到大加入关键点,用栈维护“当前虚树的右链”(已加入的最后一条自上而下的路径):

sort(a + 1, a + k + 1, [](int x, int y) { return dfn[x] < dfn[y]; });
k = unique(a + 1, a + k + 1) - a - 1;
st[top = 1] = 1;
for (int i = 1; i <= k; i ++) {
    int u = a[i];
    if (u == st[top]) continue;
    int l = lca(u, st[top]);
    while (top > 1 && dep[st[top - 1]] >= dep[l])
        add(st[top - 1], st[top]), top --;
    if (st[top] != l) add(l, st[top]), st[top] = l;
    st[++ top] = u;
}
while (top > 1) add(st[top - 1], st[top]), top --;

3.2 动态点集

引理 2 可以动态维护:用 set(以 \text{dfn} 升序排序)维护点集。

插入 / 删除 x 时找前驱 l、后继 r,只需增量:

ans += dis[x] + dis[lca(l, r)] - dis[lca(x, l)] - dis[lca(x, r)];

于是虚树边权和可以 O(\log n) 动态维护;点集 \text{LCA} 就是 \text{dfn} 最小与最大两点的 \text{LCA}(引理 1)。

同样的,这个过程也可以使用以 \text{dfn} 为下标的线段树维护,记录一个区间内 \text{dfn} 的最小值与最大值,每次合并两个区间的增量和将边权和相加后减去 \text{dis}(\text{LCA}(\text{lmax}, \text{rmin}), \text{rt})。

在一些题目中,用线段树合并维护会比 set + 启发式合并更优秀。

【例题】

4 重链剖分

如果 dfs 时先走重儿子,那么同一个 \text{dfn} 同时满足两件事:

  1. 子树连续:\text{subtree}(u) 对应 [\text{dfn}_u,\ \text{dfn}_u + \text{siz}_u - 1];
  2. 重链连续,且链头的 \text{dfn} 最小:链 \text{top} \leftrightsquigarrow u 上的点对应 [\text{dfn}_{\text{top}},\ \text{dfn}_u]。

由重链上区间连续 + 点到根路径至多经过 O(\log n) 条重链的性质,树链剖分能 O(\log^2 n) 维护树上路径信息。

实现上形如:

void sol (int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        work on [dfn[top[u]], dfn[u]];
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) swap(u, v);
    work on [dfn[v], dfn[u]];
}

【例题】

5 特殊树上信息

5.1 重心

定义:以 c 为根时,满足所有真子树大小 \le \frac{n}{2} 的节点 c 即为重心。

性质:

求法:

可以通过一次 dfs 维护以 u 为根时的最大真子树大小 f_u(仍然类似换根 DP,还要考虑 n - \text{siz}_u 这个“子树”),f_u 最小的 u 就是重心。

应用:点分治。

【例题】

5.1.1 动态带权重心

比上面例题的做法更通用普遍。很厉害的东西。

每个点有一个权重 a_i,找到使得 \sum_{u = 1}^{n} a_u \times \text{dis}(u, v) 最小的 v,即带权重心。

以下默认 a_i \ge 0。

随便钦定一个点为根,记 S_u 表示点 u 的子树的 a_u 的和,记 T = S_{\text{rt}}。

和普通重心一样,其判定条件等价于删除该点后剩余的连通分量的权值和均 \le \frac{T}{2}。

可以用调整法理解这个东西,记到某个点的带权路径总为 F(u)。

考虑 F(u) 和 F(v)(v 为 u 的儿子)的差值,等于 - S_v + (T - S_v),也就是 + T - 2S_v。同样的还有 F(u) 和 F(\text{fa}_u) 的差值,等于 + S_u - (T - S_u) = +2S_u - T。重心的 F(u) 是最小的,所以这两个差值都必须 \ge 0,也就是 2S_u \ge T 且 2S_v \le T。

重心是满足 2S_u \ge T 的最深的节点。

因为其最深,所以该点的儿子满足 2S_v < T,同时该点满足 2S_u \ge T,符合上面所述的判定条件。

这里用到了一个很巧妙的东西,如果我们知道实际重心子树内的任意一点 v,我们可以倍增找到第一个满足 2S_u \ge T 的点,即重心。

引理:若 2S_c > T,则 dfs 序上的带权中位点 p 满足 \text{src}(p) \in \text{subtree}(c)。

用线段树二分找到中位数后倍增就可以找到实际重心了。

采用线段树在 dfs 序上维护的话,这里每次查询 S_u 是 O(\log n) 的,加上倍增总体复杂度即为 O(\log^2 n)。

【例题】

定义:树上所有路径中,最长的路径即为直径。

下面记直径两个端点为 (l_1, l_2)。

性质:

求法:

  1. 如果边权全正则考虑两次 dfs,第一次从任意点出发找到最远点,然后以该最远点出发再次找到最远点。由性质 1,第一次找到的点一定是直径端点之一,第二次则找到另一个直径端点。
  2. 树形 DP,记 f_u 表示从 u 出发到 u 子树内的点的最长路径长度,考虑类似换根地维护从 u 出发到 \text{subtree}(u) 外任意点的最长距离 g_u,直径长度为 \max (f_u + g_u)。
  3. 还是树形 DP,维护 f_u 表示 u 到子树内任意点的最长距离,在更新 f_u \gets \max(f_u, f_v + w(u, v)) 前维护 \text{ans} \gets \max(\text{ans}, f_u + f_v + w(u, v))。

【例题】

5.2.1 动态维护带权直径

一种很蠢的做法是使用第二种 DP 状态直接 DDP,码量大的同时复杂度也很劣,我写的是 3\times 3 的矩阵+树剖+线段树。

下面讲解一种很快很便捷的东西(但是只适用于正边权)。

我们回归直径本身的定义,相当于要找到 \max_{1 \le u,v \le n} \text{dis}(u, v)。

把它放到欧拉序上,等价于:

\max_{1 \le u, v \le n} (\text{dis}(u) + \text{dis}(v) - 2 \times \min_{\text{fst}_u \le \text{dfn}_k \le \text{fst}_v} \text{dis}(k))

由于外部取 \max 且内部是 - \min,考虑直接去掉这个 \min,等价于 \max_{i \le j \le k} \text{dis}(i) - 2\text{dis}(j) + \text{dis}(k)。

为什么只适用于正边权:\text{LCA} 是欧拉序区间内深度最小的点,如果有负权边则 \text{dis} 关于 \text{dep} 不具有单调性了,\text{dis} 最小的点深度不一定最小,也就不一定是 \text{LCA}。

这样就脱离树结构本身了,这是可以用线段树维护的东西。

对于一个区间我们维护五个信息:ma, mi, l, r, ans。

考虑合并两个区间的信息:

\begin{array}{l} \text{ma} = \max(\text{ma}_L, \text{ma}_R) \\ \text{mi} = \min(\text{mi}_L, \text{mi}_R) \\ l = \max(l_L, l_R, \text{ma}_L - 2\text{mi}_R) \\ r = \max(r_L, r_R, -2\text{mi}_L + \text{ma}_R) \\ \text{ans} = \max(\text{ans}_L, \text{ans}_R, \text{ma}_L + r_R, l_L + \text{ma}_R) \end{array}

然后放到线段树上维护就可以了,修改一条边的边权对 \text{dis} 的影响等价于子树加,转化为欧拉序上的区间加即可。

值得注意的是,如果维护的是动态“加边”的情形,等价于没有加入的边的端点不能作为 (i, j, k) 的端点 i, k,需要将线段树对应节点的初值设为 (-\infty, \text{dis}(u), -\infty, -\infty, -\infty),最小值保留因为该点可以作为 j 贡献。

特别的,如果有负边权,考虑使用点分树维护。具体怎么做先咕了。

【例题】