AcWing 356 次小生成树

题目传送门

一、分析

本题要求严格的次小生成树，之前在里也曾求过次小生成树，但是本题的数据范围更大，对时间复杂度的要求也更高。

秘密的牛奶运输的的性能为什么可以优化呢？这是因为每次执行\(dfs\)求最小生成树上两点路径中的最大和次大边权的时间复杂度是\(O(n)\)，总的时间复杂度就是\(O(n^2)\)，求任意两点间的最短距离可以想办法优化一下。

\(LCA\)的树上倍增法可以优化！树上倍增法的详细介绍见。
因为树上倍增法可以求出树上任意两点间的最短距离，扩展一下也可以求也次短距离，而且是\(O(log_2n)\)级别的，比上面的\(O(n)\)快。

二、思路

设\(d[i][k]\)表示树上的某节点\(i\)向上走\(2^k\)步到达的节点，则状态转移方程为\(d[i][k] = d[d[i][k-1]][k-1]\)，设\(j = d[i][k-1]\)，则状态转移方程表示为\(d[i][k] = d[j][k-1]\)，直观的理解就是要想到达离\(i\)距离为\(2^k\)的节点，只需要先走\(2^{k-1}\)步到达\(j\)节点，再从\(j\)节点走\(2^{k-1}\)步就到达了目的节点。

设\(f[i][k]\)表示\(i\)到\(d[i][k]\)节点路径上的最大边权、次大边权，显然\(f[i][k].first = max(f[i][k-1].first,f[j][k-1].first)\)，也就是\(i\)到\(d[i][k]\)一共有\(2^k\)条边，边权的最大值是\(i\)到\(j\)中边权的最大值与\(j\)到\(d[i][k]\)中边权的最大值中的较大者。\(f[i][k].second\)的求解就需要分情况讨论了：
\(f[i][k-1].first == f[j][k-1].first\)时，\(f[i][k].second = max(f[i][k-1].second,f[j][k-1].second)\)
\(f[i][k-1].first > f[j][k-1].first\)时，\(f[i][k].second = max(f[i][k-1].second,f[j][k-1].first)\)
\(f[i][k-1].first < f[j][k-1].first\)时，\(f[i][k].second = max(f[i][k-1].first,f[j][k-1].second)\)

也就是 * $i$到$j$的边权最大值等于$j$到$d[i][k]$的边权最大值时，$i$到$d[i][k]$的次大边权为$i$到$j$的边权次大值与$j$到$d[i][k]$的边权次大值中较大者； * $i$到$j$的边权最大值大于$j$到$d[i][k]$的边权最大值时，$i$到$d[i][k]$的次大边权为$i$到$j$的边权次大值与$j$到$d[i][k]$的边权最大值中较大者； * $i$到$j$的边权最大值小于$j$到$d[i][k]$的边权最大值时，$i$到$d[i][k]$的次大边权为$i$到$j$的边权次大值与$j$到$d[i][k]$的边权最大值中较大者。

求出了树上任意一点向上走\(2^k\)步路径中的最大边权和次大边权并不是求解本题的终点，我们需要的是求解树上任意两点间的最大边权和次大边权。

回忆下求节点\(a\)和节点\(b\)的\(LCA\)的过程，我们先将深度较大的\(a\)节点不断向上跳，直到跳到与\(b\)节点同一深度为止，如果此时\(a\)与\(b\)不重合，则继续将\(a\)和\(b\)以同样的步数向上跳，直到\(a\)和\(b\)的父节点是同一个为止。

求\(LCA\)的树上倍增的过程也可以用来求最大和次大边权，只需要在跳的过程中同步更新最大边权和次大边权即可。

使用树上倍增法求解树上两点路径中的最大边权和次大边权的时间复杂度降低到了\(O（logn）\)，只需要再加上图和树的存储代码以及\(kruskal\)算法的并查集代码就可以了，总的代码如下：

三、实现代码

#include 
using namespace std;
typedef long long LL;
const int N = 100010, M = 300010;
const int INF = 0x3f3f3f3f;
typedef pair PII;
int f[N][16];    // f[i][k]表示树上的某节点i向上走2^k步到达的节点
PII d[N][16];    // d[i][k]表示树上的某节点i向上走2^k步到达的节点最长距离和次长距离
int depth[N];    //深度数组

// Kruskal用的结构体
struct Edge {
    int a, b, c; //从a到b边权为c
    bool flag;   //是不是最小生成树的树边
    bool operator<(const Edge &ed) const {
        return c < ed.c;
    }
} edge[M];

