AtCoder

Luogu

分析

点分治+$\mathrm{Kruskal}$。

对于点分树上的每一个子树，只选取可能会出现的 $size$ 条边。

具体就是，每次找到点分树中 $dis(root,u)+w[u]$ 最小的 $u$ ，然后其它的路径与它组合，并丢到候选边内即可。

找到所有候选边后，跑一边$\mathrm{Kruskal}$求出答案即可。

上面这么讲比较抽象，可以结合代码理解一下。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,m;
int w[N];

struct Graph {
    struct Edge { int v,w,nxt; } e[N<<1];
    int head[N];
    
    inline void addEdge(int u,int v,int w) {
        static int cnt=0;
        e[++cnt]=(Edge){v,w,head[u]},head[u]=cnt;
    }
} G;

struct Edge { int u,v; ll w; } e[N*50];
bool operator <(Edge a,Edge b) { return a.w<b.w; }

int sumsz,root,pos;
ll minval;
int sz[N],f[N],vis[N];

inline void getroot(int u,int fa) {
    sz[u]=1,f[u]=0;
    for (re int i=G.head[u];i;i=G.e[i].nxt) {
        int v=G.e[i].v; if (vis[v]||v==fa) continue;
        getroot(v,u); sz[u]+=sz[v],f[u]=max(f[u],sz[v]);
    }
    f[u]=max(f[u],sumsz-sz[u]);
    if (!root||f[u]<f[root]) root=u;
}

inline void find_val(int u,int fa,ll dis) {
    if (dis+w[u]<minval) minval=dis+w[u],pos=u;
    for (re int i=G.head[u];i;i=G.e[i].nxt)
        if (!vis[G.e[i].v]&&G.e[i].v!=fa)
            find_val(G.e[i].v,u,dis+G.e[i].w);
}

inline void link(int u,int fa,ll dis) {
    e[++m]=(Edge){u,pos,minval+dis+w[u]};
    for (re int i=G.head[u];i;i=G.e[i].nxt)
        if (!vis[G.e[i].v]&&G.e[i].v!=fa)
            link(G.e[i].v,u,dis+G.e[i].w);
}

inline void solve(int u) {
    vis[u]=1;
    minval=1e18,pos=0,find_val(u,0,0),link(u,0,0);
    for (re int i=G.head[u];i;i=G.e[i].nxt) {
        int v=G.e[i].v; if (vis[v]) continue;
        sumsz=sz[v],root=0,getroot(v,u),solve(root);
    }
}

struct UFS {
    int f[N];
    inline int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }
    inline void merge(int x,int y) {
        x=find(x),y=find(y);
        if (x!=y) f[x]=y;
    }
} S;

int main() {
    n=read();
    for (re int i=1;i<=n;++i) w[i]=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read(),w=read();
        G.addEdge(u,v,w),G.addEdge(v,u,w);
    }
    sumsz=n,root=0,getroot(1,0);
    solve(root); sort(e+1,e+m+1);
    int tot=0; ll ans=0;
    for (re int i=1;i<=n;++i) S.f[i]=i;
    for (re int i=1;i<=m;++i) {
        int u=e[i].u,v=e[i].v; ll w=e[i].w;
        if (S.find(u)==S.find(v)) continue;
        ++tot,ans+=w,S.merge(u,v);
        if (tot==n-1) break;
    }
    printf("%lld\n",ans);
    return 0;
}