并查集

将边升序排列，两个连通图之间增加(p*q-1)条边，最小增加的权值为（w+1）。

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 6010;
int n;
int father[N], num[N];
int ans;
struct edge{
	int from, to, weight;
	bool operator <( const edge b)const{
		return weight < b.weight;
	}
}Edge[N];
void init(){
	for (int i = 1; i <= n; i++){
		father[i] = i;
		num[i] = 1;
	}
}
int findfather(int x){
	while (x != father[x]){
		x = father[x];
	}
	return father[x];
}
int main(){
	int t;
	cin >> t;
	while (t--){
		cin >> n ;
		init();
		for (int i = 1; i < n ; i++){
			cin >> Edge[i].from >> Edge[i].to >> Edge[i].weight;
		}
		ans = 0;
		sort(Edge, Edge + n);

		for (int i = 1; i < n; i++){
			int x = findfather(Edge[i].from); int y = findfather(Edge[i].to);

			ans += (num[x] * num[y] - 1)*(Edge[i].weight+1);

			father[x] = y;
			num[y] += num[x];
		}

		cout << ans << endl;
	}
	ret...