生成树相关问题（二）

最小生成树相关问题

最小生成树问题经常要求：点 $(u, v)$ 在 $\textbf{MST}$ 上，权值最大的边 $\text{maxcost}(u, v)$

实现的过程仍然是基于 dfs 和 dp 的，一般来说

定义数据结构
vector<Edge> maxcost[maxn][maxn];

另外需要一个集合 nodes 维护 dfs 时已经被访问过的节点
vector<int> nodes;

执行 $\textbf{dfs}(u, fa)$，尝试加入当前点 $u$

• 遍历已访问过的节点集合 $\text{nodes}$，$\forall x \in \text{nodes}$，更新 $\text{maxcost}(x, u)$，检查路径 $x \to fa \to u$
  如果 $\text{maxe}(x, fa).z > w(fa, u)$，那么 $\text{maxe}(x, u) \leftarrow \text{maxe}(x, fa)$
  否则的话，$\text{maxe}(u, x) \leftarrow \bm{Edge}(fa, u, w(fa, u))$
• 将 $u$ 加入集合 $\text{nodes}$ 中，然后 $\text{dfs}(v, u)$

Qin Shi Huang’s National Road System

根据 $n$ 的取值范围，该问题可以暴力枚举 $(i, j)$，然后求 $A(i, j) / B(i, j)$ 的最大值
其中 $A(i, j)$ 很容易求，就是 $i, j$ 两座城市的人口和 $p_i + p_j$
那么 $B(i, j)$ 呢？首先如果不用法术，$B$ 一定是原图中的最小生成树

用法术，$B(i, j)$ 最小值，一定是 $\text{mst} - \text{maxcost}(i, j)$
$i, j$ 沿着最小生成树走，经过的最大的边记为 $\text{maxcost}(i, j)$，将其从最小生成树上删去，就是答案

$\text{maxcost}(i, j)$ 可以通过 $O(n^2)$ 的预处理求出

核心预处理 $\text{maxcost}$ 的代码给出

struct Edge {
    int x, y;
    double z;
};

vector<vector<Edge> > maxe(maxn, vector<Edge>(maxn, Edge()));

vector<int> nodes;
void dfs(int u, int fa) {
    for (auto x : nodes) {
        if (maxe[x][fa].z > g[fa][u]) maxe[x][u] = maxe[u][x] = maxe[x][fa];
        else maxe[x][u] = maxe[u][x] = Edge{fa, u, g[fa][u]};
    }
    nodes.push_back(u);
 
    for (auto v : G[u]) {
        if (!used[u][v] || v == fa) continue;
        dfs(v, u);
    }
}

增量最小生成树

包含 $n$ 个点的图，依次加入 $m$ 条带权边，每加入一条边，输出当前图中最小生成树的权值

先求出原图 $G$ 的一个最小生成树，加入边 $e(u, v)$ 之后，图中包含 $u \to v$ 的一个环
因此需要找出 $\text{MST}$ 中 $u \to v$ 路径上权值最大的边，即 $\text{maxcost}(u, v)$
最后的答案为 $res = \text{MST} - \text{maxcost}(u, v) + \min(\text{maxcost}(u, v), e(u, v))$

RMQ 解决树上问题

最小生成树有关的问题中，经常求 $\text{MST}$ 中 $u \to v$ 的最大值或最小值
如果将生成树伸展成链，问题可以抽象为区间最值问题，可以用 RMQ 算法求解

RMQ 算法是基于倍增的思想，假设原数组为 $A[\cdots]$，RMQ 需要用一个新数组 $f(i, j)$
表示从 $i$ 开始，长度为 $2^{j}$ 的一段元素的最小值
可以写出递推关系 $f(i, j) = \min (f(i, j-1), f(i+2^{j-1}, j-1))$
初始化时，令 $f(i, 0) = A[i]$

RMQ 的查询操作也很简单，令 $k$ 为满足 $2^{k} \leqslant R-L+1$ 的最大整数，那么区间最值为
$\min (f(l, k), f(r-2^k+1, k))$

Frequent Values

注意到整个数组 $A_i$ 都是非降序的，那么可以用分块思想，将相同的数合并成一个块
对于某个位置 $i$，$le(i)$ 表示 $i$ 的最左边，和 $A_i$ 相同的元素的下标
同理 $ri(i)$ 表示最右边和 $i$ 相同的元素的下标

对于区间 $(l, r)$，求 $(l, r)$ 中出现次数最多的元素，出现的次数
最多元素出现次数是以下几部分取 $\max$
$[l, ri(l)]$，$[le(r), r]$，以及中间的一部分

