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

· · 题解

分析题目

首先题目要求把一个森林通过加一些固定的权值的边来得到一棵树，使得树上的点两两的距离之和是最小的。那么为了使得合并之后点两两之间距离和最小，只能去考虑合并两棵带权树的重心。可以发现如果把原来森林里的每一棵树用它的重心表示，则最后的图是一个菊花图。而且为了使得点两两之间距离和最小要把最大的树放在菊花图的中心，次大的用最小的边连接，最小的用最长的边连接，即可。所以换根 DP 求出重心再按照上述策略合并并求出答案。

代码

#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;
}