题解 | #Forsaken喜欢独一无二的树#

貌似看起来没几个用kruskal重构树来写该题的

那就直接来一发kruskal重构树的题解

建议学习完kruskal重构树知识点后再来阅读本题解更佳

核心思想在于建完图后，枚举未被选入构成最小生成树的边，利用该边两端点间最小瓶颈路径判断是否需要删除该边

时间复杂度大概是O(Mlog2N)级别的（不太会算只能算个大概QWQ）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+7;
int n,m,fa[maxn*2],p[maxn*2][21],dep[maxn*2];
ll val[maxn*2],ans;
map<int,bool>mp;

struct node{
	int u,v;
	ll w;
}e[maxn];

bool cmp(node a,node b){
	return a.w<b.w;
}

vector<int>G[maxn*2];

void init(){
	for(int i=1;i<=2*n;i++)fa[i]=i;
}

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

void dfs(int u,int f){
	dep[u]=dep[f]+1;
	p[u][0]=f;
	for(int i=1;i<=20;i++)p[u][i]=p[p[u][i-1]][i-1];
	for(int i=0;i<G[u].size();i++){
		int v=G[u][i];
		dfs(v,u);
	}
}

int lca(int a,int b){
	if(dep[a]>dep[b])swap(a,b);
	for(int i=20;i>=0;i--)if(dep[a]<=dep[b]-(1<<i))b=p[b][i];
	if(a==b)return a;
	for(int i=20;i>=0;i--)
		if(p[a][i]!=p[b][i])a=p[a][i],b=p[b][i];
	return p[a][0];
}

int main(){
	scanf("%d%d",&n,&m);
	init();
	int cnt=n;
	for(int i=1;i<=m;i++)scanf("%d%d%lld",&e[i].u,&e[i].v,&e[i].w);
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++){
		int fx=find(e[i].u),fy=find(e[i].v);
		if(fx!=fy){
			mp[i]=1;
			fa[fx]=fa[fy]=++cnt;
			G[cnt].push_back(fx);
			G[cnt].push_back(fy);
			val[cnt]=e[i].w;
		}
		if(cnt==2*n-1)break;
	}
	dfs(cnt,0);
	for(int i=1;i<=m;i++){
		if(mp[i])continue;
		if(e[i].w==val[lca(e[i].u,e[i].v)])ans+=e[i].w;
	}
	cout<<ans;
	return 0;
}