xpp杂题清除计划

这题和P8207 [THUPC2022 初赛] 最小公倍树有点像，都可以用优化选边的 kruskal 解决。

很显然，对于一张边数为 $n^2$ 级别的完全图，直接做 kruskal 的复杂度时 $O(n^2logn^2)$ 的，显然过不了。

但是也正是因为这是一张完全图，所以我们可以用一个定理来解决问题。

定理：对于任意一张完全图 $G=(V,E)$ ，选取数个边集 $(E_1,E_2,E_3,...,E_k)$ 使其完全覆盖边集 $E$ 。对每个集合 $E_i$ 求最小生成树，得到边集 $E_{MST_{i}}$ 。再对 $E_{MST_{1}},E_{MST_{2}},E_{MST_{3}},...,E_{MST_{k}}$ 求最小生成树，其最小生成树一定也是 $E$ 的最小生成树。

证明：考虑反证。假设最终图有一种比用 $E_{MST_{1}},E_{MST_{2}},E_{MST_{3}},...,E_{MST_{k}}$ 建出来的最小生成树更小的生成树，则该树一定有一条边 $(u,v)$ 不被包含在任何的 $E_{MST_i}$ 中。考虑这条边所属的一个或多个边集，在该边集中一定有一条连接 $(u,v)$ 的链，且此链一定不比 $(u,v)$ 更劣。因此在最终的最小生成树中用该链替代 $(u,v)$ 一定不会更劣。与该生成树比 $E_{MST_{1}},E_{MST_{2}},E_{MST_{3}},...,E_{MST_{k}}$ 建出来的最小生成树更小矛盾。

因此考虑淀粉质，假设我们以当前的分治中心 $rt$ 为根，设每个点的权值 $p_i$ 为 $dis_{rt,i} + w_i$ ，则对于不同子树的两个点，他们连边的权值为 $p_i+p_j$ 。考虑两两不同子树内的点之间连边组成的边集，设 $p_i$ 最小的 $i$ 为 $mn$ ，则这个边集的最小生成树一定为 $\sum_{i \in V} p_i+p_{mn}$ （这里的证明珂以参考一下 kruskal 算法正确性的证明），因此将淀粉质得到的所有边 $(i,mn)$ 加入边集，再做一次最小生成树就是 $G=(V,E)$ 的最小生成树了。

$Code$

#include<bits/stdc++.h>
#define N 200010
using namespace std;
typedef long long ll;
int n,en;
ll w[N],INF=1e18;
int cnt,head[N],to[N<<1],nxt[N<<1];
ll val[N<<1];
int S,son[N],siz[N],vis[N],rt;
struct edge{
	int u,v;
	ll w;
	const bool operator < (const edge o) const {return w<o.w;}
}e[N<<4];
void insert(int u,int v,int w) {
	cnt++;
	to[cnt]=v;
	val[cnt]=w;
	nxt[cnt]=head[u];
	head[u]=cnt;
}
int read() {
	int res=0,f=1;char ch=getchar();
	while(!isdigit(ch)) f=ch=='-'?-1:1,ch=getchar();
	while(isdigit(ch)) res=res*10+ch-'0',ch=getchar();
	return f*res;
}
void gtrt(int now,int fa) {
    siz[now]=1,son[now]=0;
    for(int i=head[now]; i; i=nxt[i]) if(to[i]!=fa&&!vis[to[i]]) {
    	gtrt(to[i],now);
    	siz[now]+=siz[to[i]];
    	son[now]=max(son[now],siz[to[i]]);
    }
    son[now]=max(son[now],S-siz[now]);
    if(son[now]<son[rt]) rt=now;
}
ll sk[N];
int id[N],tp,mn;
void dfs(int now,int fa,ll dis) {
	sk[++tp]=w[now]+dis,id[tp]=now;
	if(sk[tp]<sk[mn]) mn=tp;
	for(int i=head[now]; i; i=nxt[i]) if(!vis[to[i]]&&to[i]!=fa) 
		dfs(to[i],now,dis+val[i]);
}
void solve(int now) {
	vis[now]=1;
    tp=mn=0,dfs(now,0,0);
	for(int i=1; i<=tp; i++) if(i!=mn) e[++en]=edge{id[i],id[mn],sk[i]+sk[mn]}; 
	int tmp=S;
	for(int i=head[now]; i; i=nxt[i]) if(!vis[to[i]]) {
	    S=siz[to[i]]<siz[now]?siz[to[i]]:tmp-siz[now];
	    rt=0,gtrt(to[i],now),solve(rt);
	}
}
int fa[N];
int find(int x) {
	while(fa[x]!=x) x=fa[x]=fa[fa[x]];
	return x;
}
int main()
{
	n=read();
	for(int i=1; i<=n; i++) w[i]=read();
	for(int i=1; i<n; i++) {
		int u=read(),v=read(),w=read();
		insert(u,v,w);
		insert(v,u,w);
	}
	S=son[0]=n,rt=0,gtrt(1,0),sk[0]=INF;
	solve(rt);
	for(int i=1; i<=n; i++) fa[i]=i;
	sort(e+1,e+en+1);int tot=0;ll sum=0;
	for(int i=1; i<=en; i++) {
		int u=find(e[i].u),v=find(e[i].v);
		if(u!=v) fa[u]=v,tot++,sum+=e[i].w;
		if(tot==n-1) {printf("%lld",sum);return 0;}
	}
	return 0;
}

我是不会说我开 nlogn 的数组只开了 n*4 导致错了好几发的