这是由 AI 翻译为中文文本的官方题解

子任务 1

确定首都之后的操作，即为寻找带权无向图的最小生成树的算法，被称为“Prim 算法”。Prim 算法通过使用 priority queue 等数据结构，可以在单次 $O(M \log M)$ 的时间复杂度内执行。将此操作对 $N$ 种首都情况分别进行，计算复杂度为 $O(NM \log M)$。

子任务 2

由于 Prim 算法是求解最小生成树的算法，如果存在某条边使得有新的顶点变得可达，那么这条边必定包含在最小生成树中。因此，可以忽略不包含在最小生成树中的边。首先求出最小生成树，然后在该图上改变起点为 $N$ 种情况执行 Prim 算法，计算复杂度变为 $O(N^2 \log N)$。

子任务 3

从 $s$ 出发可达的岛屿集合始终构成一个区间。 考虑 $s < i$ 的情况，当从 $s$ 可以到达 $i$ 时，存在某个 $j$（$j \le s$），使得从 $j$ 到 $i$ 的区间都是可达的。这个 $j$ 的值是，设 $s$ 到 $i$ 路径上边的最大权值为 $m$，从 $s$ 开始向编号较小的方向查看时，第一次出现权值大于 $m$ 的边的位置。固定 $i$，当 $s$ 的编号逐渐减小时，$j$ 的编号也会同样逐渐减小。因此，利用尺取法（双指针）的要领，可以依次求出 $s = i - 1, i - 2, \dots, 1$ 对应的 $j$ 的值。利用同样的方法也可以计算 $s = i + 1, i + 2, \dots, N$ 的情况，计算复杂度为 $O(NQ)$。

子任务 4, 5，满分解法

考虑与 Prim 算法齐名的另一种求解最小生成树的算法——Kruskal 算法。

假设在 Kruskal 算法的某一步中，连通分量 $A$ 和连通分量 $B$ 通过连接 $A$ 中顶点 $x$ 和 $B$ 中顶点 $y$ 的边 $(x, y)$ 进行合并。此时，对于属于 $A$ 的顶点 $a$ 和属于 $B$ 的顶点 $b$，可以确定 $D_{a,b} = |A| + D_{y,b}$。在这里，对于顶点 $b$ 的不便度 $D_{1,b} + D_{2,b} + \dots + D_{N,b}$ 的表达式，通过反复进行前面等式所表示的代入操作，最终可以将其表示为 $|A_1| + |A_2| + \dots$ 的形式。（请注意 $D_{b,b} = 0$。）可以发现，在这个表达式中 $|A|$ 出现的次数，等于在边 $(x, y)$ 处切断最小生成树时，位于 $x$ 一侧的顶点总数 $k$。因此，只需对包含在 $B$ 中的所有顶点 $b$ 的得分统一加上 $|A| \times k$ 即可。同理，对包含在 $A$ 中的所有顶点 $a$ 的得分也要加上 $|B| \times (N - k)$。

当图是一条路径时，这个加法操作相当于区间加法。因为只需要在最后求出结果即可，所以可以使用 imos 法（差分法）。 对于一般的图，这个加法操作对应于在“表示合并过程的树（Kruskal 重构树）”中，对子树的所有节点进行加法的操作。因为只需要在最后求出结果即可，所以只需将该值记录在子树的根节点上，之后一边将这些值累加，一边自顶向下地向子节点传递即可。

在计算复杂度方面，求解最小生成树时的边排序过程成为了瓶颈，为 $O(M \log M)$。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i < (n);i++)
#define eb emplace_back
#define si(x) (ll)x.size()
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>
#define vll vector<ll>
#define inf LLONG_MAX / 3
template<class T> bool chmin(T& a, const T& b){ if(a <= b) return 0; a = b; return 1; }
template<class T> bool chmax(T& a, const T& b){ if(a >= b) return 0; a = b; return 1; }
typedef long long ll;

struct uf{
	vll p;
	void init(ll n){
		p.resize(n);
		rep(i,n)p[i] = i;
	}
	ll par(ll x){
		return p[x] = (x == p[x] ? x : par(p[x]));
	}
	bool same(ll a,ll b){
		a = par(a);
		b = par(b);
		return a == b;
	}
	void unite(ll a,ll b){
		a = par(a);
		b = par(b);
		p[a] = b;
	}
};

int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	ll n,m,q;
	cin>>n>>m>>q;
	vector<tuple<ll,ll,ll> >edges;
	rep(i,m){
		ll a,b,c;
		cin>>a>>b>>c;
		a--,b--;
		edges.eb(c,a,b);
	}
	sort(all(edges));

	vector<pll>tedges;
	vector<vll> t(n);
	vll szt(n);
	auto gawa = [&](ll x,ll y){

		if(szt[x] > szt[y]){
			return n - szt[y];
		}
		return szt[x];
	};
	{
		uf uf;
		uf.init(n);
		for(auto &&[c,a,b] : edges){
			if(uf.same(a,b))continue;
			uf.unite(a,b);
			tedges.eb(a,b);
			t[a].eb(b);
			t[b].eb(a);
		}
		function<ll(ll,ll)> dfs = [&](ll x,ll frm){
			szt[x] = 1;
			for(auto &&y: t[x])if(y != frm){
				szt[x] += dfs(y,x);
			}
			return szt[x];
		};
		dfs(0, -1);
	}

	ll id = n;
	vll ad(n,0),p(n),sz(n, 1);
	vll p_star(n);
	rep(i,n)p[i] = p_star[i] = i;
	function<ll(ll)> par = [&](ll x){
		return p_star[x] = (p_star[x] == x ? x : par(p_star[x]));
	};

	for(auto &&[x,y] : tedges){
		ll a = par(x);
		ll b = par(y);
		ad[b] += sz[a] * gawa(x,y);
		ad[a] += sz[b] * gawa(y,x);
		p[a] = p_star[a] = p[b] = p_star[b] = id;
		p.eb(id);
		p_star.eb(id);
		ad.eb(0);
		sz.eb(sz[a] + sz[b]);
		id++;
	}

	for(int i = id - 1;i >= 0; i--){
		ad[i] += ad[p[i]];
	}

	while(q--){
		ll x;
		cin>>x;
		x--;
		cout<<ad[x]<<"\n";
	}
}