P6199 [EER1]河童重工

· · 题解

比较经典的套路，写这篇题解来记录一下。

考虑 Boruvka 算法求最小生成树。

这个算法的好处是用 O(\log n) 的代价将最小生成树问题转化为较为简单的数据结构问题。

对于这道题来说，转化后的问题是：每个点 i 有一个颜色 col_i，要对于每一个点 i 求出 \min\limits_{col_i\neq col_j}dis_1(i,j)+dis_2(i,j)。

考虑在 T_1 上点分治，每次求出当前子树在 T_2 上的虚树。点分治的好处是把 dis_1(i,j) 拆成 w_i+w_j。于是直接在虚树上换根 dp 即可。dp 过程中需要记录最大值以及与最大值颜色不同的最大值。

需要注意的一个细节是：点分治过程中在重心的同一儿子的子树内的两个点实际上并不应该在当前过程中计算。

但可以发现由于边权都是正数，所以即便这两个点在当前过程中被计算到了也不会影响答案，这种方案一定不优。

这样直接计算一遍复杂度是 O(n\log ^2n)，瓶颈在建虚树。算上 Boruvka 就是 O(n\log^3 n)。但虚树的形态是固定的，我们只需要预处理出点分树上每个子树的虚树就可以做到 O(n\log^2 n)。

参考代码：

#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define pb push_back
#define ll long long
const int INF=1e9;
int n,m,dfsT,G,vs2[N],rt[N],st[N];ll ans;bool vs1[N];
int dfn1[N],dfn2[N],fa[N],dep[N],s[N],sz[N],hv[N],tp[N];
struct Edge
{
    int v,w;Edge(int _v=0,int _w=0) {v=_v;w=_w;}
    Edge operator + (int t) const {return Edge(v,w+t);}
    Edge operator - (int t) const {return Edge(v,w-t);}
}z[N],dp1[N],dp2[N],dp3[N],dp4[N];
vector<Edge> e1[N],e2[N];struct Node {int u,w;};
vector<Node> vc1[N];vector<int> vc2[N];
bool cmp(int x,int y)
{return (x>0?dfn1[x]:dfn2[-x])<(y>0?dfn1[y]:dfn2[-y]);}
int findRt(int u) {return u==rt[u]?u:rt[u]=findRt(rt[u]);}
void merge(int u,int v,int w)
{u=findRt(u);v=findRt(v);if(u!=v) rt[u]=v,ans+=w;}
void ins(Edge &z1,Edge &z2,Edge vl)
{
    if(vl.w<z1.w) {if(vl.v!=z1.v) z2=z1;z1=vl;}
    else if(vl.w<z2.w && vl.v!=z1.v) z2=vl;
}
void dfs1(int u,int f,int x,int s,bool fl)
{
    int mx=0;sz[u]=1;
    if(fl) vc1[G].pb((Node) {u,s}),vc2[G].pb(u),vs2[u]=G;
    for(auto i:e1[u]) if(i.v!=f && !vs1[i.v])
        dfs1(i.v,u,x,s+i.w,fl),sz[u]+=sz[i.v],mx=max(mx,sz[i.v]);
    mx=max(mx,x-sz[u]);if(!fl && mx<=x/2) G=u;
}
void dfs2(int u,int f)
{
    fa[u]=f;dfn1[u]=++dfsT;dep[u]=dep[f]+1;sz[u]=1;
    for(auto i:e2[u]) if(i.v!=f)
    {
        s[i.v]=s[u]+i.w;dfs2(i.v,u);sz[u]+=sz[i.v];
        if(sz[i.v]>sz[hv[u]]) hv[u]=i.v;
    }dfn2[u]=++dfsT;
}
void dfs3(int u,int f)
{
    tp[u]=f;if(hv[u]) dfs3(hv[u],f);
    for(auto i:e2[u]) if(i.v!=fa[u] && i.v!=hv[u]) dfs3(i.v,i.v);
}
int LCA(int u,int v)
{
    while(tp[u]!=tp[v])
    {if(dep[tp[u]]<dep[tp[v]]) swap(u,v);u=fa[tp[u]];}
    if(dep[u]<dep[v]) swap(u,v);return v;
}
void build(int u,int x)
{
    dfs1(u,0,x,0,0);u=G;dfs1(u,0,x,0,1);vs1[u]=1;
    sort(vc2[u].begin(),vc2[u].end(),cmp);
    for(int i=0;i<(int)vc2[u].size()-1;++i)
    {
        int t=LCA(vc2[u][i],vc2[u][i+1]);
        if(vs2[t]!=u) vs2[t]=u,vc2[u].pb(t);
    }
    for(int i=0;i<(int)vc2[u].size();++i)
    {if(vc2[u][i]<0) break;vc2[u].pb(-vc2[u][i]);}
    sort(vc2[u].begin(),vc2[u].end(),cmp);
    for(auto i:e1[u]) if(!vs1[i.v]) build(i.v,sz[i.v]);
}
void slv(int u)
{
    for(auto i:vc2[u]) if(i>0)
        dp1[i]=dp2[i]=dp3[i]=dp4[i]=Edge(0,INF);
    for(auto i:vc1[u]) dp1[i.u]=Edge(rt[i.u],i.w);
    for(auto i:vc2[u]) if(i>0) st[++st[0]]=i;else
    {
        int f=st[--st[0]],w=s[-i]-s[f];if(!f) continue;
        ins(dp1[f],dp2[f],dp1[-i]+w);ins(dp1[f],dp2[f],dp2[-i]+w);
    }
    for(auto i:vc2[u]) if(i>0)
    {
        int f=st[st[0]],w=s[i]-s[f];st[++st[0]]=i;
        dp3[i]=dp1[i];dp4[i]=dp2[i];if(!f) continue;
        ins(dp3[i],dp4[i],dp3[f]+w);ins(dp3[i],dp4[i],dp4[f]+w);
    }else --st[0];
    for(auto i:vc1[u])
    {
        int t1=rt[i.u];Edge t=t1==dp3[i.u].v?dp4[i.u]:dp3[i.u];
        t=t+i.w;if(t.w<z[t1].w) z[t1]=t;
    }
}
void Boruvka()
{
    for(int i=1;i<=n;++i) rt[i]=i;
    while(1)
    {
        bool fl=0;
        for(int i=1;i<=n;++i)
        {findRt(i);if(rt[i]!=rt[1]) fl=1;z[i]=Edge(0,INF);}
        if(!fl) break;for(int i=1;i<=n;++i) slv(i);
        for(int i=1;i<=n;++i) if(rt[i]==i) merge(i,z[i].v,z[i].w);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1,u,v,w;i<n;++i)
    {
        scanf("%d %d %d",&u,&v,&w);
        e1[u].pb(Edge(v,w));e1[v].pb(Edge(u,w));
    }
    for(int i=1,u,v,w;i<n;++i)
    {
        scanf("%d %d %d",&u,&v,&w);
        e2[u].pb(Edge(v,w));e2[v].pb(Edge(u,w));
    }dfs2(1,0);dfs3(1,1);build(1,n);Boruvka();
    printf("%lld\n",ans);return 0;
}