at_cf17final_j Tree MST 题解

题目链接

点击打开链接

题目解法

还是挺有收获的题

解法1

完全图求 \(mst\)，首先应该考虑 \(boruvka\) 算法
现在的问题转化成了求 \(O(\log n)\) 次每个点 \(x\) 到不在 \(x\) 的连通块中的点的最短边
这个可以换根 \(dp\) 求
子树内的是好求的，只要记录所有连通块的最小值和次小值即可
子树外的同理
复杂度为 \(O(n\log n)\)，但细节较多，实现较为复杂（所以我没写

解法2

这个解法才是我要重点说的
求一张图的 \(mst\) 有一个 \(trick\)：先把这张图分成若干个边集，每个边集求一遍 \(mst\)，然后再把所有边集的 \(mst\) 中的边拎出来再做一遍 \(mst\)，得到的就是原图的 \(mst\)
如何应用到这道题中？
考虑点分治
分治中心 \(rt\) 包含的边集是什么？
包含边 \((x,y)\)，满足 \(x,y\) 均在 \(rt\) 的分治子树中（或 \(rt\) 自己），且 \(x,y\) 不在 \(rt\) 的同一棵子树中
这些边做 \(mst\) 得到的边是显然的
令 \(dep_x\) 为点 \(x\) 到分治中心 \(rt\) 的距离
那么在 \(mst\) 中的边即为分治区域内的所有点 到 最小的 \(dep_x+w_x\) 的 \(x\) 的边
把这些边最后做一遍 \(mst\) 即可
时间复杂度 \(O(n\log^2n)\)，且细节较少

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int N=200010;
const LL inf=1e18;
int w[N];
vector<pii> G[N];
int siz[N];bool vis[N];
typedef tuple<LL,int,int> tup;
int cnt;
tup edge[N*30];
void get_sz(int u,int fa){
    siz[u]=1;
    for(auto [v,w]:G[u]) if(v!=fa&&!vis[v]) get_sz(v,u),siz[u]+=siz[v];
}
LL dis[N],mnv;int pos;
void get_dis(int u,int fa){
    if(dis[u]+w[u]<mnv) mnv=dis[u]+w[u],pos=u;
    for(auto [v,w]:G[u]) if(v!=fa&&!vis[v]) dis[v]=dis[u]+w,get_dis(v,u);
}
void add_edge(int u,int fa){
    if(u!=pos) edge[++cnt]={w[u]+dis[u]+mnv,u,pos};
    for(auto [v,w]:G[u]) if(v!=fa&&!vis[v]) add_edge(v,u);
}
void dfz(int rt){
    get_sz(rt,0);int tot=siz[rt];
    while(true){
        bool fl=0;
        for(auto [v,w]:G[rt]) if(siz[v]<siz[rt]&&siz[v]>tot/2){ rt=v,fl=1;break;}
        if(!fl) break;
    }
    vis[rt]=1;
    dis[rt]=0,mnv=inf,get_dis(rt,0);
    add_edge(rt,0);
    for(auto [v,w]:G[rt]) if(!vis[v]) dfz(v);
}
int fa[N];
int gfa(int x){ if(x==fa[x]) return x;return fa[x]=gfa(fa[x]);}
int main(){
    int n;read(n);
    F(i,1,n) read(w[i]);
    F(i,1,n-1){
        int x,y,z;read(x),read(y),read(z);
        G[x].pb({y,z}),G[y].pb({x,z});
    }
    dfz(1);
    sort(edge+1,edge+cnt+1);
    LL ans=0;
    F(i,1,n) fa[i]=i;
    F(i,1,cnt){
        auto [z,x,y]=edge[i];
        x=gfa(x),y=gfa(y);
        if(x!=y) fa[x]=y,ans+=z;
    }
    printf("%lld\n",ans);
    return 0;
}