题意

给定一棵 n 个节点的树，现有有一张完全图，两点 x,y 之间的边长为 w_x+w_y+dis_{x,y}，其中 dis 表示树上两点的距离。

求完全图的 MST。

题解

关于最小生成树，有一个定理：

设 \operatorname{MST}(E) 为连通边集 E 的最小生成树。若

E=E_1\cup E_2\cup\cdots\cup E_k

则

\operatorname{MST}(E)=\operatorname{MST}(\operatorname{MST}(E_1)\cup\operatorname{MST}(E_2)\cup\cdots\cup\operatorname{MST}(E_k))

也就是说，我们可以把一个完全图划分成若干个边集，分别求最小生成树，最后将保留的边再求一次，就可以得到答案。

而对于这种树上的问题，完全图上的一条边对应树的一条路径。我们可以使用点分治同时处理过每个分治中心 u 的所有路径。这样的 MST 是比较好求的：在当前分支范围中选出 dis_{u,v}+w_v 最小的点 v，将 v 与所有其他点连边即可。这样做是正确的，因为所有与 v 在不同子树中的点到 v 都须经过 u,v 这条路径，而在同一子树中的点一定不比在接下来的分治中处理更优。最后所有保留下来的边数是 O(n\log n) 的，再跑一次 Kruskal 复杂度就是 O(n\log^2 n)。下面是代码：

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN=220000;
const int MAXM=5500000;
const ll INF=1E18;
int n, m, a[MAXN];
struct Edge1
{
    int to, val;
    Edge1(int v, int w): to(v), val(w) {}
};
vector<Edge1> g[MAXN];
struct Edge2
{
    int u, v; ll w;
    Edge2() {}
    Edge2(int a, int b, ll c):
        u(a), v(b), w(c) {}
    bool operator < (const Edge2& rhs) const
    {
        return w<rhs.w;
    }
} ed[MAXM];
struct DSU
{
    int f[MAXN];
    void init()
    {
        for (int i=1; i<=n; i++) f[i]=i;
    }
    int getf(int x)
    {
        if (x==f[x]) return x;
        return f[x]=getf(f[x]);
    }
    bool merge(int u, int v)
    {
        int x=getf(u), y=getf(v);
        if (x==y) return 0;
        f[x]=y; return 1;
    }
} dsu;
bool vis[MAXN];
int sz[MAXN], mx[MAXN];
ll dis[MAXN];
int sum, root, pos; ll mn;
void getroot(int u, int f)
{
    sz[u]=1, mx[u]=0;
    for (Edge1 e:g[u])
    {
        int v=e.to;
        if (!vis[v]&&v!=f)
        {
            getroot(v, u); sz[u]+=sz[v];
            mx[u]=max(mx[u], sz[v]);
        }
    }
    mx[u]=max(mx[u], sum-sz[u]);
    if (mx[u]<mx[root]) root=u;
}
void getpos(int u, int f)
{
    if (a[u]+dis[u]<mn) mn=a[u]+dis[u], pos=u;
    for (Edge1 e:g[u])
    {
        int v=e.to;
        if (!vis[v]&&v!=f)
        {
            dis[v]=dis[u]+e.val;
            getpos(v, u);
        }
    }
}
void link(int u, int f)
{
    ed[++m]=Edge2(u, pos, a[u]+a[pos]+dis[u]+dis[pos]);
    for (Edge1 e:g[u])
        if (!vis[e.to]&&e.to!=f) link(e.to, u);
}
void solve(int u)
{
    mn=INF, dis[u]=0;
    getpos(u, 0); link(u, 0);
    vis[u]=1;
    for (Edge1 e:g[u])
    {
        int v=e.to;
        if (!vis[v])
        {
            sum=sz[v], root=0;
            getroot(v, u); solve(root);
        }
    }
}
int main()
{
//  freopen("AT3611.in", "r", stdin);
//  freopen("AT3611.out", "w", stdout);
    scanf("%d", &n);
    for (int i=1; i<=n; i++) scanf("%d", &a[i]);
    for (int i=1; i<n; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        g[u].push_back(Edge1(v, w));
        g[v].push_back(Edge1(u, w));
    }
    mx[0]=sum=n, root=0;
    getroot(1, 0); solve(root);
    sort(ed+1, ed+m+1);
    dsu.init();
    ll ans=0;
    for (int i=1, cnt=0; i<=m&&cnt<n-1; i++)
        if (dsu.merge(ed[i].u, ed[i].v))
            cnt++, ans+=ed[i].w;
    printf("%lld\n", ans);
    return 0;
}

