题解

这题可以分成两个部分来考虑，一是怎么连边最优，二是怎么计数。

连边

显然，初始边连完后产生 $n-m$ 个连通块，每个连通块里要再挑一个点和其他连通块相连，才能形成一棵树，我们考虑选哪一个点最优。

设 $f_u$ 为连通块的一个节点 $u$ 到连通块内其他所有点的距离之和，$s$ 为该连通块的大小，那么连边后该连通块对答案产生的贡献为：

$$(n-s)f_u$$

显然 $n-s$ 为定值，使 $f_u$ 最小即可。这个问题可以用换根 DP 解决，转移式为：

第一次 dfs，其中 $siz_v$ 表示子树大小：

$$f_u=\sum_{v \in son(u)} f_v+siz_v\times w_{u,v}$$

第二次 dfs：

$$f_v=f_u-siz_v\times w_{u,v}+ (s-siz_v) \times w_{u,v} $$

这是个换根 DP 的板子，不会的话可以移步这里。

tips: 取模是个好习惯，但这里 $f_u$ 是用来比较大小的，所以不能取模。

然后我们就找到了每个联通块的“代表” 点。接下来考虑怎么连。

不难猜想连出来的结构一定是个类似菊花图的东西，即所有边的一端都连在同一个点（连通块）上。因为这样，每两个连通块间最多只走两条边就能到达彼此，一定比其他方式更优。

接下来的结论是连通块大小 $s$ 越大，连的边权值越小。这也很好证明，因为该边的贡献为：

$$a_i\times s(n-s)$$

根据和一定差小积大，也就是二次函数的性质很好看出来，$s$ 越大，$s(n-s)$ 越大；即使 $s> \frac{n}{2}$，也有其他 $s'\leq n-s$，值总不会大于 $s(n-s)$，故给该联通块连更小的 $a_i$ 总是最优的。至于谁做根节点？把根节点看做自己连向自己的，边权为 $0$ 的边，根据上面的贪心，当然是最大的那个连通块啦。于是边就连完了。

计数

这就比较简单了，考虑每条边的贡献，边两端每对点的路径都要经过一次该边，所以贡献为：

$$w_{u,v}\times (n-siz_v) \times siz_v$$

跑一遍 dfs 就可以了。于是这道题做完了。

参考代码

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int mod=1e9+7;
int n,m,ans;
struct edge{
	int v,nxt,w;
}e[2000010];
int head[1000010],cnt;
void add(int u,int v,int w){
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
int a[1000010],f[1000010],siz[1000010];
bool vis[1000010];
vector<int> dot;
struct node{
	int x,siz;
	friend bool operator <(node x,node y){
		return x.siz>y.siz;
	} 
};
vector<node> lt;
void dfs(int u,int fa){
	siz[u]=1,vis[u]=1;
	dot.push_back(u);
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v,w=e[i].w;
		if(v==fa) continue;
		dfs(v,u);
		siz[u]+=siz[v];
		f[u]=f[u]+f[v]+siz[v]*w;
	}
}
void dp(int u,int fa){
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v,w=e[i].w;
		if(v==fa) continue;
		f[v]=f[u]-(w*(siz[v]))+w*(dot.size()-siz[v]);
		dp(v,u);
	}
} 
void work(int x){
	dot.clear();
	dfs(x,0);
	dp(x,0);
	int zx=0,mx=1e18;
	for(auto u:dot) if(f[u]<mx) zx=u,mx=f[u];
	lt.push_back(node{zx,dot.size()});
}
void cal(int u,int fa){
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v,w=e[i].w;
		if(v==fa) continue;
		int plus=((w*siz[v]*(n-siz[v]))%mod+mod)%mod; 
		ans+=plus;
		ans%=mod;
		cal(v,u);
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;cin>>u>>v>>w;
		add(u,v,w),add(v,u,w);
	}
	for(int i=1;i<=n-m-1;i++) cin>>a[i];
	sort(a+1,a+n-m);
	for(int i=1;i<=n;i++) if(!vis[i]) work(i);
	sort(lt.begin(),lt.end());
	for(int i=1;i<lt.size();i++){
		add(lt[0].x,lt[i].x,a[i]);
		add(lt[i].x,lt[0].x,a[i]);
	}
	dfs(lt[0].x,0);
	cal(lt[0].x,0);
	cout<<(ans+mod)%mod<<endl;
	return 0;
}