AcWing 346. Solution to the problem of water splashing festival in the corridor (deduction formula, minimum spanning tree)

AcWing 346. Corridor Water Splashing Festival
The key to solving the problem is to deduce the formula ：**(Size[a] * Size[b] - 1) * (w + 1)** The meaning of this formula is mortgage ： Traverse to two points belonging to two different connected blocks connected by a certain edge , Connect all points of the two connecting blocks to each other , Subtract an existing edge , After introducing the formula , Traverse all edges according to the algorithm of minimum spanning tree , Find out two points that are not in a connected block and accumulate the calculated value with a formula

#include<bits/stdc++.h>

using namespace std;

const int N = 6010;

struct Edge{
    
	int a, b, w;
	bool operator< (const Edge &t) const {
    
		return w < t.w;
	}
}e[N * 4];

int T, n, m;
int p[N];
int Size[N];

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

int main()
{
    
	cin>>T;
	while(T -- ){
    
		cin>>n;
		int res = 0;
		for(int i = 0; i < n - 1; i ++ ){
    
			int a, b, w;
			cin>>a>>b>>w;
			e[i] = {
    a, b, w};
		}
		// Initialize and query array  
		for(int i = 1; i <= n; i ++ ){
    
			p[i] = i;
			Size[i] = 1;
		}
		
		sort(e, e + n - 1);
		
		for(int i = 0; i < n - 1; i ++ ){
    
			int a = find(e[i].a), b = find(e[i].b), w = e[i].w;
			if(a != b){
    
				res += (Size[a] * Size[b] - 1) * (w + 1);  // The formula , Connect all points of the two connecting blocks to each other , Subtract an existing edge  
				p[a] = b;
				Size[b] += Size[a]; 
			}
		}
		cout<<res<<endl;
	}
	return 0;
}