但是上面这种做法还是太 naive 了，我们有效率更高的做法。

Borůvka 也是一种求 MST 的算法，有些边数 n^2 级别的图求最小生成树可以考虑使用它，比如 CF888G。

它的思路大概是多路增广，从当前的每个连通块中伸出一条到别的连通块中最短的边，并合并这两个连通块。这个过程的复杂度是 O(n\log n) 的，具体可以看 Wikipedia 上它的讲解。

现在边权与树上路径的长度有了关系。处理每一层时，我们考虑树形 DP，求出每个点 x 到其他点的最小边权，以及这条边通向的点 y。但是这还不能解决问题，因为可能最优的点与这个点在同一个连通块中，因此我们还需要求与 y 不在一个连通块，且到 x 边权最小的点 z。这两个东西可以两次 DFS 求出，第一次儿子向父亲转移，第二次父亲向儿子转移。因为一条路径必然是先向上走若干条边再向下走若干条边，因此这样的顺序是对的。然后用并查集合并连通块，如此反复直到连的边数为 n-1 为止。复杂度为 O(n\log n)。

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN=220000;
const ll INF=1E18;
int n, m, a[MAXN];
struct Edge
{
    int to, val;
    Edge(int v, int w): to(v), val(w) {}
};
vector<Edge> g[MAXN];
struct DSU
{
    int f[MAXN];
    void init()
    {
        for (int i=1; i<=n; i++) f[i]=i;
    }
    int getf(int x)
    {
        if (x==f[x]) return x;
        return f[x]=getf(f[x]);
    }
    bool merge(int u, int v)
    {
        int x=getf(u), y=getf(v);
        if (x==y) return 0;
        f[x]=y; return 1;
    }
} dsu;
typedef pair<ll, int> pli;
pli dp1[MAXN], dp2[MAXN], p[MAXN];
void dfs1(int u, int f)
{
    for (Edge e:g[u])
    {
        int v=e.to;
        if (v!=f)
        {
            dfs1(v, u);
            dp1[u]=min(dp1[u], make_pair(dp1[v].first+e.val, dp1[v].second));
        }
    }
    for (Edge e:g[u])
    {
        int v=e.to;
        if (v!=f)
        {
            dp2[u]=min(dp2[u], dsu.f[dp1[v].second]!=dsu.f[dp1[u].second]?
            make_pair(dp1[v].first+e.val, dp1[v].second):
            make_pair(dp2[v].first+e.val, dp2[v].second));
        }
    }
}
void dfs2(int u, int f)
{
    for (Edge e:g[u])
    {
        int v=e.to;
        if (v!=f)
        {
            dp1[v]=min(dp1[v], make_pair(dp1[u].first+e.val, dp1[u].second));
            dp2[v]=min(dp2[v], dsu.f[dp1[u].second]!=dsu.f[dp1[v].second]?
            make_pair(dp1[u].first+e.val, dp1[u].second):
            make_pair(dp2[u].first+e.val, dp2[u].second));
            dfs2(v, u);
        }
    }
}
int main()
{
//  freopen("AT3611.in", "r", stdin);
//  freopen("AT3611.out", "w", stdout);
    scanf("%d", &n);
    for (int i=1; i<=n; i++) scanf("%d", &a[i]);
    for (int i=1; i<n; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        g[u].push_back(Edge(v, w));
        g[v].push_back(Edge(u, w));
    }
    dsu.init();
    int cnt=0; ll ans=0;
    while (cnt<n-1)
    {
        for (int i=1; i<=n; i++)
        {
            dp1[i]=make_pair(a[i], i);
            dp2[i]=make_pair(INF, 0);
        }
        dfs1(1, 0); dfs2(1, 0);
        for (int i=1; i<=n; i++)
        {
            p[i]=dsu.f[dp1[i].second]!=dsu.f[i]?dp1[i]:dp2[i];
            p[i].first+=a[i];
        }
        for (int i=1; i<=n; i++) p[dsu.f[i]]=min(p[dsu.f[i]], p[i]);
        for (int i=1; i<=n; i++)
        {
            pli t=p[dsu.getf(i)];
            if (t.first<INF&&dsu.merge(i, t.second)) cnt++, ans+=t.first;
        }
        for (int i=1; i<=n; i++) dsu.getf(i);
    }
    printf("%lld\n", ans);
    return 0;
}

然而这也不是最好的方法，EER1F. 河童重工 的标算说到了一种更好的做法。传送门

最后的排序使用基数排序可以做到线性或者并查集的复杂度。然而我不会证正确性orz