AT3611 Tree MST
541forever
·
·
题解
首先我们发现在完全图上的边权若是在钦定经过一个点 x 的情况下可以转换为 dis_u + dis_v + w_u +
w_v，dis_i 是点 x 到点 i 的距离。这又可以转换为 p_u + p_v，p_i 表示 dis_i + w_i，这就告诉我们这两个点的价值是可以分开算的。
而钦定一个点的过程就启示我们点分。考虑点分出一个分治重心后，首先我们知道只有在强制经过分治重心的情况下能成为最小生成树的边才有可能成为最终的最小生成树的边，接着，对于又因为每个点是独立的，所以强制经过分治重心情况下的最小生成树一定是选出一个最小
最后将所有侯选边提出来跑一遍 Kruskal 就做完了。考虑时间复杂度，首先我们点分了 $\log$ 层，每层连的边数又是 $O(n)$ 的，那么总的候选边数就是 $O
(n \log n)$，然后 Kruskal 的复杂度 $O (m \log n)$ 的，所以总复杂度是 $O (n \log^2 n)$ 的。
最后贴上丑陋的代码
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=200000,INF=0x3f3f3f3f;
int n,edgenum,ans,rt,head[MAXN+5],val[MAXN+5],si[MAXN+5],dist[MAXN+5],a[MAXN+5],num,b[MAXN+5],tot,fa[MAXN+5];
bool vis[MAXN+5];
inline int read(){
int x=0,f=1;
char ch;
do{
ch=getchar();
if(ch=='-'){
f=-1;
}
}while(!(ch>='0'&&ch<='9'));
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+ch-'0';
ch=getchar();
}
return x*f;
}
struct Tree{
int from,to,next,w;
}edge[2*MAXN+5];
struct Nedge{
int from,to,w;
}nedge[20*MAXN+5];
void add_edge(int from,int to,int w){
edge[++edgenum].next=head[from];
edge[edgenum].from=from;
edge[edgenum].to=to;
edge[edgenum].w=w;
head[from]=edgenum;
}
void get_root(int x,int f,int cnt){
si[x]=1;
int maxn=-INF;
for(int i=head[x];i;i=edge[i].next){
int v=edge[i].to;
if(v==f||vis[v]){
continue;
}
get_root(v,x,cnt);
si[x]+=si[v];
maxn=max(maxn,si[v]);
}
maxn=max(maxn,cnt-si[x]);
if(maxn<ans){
ans=maxn;
rt=x;
}
}//求重心
void dfs(int x,int f,int from){
a[++num]=x;
b[x]=from;
si[x]=1;
for(int i=head[x];i;i=edge[i].next){
int v=edge[i].to;
if(v==f||vis[v]){
continue;
}
dist[v]=dist[x]+edge[i].w;
dfs(v,x,from);
si[x]+=si[v];
}
}
void solve(){
vis[rt]=1;
dist[rt]=0;
num=0;
a[++num]=rt;
b[rt]=rt;
for(int i=head[rt];i;i=edge[i].next){
int v=edge[i].to;
if(vis[v]){
continue;
}
dist[v]=edge[i].w;
dfs(v,rt,v);
}
int pos=rt,minx=INF;
for(int i=1;i<=num;++i){
if(val[a[i]]+dist[a[i]]<minx){
minx=val[a[i]]+dist[a[i]];
pos=a[i];
}
}
for(int i=1;i<=num;++i){
if(b[a[i]]!=b[pos]){
nedge[++tot].from=pos;
nedge[tot].to=a[i];
nedge[tot].w=dist[pos]+val[pos]+dist[a[i]]+val[a[i]];//将候选边存下来
}
}
for(int i=head[rt];i;i=edge[i].next){
int v=edge[i].to;
if(vis[v]){
continue;
}
ans=INF;
get_root(v,v,si[v]);//继续点分下去
solve();
}
}//点分
bool cmp(Nedge x,Nedge y){
return x.w<y.w;
}
int find(int x){
if(fa[x]==x){
return x;
}
return fa[x]=find(fa[x]);
}
signed main(){
n=read();
for(int i=1;i<=n;++i){
val[i]=read();
}
for(int i=1;i<n;++i){
int x=read();
int y=read();
int w=read();
add_edge(x,y,w);
add_edge(y,x,w);
}
ans=INF;
get_root(1,1,n);
solve();
sort(nedge+1,nedge+tot+1,cmp);
for(int i=1;i<=n;++i){
fa[i]=i;
}
ans=0;
for(int i=1;i<=tot;++i){
int x=nedge[i].from;
int y=nedge[i].to;
x=find(x);
y=find(y);
if(x!=y){
fa[x]=y;
ans+=nedge[i].w;
}
}//Kruskal
printf("%lld\n",ans);
return 0;
}
```