$[l, ri(l)]$ 很好求，$ri(l) - l + 1$ 就是答案，另外 $le(i)$ 和 $ri(i)$ 数组也很容易求
只需要 $O(n)$ 从前往后扫描整个 $A[\cdots]$，对于某个位置 $i$
如果 $A_i = A_{i-1}$，那么 $le(i) = le(i-1)$，否则的话 $le(i) = i$

那么中间部分怎么求呢？实际上中间部分只需要缩点成块即可，将相同的数缩成一个个块，并且记录块编号
然后对块执行 RMQ 即可，具体编程实现如下

对于某一个位置 $i$，$num(i)$ 表示 $i$ 所在块的编号
如果 $A_i = A_{i-1}$，那么不需要开新块，直接令 $num(i) \leftarrow num(i-1)$
否则的话，需要开一个新块，$num(i) = tot++$
然后再用 $cnt[num(i)]$ 记录这个块有多少个数，直接统计令 $cnt[num(i)]++$ 即可

块的数量存储在 $cnt[0\cdots tot)$ 中，实际上中间部分的最大值，就是用 $cnt$ 初始化 $\text{rmq}$
$\text{rmq}(num[l]+1, num[r]-1)$

const int maxn = 1e5 + 10;
vector<int> a(maxn, 0);
int n, q;

vector<int> le(maxn, 0), ri(maxn, 0);
vector<int> num(maxn, 0), cnt(maxn, 0);
int tot = 0;

template<class T>
struct RMQ {
    vector<vector<T> > f;
    RMQ() = default;
    RMQ(const vector<T>& a, int n) {
        int Log = log(n) / log(2) + 1;
        f.resize(n+1);
        for (int i = 0; i < n+1; i++) f[i].resize(Log);

        for (int i = 0; i < n; i++) f[i][0] = a[i];
        for (int j = 1; (1<<j) <= n; j++) {
            for (int i = 0; i + (1<<j) - 1 < n; i++) {
                f[i][j] = max(f[i][j-1], f[i + (1<<(j-1))][j-1]);
            }
        }
    }

    T qry(int L, int R) const {
        int k = log(R-L+1) / log(2);
        while ((1<<(k+1)) <= R-L+1) k++;
        return max(f[L][k], f[R - (1<<k) + 1][k]);
    }
};

void pre() {
    le[0] = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] == a[i-1]) le[i] = le[i-1];
        else le[i] = i;
    }

    ri[n-1] = n-1;
    for (int i = n-2; i >= 0; i--) {
        if (a[i] == a[i+1]) ri[i] = ri[i+1];
        else ri[i] = i;
    }

    tot = 0;
    for (int i = 0; i < n; i++) {
        if (i == 0 || (i && a[i] != a[i-1])) num[i] = tot++;
        else num[i] = num[i-1];

        cnt[num[i]]++;
    }
}

void dbg() {
    for (int i = 0; i < n; i++) printf("%d ", num[i]);
    printf("\n");
}

void solve(const RMQ<int> &rmq, int l, int r) {
    if (num[l] == num[r]) {
        int res = r - l + 1;
        printf("%d\n", res);
        return;
    }

    int res1 = ri[l] - l + 1, res2 = r - le[r] + 1;
    // debug(res1), debug(res2);
    int res3 = num[l] + 1 <= num[r] - 1 ? rmq.qry(num[l]+1, num[r]-1) : 0;

    int ans = max({res1, res2, res3});
    printf("%d\n", ans);
}

void init() {
    fill_v(le, 0), fill_v(ri, 0);
    fill_v(num, 0), fill_v(cnt, 0);
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d%d", &n, &q) == 2 && n) {
        init();

        for (int i = 0; i < n; i++) scanf("%d", &a[i]);

        // calc le and ri
        pre();
        RMQ<int> rmq(cnt, tot);

        // dbg();


        while (q--) {
            int l, r;
            scanf("%d%d", &l, &r);
            l--, r--;
            // rmq(l, r)
            solve(rmq, l, r);
        }
    }
}

kruskal 重构树

在处理生成树有关的问题的时候，边和点相关的一些边界条件比较难处理，一种常见的编程技巧是
建新图，将边的问题转化为点带权，如下图所示

都市的泊油路太硬

该问题的关键是快速回答多个查询，对于 $[l, r]$，需要知道在 MST 中 $l \to r$ 路径上边的最大值
可以如下处理

