[蓝桥杯 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;
}