题解：P12007 【MX-X10-T3】[LSOT-4] 全国联赛？

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll p = 1e9 + 7;
ll n, m;
vector <pair <ll, ll>> adj[1000005];
ll dp[1000005];
ll siz[1000005];
ll a[1000005];
ll zx, ans;
void dcd(ll u, ll fa)
{
	siz[u] = 1;
	for(auto it:adj[u])
	{
		if(it.first != fa)
		{
			dcd(it.first, u);
			siz[u] += siz[it.first];
			dp[u] += siz[it.first] * it.second + dp[it.first];
		}
	}
}
void dcu(ll u, ll fa)
{
	zx = min(zx, dp[u]);
	for(auto it:adj[u])
	{
		if(it.first != fa)
		{
			ans += siz[it.first] * (siz[u] - siz[it.first]) % p * it.second % p;
			ans %= p;
			dp[it.first] += (dp[u] - dp[it.first] - siz[it.first] * it.second + (siz[u] - siz[it.first]) * it.second);
			siz[it.first] = siz[u];
			dcu(it.first, u);
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);     cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= m; i++)
	{
		ll u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	vector <ll> v;
	for(int i = 1; i <= n; i++)
	{
		if(!siz[i])
		{
			zx = 0x7f7f7f7f7f7f7f7f;
			dcd(i, 0);
			dcu(i, 0);
			zx %= p;
			ans += zx * (n - siz[i]) % p;
			ans %= p;
			v.push_back(siz[i]);
		}
	}
	sort(v.begin(), v.end());
	for(int i = 1; i <= n - 1 - m; i++)
		cin >> a[i];
	sort(a + 1, a + n - m, greater <ll>());
	for(int i = 1; i <= n - m - 1; i++)
	{
		ans += a[i] * v[i - 1] % p * (n - v[i - 1]) % p;
		ans %= p;
	}
	cout << ans;
	return 0;
}