[蓝桥杯 2023 省 A] 网络稳定性

题目来自DOTCPP：

 思路：

①由于题目没有告诉我们成树形结构，可能成环。因此，我们要自己构建树。

②本体我们通过kruskal重构树，按边权从大到小排序，那么查询的两个点的最近公共祖先权值就是答案。

③在通过树链剖分找到树上两个节点的最近公共祖先 ，就能找到答案了。

代码实现：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5+20;

int n, m, q;
//kruskal重构树
struct edge{//记录边的信息
    int u, v, w;
}e[N];
vector<int> t[N];//记录重构的树
int fa[N];//判断两个点是否联通，可以建树
int val[N]; //用来记录这个点的点权

//找到x根节点
int find(int x){
    if(fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

//重构树
void kruskal(){
    //对fa初始化，每个节点父节点为本身
    for(int i = 1; i <= 2*n; i++)fa[i] = i;
    //对e根据e.w排序，根据题目决定大到小/小到大
    sort(e, e+m, [&](edge x, edge y){return x.w > y.w;});
    //新节点 
    int idx = n;
    
    for(int i = 0; i < m; i++){
        //取出节点
        int x = e[i].u, y = e[i].v;
        //找到节点顶点
        int xx = find(x), yy = find(y);
        //如果两个节点在一个集合中，跳过
        if(xx == yy) continue;
        idx++;//新节点+1
        //指向父节点
        fa[xx] = fa[yy] = idx;
        //记录这课树
        t[idx].push_back(xx);
        t[idx].push_back(yy);
        //更新这个点的权值
        val[idx] = e[i].w;
    }
}

//树链剖分
int fa1[N], sz[N], dep[N], son[N], top[N];

void dfs1(int u, int father){
    fa1[u] = father, dep[u] = dep[father] +1, sz[u] = 1;
    for(auto v: t[u]){
        if(v == fa1[u]) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if(sz[son[u]] < sz[v]) son[u] = v;
    }
}

void dfs2(int u, int tt){
    top[u] = tt;
    if(!son[u])return;
    dfs2(son[u], tt);
    
    for(auto v: t[u]){
        if(v == fa1[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

int lca(int u, int v){
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        u = fa1[top[u]];
    }
    return dep[u] < dep[v] ? u:v;
}

signed main(){
    scanf("%lld %lld %lld", &n, &m, &q);
    for(int i = 0; i < m; i++){
        scanf("%lld %lld %lld", &e[i].u, &e[i].v, &e[i].w);
    }
    //开始重构树
    kruskal();
    //对树预处理，要找到树的顶点
    for(int i = 1; i <= 2*n; i++){
        if(fa[i] == i){
            //树链剖分预处理模板
            dfs1(i, 0);
            dfs2(i, i);
        }
    }
    
    //输出询问的答案
    while(q--){
        //找到 x,y的根节点，判断是否在一个集合下
        int x, y; scanf("%lld %lld", &x, &y);
        int xx = find(x), yy = find(y);
        if(xx != yy) printf("-1\n");
        else{
            //找到x，y最近公共祖先
            int ans = lca(x, y);
            //ans的点权就是答案
            printf("%lld\n", val[ans]);
        }
    }
    return 0;
}