https://codeforces.com/contest/2021/problem/E3
题意：n个点，m条边。p个点需要“互联网”，有k个服务器。每个点的延迟是到服务器的最大边权。对k=1,2,3,,,n求最小延迟和。

1.如果构造一个MST，比MST更大的边肯定用不上。
2.构造MST的过程中，如果将连通分量A和连通分量B合并，如果在连通分量A里放一个服务器，那么连通分量B的延迟和就是$siz[B]*w$。（siz数组是连通分量B所含的需要网的点的数量，w是构造MST时正在遍历的边）。因此思路不能以点为单位思考，应该以连通分量为单位思考。
3.因此在构造MST的过程中，合并两个连通分量A，B时，构造一个新顶点C，将A，B合并到C上，并记录边A->C B->C。
4.此时多加一个服务器，就可以抽象为将一个连通分量一分为二。这个划分肯定是从大的连通分量开始划分，比如A和B连成C，肯定先把C一分为二之后再考虑划不划分A、B。然后dp状态如果按照固有思维应该是以i为根的子树安排j个服务器的最小延迟，但是根本做不了状态转移，也开不了那么大的空间。
5.考虑一个dp状态为将连通分量X中安排一个服务器后，能减少的最大的延迟和。再考虑与状态转移相关的问题，对于连通分量X，如果不在其中安排服务器，则转移到它的父节点，延迟要多出$(w_{fa}-w_{x})*siz[X]$。反过来想，如果在X中安排一个服务器，就能多剩下这么多延迟。然后对于构成X的两个连通分量M和N，dp[X]应该是$max(dp[M],dp[N])+(w_{fa}-w_{x})*siz[X]$。
6.最后我们考虑答案该怎么算，dp[root]应是对所有点划分一次即有一个服务器后能省下的延迟，那一次不划分的延迟是多少。考虑其意义，为所有点连成一个连通分量后的延迟和，即$siz[root] * W$，W即最小生成树最后一条边（以下叙述，对连通分量X，以W[x]表示构成这个连通分量时的边权）。
7.则k=1时，答案为tot-dp[root]。接着考虑第二次划分，设构成root的两个连通分量为M，N。则第一个安排的服务器一定在M或N中，具体在哪个连通分量由dp值的意义可看出，服务器一定在dp值更大的那个连通分量中，递归向下我们能知道第一个服务器被安排在了哪个节点。由于我们dp的定义是在该连通分量中安排一个服务器能剩下的最大延迟，则接下来第二次划分一定得在一个没有被安排过服务器的地方。假设第一次服务器安排在N中，则这样的连通分量有M、N的子节点Nl(假设服务器在Nr中)、Nr的子节点Nrl(假设服务器在Nrr中)······然后我们应该找个dp值最大的划分。
8.注意到这些连通分量，都是和兄弟节点dp值中较小的那个。且对从下往上的每一条路径，dp值都是非严格递增的。所以我们直接在dp过程中，用一个vector存储子节点中更小的dp值，更大的dp值不存储而是往上传去更新上面的节点。最后到根节点的时候多存储一下根节点的dp值。然后把这个vector从大到小排序。答案就是$tot-vector[0]、tot-vector[1]·····$

ps.代码中weight[x]为合并成连通分量x的边权。siz为该连通分量中需要网的节点数量。dp值以生成树的边权形式存储。

#include<bits/stdc++.h>

#define MULTI_TEST

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

struct DSU {
    std::vector<int> f, siz;

    DSU() {}
    DSU(int n) {
        init(n);
    }

    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }

    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }

    int size(int x) {
        return siz[find(x)];
    }
};
struct Edge{
    int u,v,w;
    bool operator < (const Edge& rhs) const{
        return w < rhs.w;
    }
};
int n,m,p;
vector<int> s;
vector<Edge> edges;
void solve(){
    cin>>n>>m>>p;
    s.resize(p); edges.resize(m);
    for(int i=0;i<p;i++) cin>>s[i],s[i]--;
    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w; u--,v--;
        edges[i] = {u,v,w};
    }
    sort(edges.begin(),edges.end());

    //板子下标是从0开始的,所以上面所有点的下标全部--
    DSU dsu(2*n-1);
    vector<vector<int>> adj(2*n-1);
    vector<ll> weight(2*n-1);
    vector<ll> siz(2*n-1,0);
    int cnt = n;
    for(auto &[u,v,w]:edges){
        if(dsu.same(u,v)) continue;
        int x = cnt++;
        int rv = dsu.find(v),ru = dsu.find(u);
        adj[x].push_back(ru);
        adj[x].push_back(rv);
        weight[x] = w;
        dsu.merge(x,u);
        dsu.merge(x,v);
    }
    vector<ll> a;
    for(auto x:s) siz[x]++;
    auto dfs = [&](auto &self,int u,int fa)-> ll{
        ll ans = 0;
        for(auto v:adj[u]){
            ll res = self(self,v,u);
            siz[u] += siz[v];
            if(res > ans){
                swap(res,ans);
            }
            a.push_back(res);
        }
        if(fa!=-1){
            ans += 1ll * siz[u]*(weight[fa]-weight[u]);
        }
        return ans;
    };
    int rt = cnt-1;
    a.push_back(dfs(dfs,rt,-1));
    sort(a.begin(),a.end(),greater());
    a.resize(n);
    ll ans = 1ll*p * weight[rt];
    for(int i=0;i<n;i++){
        ans -= a[i];
        cout<<ans<<" ";
    }
    cout<<endl;

}

int main(){     
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);
    int T = 1;
#ifdef MULTI_TEST
    cin>>T;
#endif
    while(T--){
        solve();
    }
    return 0;
}