//邻接表
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
//并查集
int p[N];
int find(int x) {
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

//树上倍增求任意两点最短距离
int bfs(int u) {
    queue q;
    q.push(u);
    depth[u] = 1;
    while (q.size()) {
        int t = q.front();
        q.pop();
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (!depth[j]) {
                q.push(j);
                depth[j] = depth[t] + 1;        //记录深度
                f[j][0] = t;                    //记录2^0->t,描述父节点

                //下面是与普通的倍增不一样的代码，记录两点间最大长度与次大长度
                /*->->->->->->->->->->->->->->->->->->->->*/
                d[j][0] = {w[i], -INF}; // j->t 的最大距离与次大距离
                /*->->->->->->->->->->->->->->->->->->->->*/

                for (int k = 1; k <= 15; k++) { //倍增
                    int v = f[j][k - 1];        // 设j跳2 ^(k-1)到达的是v点
                    f[j][k] = f[v][k - 1];      // v点跳 2^(k-1)到达的终点就是j跳2^k的终点

                    /*->->->->->->->->->->->->->->->->->->->->*/
                    //最大边权一定是两个线段中最长边权的最大值
                    d[j][k].first = max(d[j][k - 1].first, d[v][k - 1].first);
                    //次大边权分情况讨论
                    //如果前半段的最大值 小于 后半段的最大值
                    if (d[j][k - 1].first < d[v][k - 1].first)
                        //次大值 等于 max(前半段最大值,后半段次大值)
                        d[j][k].second = max(d[j][k - 1].first, d[v][k - 1].second);
                    //如果前半段的最大值 等于 后半段的最大值
                    else if (d[j][k - 1].first == d[v][k - 1].first)
                        //次大值 等于 max(前半段次大值,后半段次大值)
                        d[j][k].second = max(d[j][k - 1].second, d[v][k - 1].second);
                    //如果前半段的最大值 大于 后半段的最大值
                    else
                        //次大值 等于 max(前半段次大值,后半段的最大值)
                        d[j][k].second = max(d[j][k - 1].second, d[v][k - 1].first);
                    /*->->->->->->->->->->->->->->->->->->->->*/
                }
            }
        }
    }
}
//因为同时需要同步修改最大值和次大值，所以采用了地址符&引用方式定义参数
// m1:最大值，m2：次大值
void cmp(int &m1, int &m2, PII x) {
    if (m1 < x.first)
        m2 = max(m1, x.second), m1 = x.first;
    else if (m1 == x.first)
        m2 = max(m2, x.second);
    else
        m2 = max(m2, x.first);
}
// 最近公共祖先
// 由a->b的边,边权是w
// 返回值：如果加上这条边w，去掉最小生成树中的某条边(m1或m2)，得到一个待选的次小生成树
// 此时的 w- m1 或者 w-m2的值是多少。
// 具体是-m1,还是-m2，要区别对待，因为如果w=m1,就是-m2,否则就是-m1
// 利用倍增的思想，对bfs已经打好的表 d数组和f数组 进行快速查询
// 找出a->b之间的最大距离和次大距离
int lca(int a, int b, int w) {
    if (depth[a] < depth[b]) swap(a, b); //保证a的深度大于b的深度
    /*->->->->->->->->->->->->->->->->->->->->*/
    int m1 = -INF, m2 = -INF; //最大边，次大边初始化
    /*->->->->->->->->->->->->->->->->->->->->*/
    for (int k = 15; k >= 0; k--)         //由小到大尝试
        if (depth[f[a][k]] >= depth[b]) { //让a向上跳2^k步
            /*->->->->->->->->->->->->->->->->->->->->*/
            cmp(m1, m2, d[a][k]); // a向上跳2^k步时，走过的路径中可能存在最大边或次大边
            /*->->->->->->->->->->->->->->->->->->->->*/
            a = f[a][k]; //标准的lca
        }

    //当a与b不是同一个点时，此时两者必须是depth一样的情况，同时向上查询2^k，必然可以找到LCA
    if (a != b) {
        for (int k = 15; k >= 0; k--)
            if (f[a][k] != f[b][k]) {
                /*->->->->->->->->->->->->->->->->->->->->*/
                cmp(m1, m2, d[a][k]); // a向上跳2^k步时，走过的路径中可能存在最大边或次大边
                cmp(m1, m2, d[b][k]); // b向上跳2^k步时，走过的路径中可能存在最大边或次大边
                /*->->->->->->->->->->->->->->->->->->->->*/
                a = f[a][k], b = f[b][k];
            }
        /*->->->->->->->->->->->->->->->->->->->->*/
        // 此时a和b到lca下同一层 所以还要各跳1步=跳2^0步
        cmp(m1, m2, d[a][0]);
        cmp(m1, m2, d[b][0]);
        /*->->->->->->->->->->->->->->->->->->->->*/
    }
    return w == m1 ? w - m2 : w - m1;
}
int main() {
    int n, m, a, b, c;
    cin >> n >> m;

    //并查集初始化
    for (int i = 1; i <= n; i++) p[i] = i;
    //邻接表初始化
    memset(h, -1, sizeof h);
    // Kruskal
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        edge[i] = {a, b, c, false};
    }
    //按边权排序+最小生成树
    sort(edge, edge + m);
    LL sum = 0, ans = 1e18;
    for (int i = 0; i < m; i++) {
        a = find(edge[i].a), b = find(edge[i].b), c = edge[i].c;
        if (a != b) {
            p[a] = b;
            sum += c;
            edge[i].flag = true; //树边
            //将最小生成树中的树边单独构建一个图出来
            add(edge[i].a, edge[i].b, c), add(edge[i].b, edge[i].a, c);
        }
    }

    //倍增,记录任意点到2^k点的最大值，次大值，深度等信息，一会后面lca会用到这些信息
    //是一个预处理的过程,打表
    bfs(1);

    //回到了奶牛那道题的逻辑，用非树边去尝试替换最小生成树中的边，然后取min
    // lca查表
    for (int i = 0; i < m; i++)
        if (!edge[i].flag) { //枚举非树边
            a = edge[i].a, b = edge[i].b, c = edge[i].c;
            ans = min(ans, sum + lca(a, b, c));
        }
    printf("%lld\n", ans);
    return 0;
}