30pts求助
查看原帖
30pts求助
1256325
XYHLYCHRIS楼主2024/11/6 21:44
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll NUM = 2e5 + 10;
ll n, k, sum, fa[NUM], enm[NUM];
struct FTW {ll f, t, w;} e[NUM];
bool cmp(FTW a, FTW b) {return a.w > b.w;}
ll FF(ll x) {
	if(enm[x]) enm[fa[x]] = 1;  
	return fa[x] == x? x: fa[x] = FF(fa[x]);
}
int main() {
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
	cin >> n >> k;
	for (ll tmp, i = 1; i <= k; i++) cin >> tmp, enm[tmp] = 1;
	for (ll i = 1; i <= n; i++) fa[i] = i;
	for (ll i = 1; i < n; i++) cin >> e[i].f >> e[i].t >> e[i].w, sum += e[i].w;
	sort (e + 1, e + n, cmp);
	for (ll i = 1; i < n; i++) {
		ll fu = FF(e[i].f), fv = FF(e[i].t);
		fa[fu] = fv, enm[fu] && enm[fv]? sum -= 0: sum -= e[i].w;
	}
	cout << sum;
	return 0;
}
2024/11/6 21:44
加载中...