一开始记录节点个数为 $\text{tot}$
在执行 $\text{kruskal}$ 的时候，如果 $(u, v)$ 不在一个集合中，执行并查集合并
此时 $e(u, v)$ 是轻量级边，将其看作新的节点 $++\text{tot}$，给节点赋权值 $w(tot) = e(u, v)$
$pa(u) = pa(v) = tot$，将 $tot$ 的两个儿子置为 $u, v$，即 $G(tot, 0) = u, G(tot, 1) = v$
这样重构树就建完了，值得注意的是，不妨设最后合并的点是 $(u_0, v_0)$，重构树的根节点就是 $e(u_0, v_0) = tot$

kruskal 重构树构造完成之后，要求 $\text{maxe}(l, r)$ 瓶颈路或者最长边，就可以转为 $\textbf{dfs}$ 序
方法就是对重构树中序遍历

auto dfs = [&](int x) {
    if (x == 0) return;
    dfs(G[x][0]);
    dfn[x] = ++clock, seq[dfn[x]] = w[x];
    // 这里 w[x] 即边 (G(x, 0), G(x, 1)) 的权值
    dfs(G[x][1]);

};
dfs(tot);

另外需要注意的是，$\text{kruskal}$ 重构树需要的空间为 $O(2n)$

这样，问询 $\text{maxe}(x, y)$ 即 $x, y$ 之间路径的最长边权时
可以转换成为 $\text{dfs}$ 序数组 $\left<\text{seq} \right>$ 中的一段 $[l, r]$
$l = \text{dfn}[x], r = \text{dfn}[y]$，可以考虑用 $\textbf{rmq}$ 维护 $\text{seq}$，求最大值
如果是求第 $k$ 大点，也可以考虑用主席树等工具

Bond
算法思想是一致的，将最小生成树转为 $\text{dfs}$ 序，具体来说，$\text{dfs}(x, fa)$

• 第一次访问 $x$ 的时候，令 $\text{dfn}(x) = ++time$，同时将点的权值放入 $\text{rmq}$ 数组 $f$ 中
  令 $f(\text{dfn}(x), 0) \leftarrow w(x)$
• 然后递归执行 $x$ 的分支 $y \leftarrow G(x), \ \text{dfs}(y, x)$，回溯完成后，要接着令 $f(++time, 0) \leftarrow w(x)$
  再递归 $x$ 的另一个分支，这样就能保证两个点夹着一个边
• 编号在 $[n+1, 2n-1]$ 区间的点实际上是边，调用 $\text{dfs}(n+1, 0)$ 之后，$\text{rmq}(\text{dfn}(l), \text{dfn}(r))$ 就是答案

树上倍增处理最小生成树

Bond
最小生成树查询问题，可以使用树上倍增 + LCA 算法解决

• 首先求出原图的最小生成树，并根据最小生成树建新图 $G$，在新图上 $\text{dfs}$ 并且把无根树转为有根树
• 具体来说，$\text{dfs}(x, fa, w)$，其中 $w$ 表示进入 $x$ 这个节点的前向弧的权值，在 $\text{dfs}$ 的时候维护以下信息
  $\text{up}(u, i)$ 表示从 $u$ 节点往上 $2^{i}$ 步能够走到的节点
  $\text{maxe}(u, i)$ 表示从 $u$ 节点往上走 $2^{i}$ 个单位所经过的最长边的权值
  $d(u)$ 表示 $u$ 节点的深度，令 $ui \leftarrow up(u, i-1)$，那么有如下递推关系
  $\text{up}(u, i) = \text{up}(ui, i-1)$， $\text{maxe}(u, i) = \max (\text{maxe}(u, i-1), \text{maxe}(ui, i-1))$
  初始化 $\text{maxe}(x, 0) = w, \ \text{up}(x, 0) = fa$
• 处理每一个问询，对于 $(s, t)$，可以用倍增求 $l \leftarrow \text{LCA}(s, t)$，那么最终的答案为
  $\max (\text{path}(l, s), \text{path}(l, t))$，其中 $\text{path}(l, s)$ 表示 $l \to s$ 路径上的最大值
  这个最大值 $\text{path}(l, u)$ 同样可以用倍增来求
  先从大到小遍历深度 $i \in [\text{LOG} \to 0]$，如果 $d(\text{up}(u, i)) \geqslant d(l)$，令 $u \leftarrow \text{up}(u, i)$
  同时更新答案，$res \leftarrow \max(res, \text{maxe}(u, i))$，最后 $res$ 即为所求

朱刘算法