题解：CF2222F Building Tree

· · 题解

Solution

首先进行初步转化，考虑到 \operatorname{mex} 的定义、dis(u,v) 的定义与最小生成树的都取 \min，因此考虑将前两个条件中的 \min 删掉，不影响答案。问题放宽为：计算一张新图中的最小生成树，其中加的边 (u,v,w) 必须满足，在原图上加上所有边权 \ne w 的边后，u 和 v 连通。

于是一个朴素做法为，模拟 Kruscal 算法流程，从小往大枚举边权 i，并在原图上加入所有边权 \ne i 的边，并查集维护。复杂度瓶颈在于以下两点：

解决第一个问题，可以利用分治思想，结构类似线段树。对权值序列进行分治，递归每个区间 [l,r]，取 mid=\lfloor \frac{l+r}{2} \rfloor。递归 [l,mid] 之前，加入边权在 (mid,r] 中的边，递归后撤销；递归 (mid,r] 之前，加入边权在 [l,mid] 中的边，递归后撤销。这样递归到叶节点时，加入的边集刚好就是所有边权 \ne i 的边了。

解决第二个问题，不能等到了叶节点再在新图中加边。由于 (u,v) 连边的条件为 u 和 v 在原图中连通，所以把加边操作调整到原图上 u 和 v 所属连通块合并的时候。具体地，当我们加入边权在 (mid,r] 中的边时，从要合并的两个连通块中各选一个关键点（即新图上的点），然后在新图上连接这两个点，边权为 l。

于是，拿两个并查集维护，一个维护原图上的，一个维护新图上的。原图上的需满足可撤销，因此不可以路径压缩；新图上的起的就是 Kruscal 中并查集的作用。由于分治和启发式合并，总时间复杂度为 O(m\log m\log n)。

Code

码风清纯。

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <stack>
using namespace std;
typedef long long LL;
int read()
{
    char c=getchar();
    int f=1,x=0;
    while(c<'0'||c>'9')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
    return x*f;
}
void print(LL x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
const int N=3e5+5;
int T,n,m,q;
bool a[N];
vector<pair<int,int>> e[N];
LL ans;
struct dsu
{
    int fa[N];
    void init(){for(int i=1;i<=n;i++) fa[i]=i;}
    int findfa(int x)
    {
        if(x==fa[x]) return x;
        return fa[x]=findfa(fa[x]);
    }
    void merge(int x,int y,int w)
    {
        x=findfa(x),y=findfa(y);
        if(x==y) return;
        ans+=w;
        fa[y]=x;
    }
}d;
struct dsu2
{
    int fa[N],sz[N],g[N];
    void init(){for(int i=1;i<=n;i++) fa[i]=i,sz[i]=1,g[i]={a[i]?i:0};}
    int findfa(int x)
    {
        if(x==fa[x]) return x;
        return findfa(fa[x]);
    }
    int merge(int x,int y,int w)
    {
        x=findfa(x),y=findfa(y);
        if(x==y) return 0;
        if(g[x]&&g[y]) d.merge(g[x],g[y],w);
        if(sz[x]<sz[y]) swap(x,y);
        fa[y]=x;
        sz[x]+=sz[y];
        if(!g[x]&&g[y]) g[x]=g[y];
        return y;
    }
    void del(int x)
    {
        if(g[fa[x]]==g[x]) g[fa[x]]=0;
        sz[fa[x]]-=sz[x];
        fa[x]=x;
    }
}d2;
void solve(int l,int r)
{
    if(l>=r) return;
    int mid=(l+r)>>1;
    stack<int> s;
    for(int i=mid+1;i<=r;i++)
    {
        for(auto it=e[i].begin();it!=e[i].end();it++)
        {
            int u=(*it).first,v=(*it).second,x=d2.merge(u,v,l);
            if(x) s.push(x);
        }
    }
    solve(l,mid);
    while(s.size())
    {
        int u=s.top();
        d2.del(u);
        s.pop();
    }
    for(int i=l;i<=mid;i++)
    {
        for(auto it=e[i].begin();it!=e[i].end();it++)
        {
            int u=(*it).first,v=(*it).second,x=d2.merge(u,v,mid+1);
            if(x) s.push(x);
        }
    }
    solve(mid+1,r);
    while(s.size())
    {
        int u=s.top();
        d2.del(u);
        s.pop();
    }
}
int main()
{
    T=read();
    while(T--)
    {
        n=read();
        m=read();
        q=read();
        for(int i=0;i<=m;i++) e[i].clear();
        for(int i=1;i<=m;i++)
        {
            int u,v,w;
            u=read();
            v=read();
            w=read();
            e[w].push_back(make_pair(u,v));
        }
        for(int i=1;i<=n;i++) a[i]=false;
        for(int i=1;i<=q;i++)
        {
            int x=read();
            a[x]=true;
        }
        d.init();
        d2.init();
        ans=0;
        solve(0,m);
        int cnt=0;
        for(int i=1;i<=n;i++)
            if(a[i]) cnt+=(d.fa[i]==i);
        if(cnt>1) puts("-1");
        else print(ans),putchar('\n');
    }
    return 0;
}