最近公共祖先——AcWing 356. 次小生成树

最近公共祖先

定义

最近公共祖先（Lowest Common Ancestor, LCA）是在一棵有根树中，对于两个节点 u和 v，LCA 是所有公共祖先中深度最大的一个节点。换句话说，LCA 是 u 和 v的共同祖先中距离根节点最远的一个。

运用情况

• 最短路径问题：在树中，求两节点间的最短路径，可以先找到它们的 LCA，然后通过 LCA 计算路径长度。
• 区间查询：在树状结构中进行区间查询，如统计区间内某些属性的总和或最小值。
• 动态规划：在解决一些树上的动态规划问题时，LCA 可以帮助确定状态转移的方向。
• 并查集和树链剖分：在这些数据结构中，LCA 可以用来优化查询效率。

注意事项

1. 树必须是有根的：LCA 的概念在有根树中才有意义，因为“祖先”这一概念依赖于树的根。
2. 节点可以是自己的祖先：在 LCA 的定义中，一个节点可以是它自己的祖先。
3. LCA 的唯一性：对于任意两个节点，LCA 都是唯一的。
4. 性能考量：在多次查询 LCA 的情况下，预处理可以显著提升查询速度，但是会消耗额外的内存。

解题思路

求解 LCA 问题有多种算法：

• DFS+RMQ（深度优先搜索+区间最小值查询）：先进行 DFS 构建树的高度信息，然后将 LCA 问题转化为 RMQ 问题。
• 倍增法：预先计算每个节点 2^k层之上的祖先，然后通过二进制搜索找到 LCA。
• Tarjan 算法：使用线性时间复杂度的算法，通过深度优先遍历同时维护栈和访问状态来找到 LCA。
• HLD（重链剖分）：将树分割成一系列链，然后在链上进行查询，适用于处理 LCA 和区间查询问题。

示例算法：倍增法

1. 预处理：使用动态规划的思想，对于每个节点 u，预计算 u 节点 2^k 层以上的祖先 dp[u][k]，其中 k 从 0 开始，直到 2^k大于树的高度。
2. 查询 LCA：给定两个节点 u和 v，先使它们处于同一深度，然后从高次幂开始逐级向上比较，直到找到最近的公共祖先。

倍增法的时间复杂度为 O( N log N)每次查询，预处理的时间复杂度为 O(N log N)，空间复杂度为 O(N log N)。

AcWing 356. 次小生成树

题目描述

356. 次小生成树 - AcWing题库

运行代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010, M = 300010, INF = 0x3f3f3f3f;

int n, m;
struct Edge
{
    int a, b, w;
    bool used;
    bool operator < (const Edge &t) const 
    {
        return w < t.w;
    }
}edge[M];
int q[N], p[N];
int h[N], e[M], ne[M], w[M], idx;
int depth[N], fa[N][17], d1[N][17], d2[N][17];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

LL kruskal()
{
    LL res = 0;
    for(int i = 1; i <= n; i ++ ) p[i] =i;
    sort(edge, edge + m);
    
    for(int i = 0; i < m; i ++ )
    {
        int a = find(edge[i].a), b = find(edge[i].b), w = edge[i].w;
        if(a != b)
        {
            p[a] = b;
            res += w;
            edge[i].used = true;
        }
    }
    
    return res;
}

void build()
{
    memset(h, -1, sizeof h);
    
    for(int i = 0; i < m; i ++ )
        if(edge[i].used)
        {
            int a = edge[i].a, b = edge[i].b, w = edge[i].w;
            add(a, b, w);
            add(b, a, w);
        }
}

void bfs()
{
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[1] = 1;
    q[0] = 1;
    
    int hh = 0, tt = 0;
    while(hh <= tt)
    {
        int t = q[hh ++ ];
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(depth[j] > depth[t] + 1)
            {
                depth[j] = depth[t] + 1;
                q[ ++ tt] = j;
                fa[j][0] = t;
                d1[j][0] = w[i], d2[j][0] = -INF;
                for(int k = 1; k <= 16; k ++ )
                {
                    int anc = fa[j][k - 1];
                    fa[j][k] = fa[anc][k - 1];
                    d1[j][k] = d2[j][k] = -INF;
                    int distance[4] = {d1[j][k - 1], d2[j][k - 1], d1[anc][k - 1], d2[anc][k - 1]};
                    for(int u = 0; u < 4; u ++ )
                    {
                        int d = distance[u];
                        if(d > d1[j][k]) d2[j][k] = d1[j][k], d1[j][k] = d;
                        else if(d != d1[j][k] && d > d2[j][k]) d2[j][k] = d;
                    }
                }
            }
        }
    }
}

int lca(int a, int b, int w)
{
    int distance[1000];
    int cnt = 0;
    
    if(depth[a] < depth[b]) swap(a, b);
    
    for(int k = 16; k >= 0; k -- )
        if(depth[fa[a][k]] >= depth[b])
        {
            distance[cnt ++ ] = d1[a][k];
            distance[cnt ++ ] = d2[a][k];
            a = fa[a][k];
        }
    
    if(a != b)
    {
        for(int k = 16; k >= 0; k -- )
            if(fa[a][k] != fa[b][k])
            {
                distance[cnt ++ ] = d1[a][k];
                distance[cnt ++ ] = d2[a][k];
                distance[cnt ++ ] = d1[b][k];
                distance[cnt ++ ] = d2[b][k];
                a = fa[a][k], b = fa[b][k];
            }
        distance[cnt ++ ] = d1[a][0];
        distance[cnt ++ ] = d1[b][0];
    }
    
    int dist1 = -INF, dist2 = -INF;
    
    for(int i = 0; i < cnt; i ++ )
    {
        int d = distance[i];
        if(d > dist1) dist2 = dist1, dist1 = d;
        else if(d != dist1 && d > dist2) dist2 = d;
    }
    
    if(w > dist1) return w - dist1;
    if(w > dist2) return w - dist2;
    return INF;
}

int main()
{
    cin >> n >> m;
    
    for(int i = 0; i < m; i ++ )
    {
        int a, b, w;
        cin >> a >> b >> w;
        edge[i] = {a, b, w};
    }
    
    LL sum = kruskal();
    
    build();
    
    bfs();
    
    LL res = 1e18;
    for(int i = 0; i < m; i ++ )
        if(!edge[i].used)
        {
            int a = edge[i].a, b = edge[i].b, w = edge[i].w;
            res = min(res, sum + lca(a, b, w));
        }
        
    cout << res << endl;
    
    return 0;
}

代码思路

1. Kruskal算法：首先通过Kruskal算法找到最小生成树，计算其边的总权重。
2. 构建图：基于最小生成树的边构建邻接表。
3. BFS遍历：进行广度优先遍历来初始化深度、父节点以及用于LCA查询的跳跃表。
4. LCA查询：实现一个LCA查询函数，用于找到两个节点的最近公共祖先，并返回连接这两个节点的边的最大和次大权重。
5. 计算结果：遍历所有非最小生成树的边，对于每条边，使用LCA查询计算如果将其加入最小生成树后，生成树的最大边权重变化，从而找到最小的可能变化。

改进思路

1. 数据结构优化：可以考虑使用更高效的数据结构来存储图和查询LCA，如使用STL容器代替手动管理数组。
2. 算法优化：在LCA查询中，可以进一步优化跳跃表的使用，减少不必要的计算，例如，可以预先计算每个节点到其祖先的路径上的最大和次大边权重，从而避免在查询时重复计算。
3. I/O优化：使用更快的输入输出方式，如scanf和printf，减少I/O开销。
4. 错误处理：增加对输入数据的合法性检查，确保程序的健壮性。