题解：CF2222F Building Tree

· · 题解

妙妙题。

思路

考虑刻画两个点之间何时有一个边权（不要求最小）为 w 的边。

考虑将 \operatorname{mex} 拓宽限制变为未出现的非负整数，不难发现，非 \operatorname{mex} 的值一定不优，所以不会影响答案。

则现在求未出现的非负整数，设其为 x，则存在一条路径使得只选边权为 [0,x-1] \cup [x+1,m] 的边路径仍然连通两个点。形式类似缺一分治，于是往分治的方向靠。

设 solve(l,r) 表示处理边权为 [l,r] 的边。根据缺一分治步骤，如下：

当加入一条边后两点连通，说明两点之间边权包含目前还未处理的区间。例如进行第一步的时候，若两点连通，则说明其边权包含 [l,mid]，取最小值 l。

上述加入删除边维护连通性可以使用可撤销并查集，同时可以维护一个普通并查集代表最小生成树答案的连通性。

目前解决了关键点是全部的情况，考虑部分是关键点的情况。

发现当连通原图 X,Y 连通块时，只需要在 X 任取一个关键点和 Y 中任意一个关键点连边即可。任取是因为 X 中关键点已经连通了，所以可以任取一个。

所以并查集多维护一个当前连通块任意一个关键点即可。

时间复杂度 O(m \log m \log n)。

AcCode

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INT_MAX (int)(1e18)

const int N=3e5+10;

int n,m,q,ans,Ans;
int fa[N],siz[N],fa1[N],inc[N];

bool mk[N];

inline int read(){
    int t=0,f=1;
    register char c=getchar();
    while(c<'0'||c>'9') f=(c=='-')?(-1):(f),c=getchar();
    while(c>='0'&&c<='9') t=(t<<3)+(t<<1)+(c^48),c=getchar();
    return t*f;
}

struct node{int u,v;};

vector<node> g[N];

int find(int x){
    if(fa[x]==x) return x;
    return find(fa[x]);
}

int find1(int x){
    if(fa1[x]==x) return x;
    return find1(fa1[x]);
}

#define mid (l+r>>1)

stack<node> s;

void Merge(int u,int v,int x){
    if(!inc[u]||!inc[v]) return;
    u=find1(inc[u]),v=find1(inc[v]);
    if(u==v) return;
    fa1[u]=v,ans+=x,Ans++;
}

void merge(int u,int v,int x){
    u=find(u),v=find(v);
    if(u==v) return;
    if(siz[u]>siz[v]) swap(u,v);
    siz[v]+=siz[u],fa[u]=v,inc[v]=inc[v]?inc[v]:inc[u];
    s.push((node){u,v}),Merge(u,v,x);
}

int Add(int l,int r,int x){
    int res=s.size();
    for(int i=l;i<=r;i++)
        for(node j:g[i]) merge(j.u,j.v,x);
    return res;
}

void Init(int x){
    while(s.size()!=x){
        int u=s.top().u,v=s.top().v;s.pop();
        siz[v]-=siz[u],fa[u]=u,inc[v]=inc[v]==inc[u]?0:inc[v];
    }
}

void solve(int l,int r){
    if(l==r) return;int Siz=0;
    Siz=Add(mid+1,r,l);solve(l,mid);Init(Siz);
    Siz=Add(l,mid,mid+1);solve(mid+1,r);Init(Siz);
}

void solve(){
    n=read(),m=read(),q=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),w=read();
        g[w].push_back((node){u,v});
    }int sumq=0;
    for(int i=1;i<=q;i++) mk[read()]=true;
    for(int i=1;i<=n;i++) sumq+=mk[i];
    for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1,fa1[i]=i,inc[i]=mk[i]?i:0;
    solve(0,m);
    if(Ans==sumq-1) cout<<ans<<"\n";
    else cout<<-1<<"\n";

    ans=0,Ans=0;
    for(int i=0;i<=m;i++) g[i].clear();
    for(int i=1;i<=n;i++) mk[i]=false;
}

signed main(){
    int T=read();
    while(T--) solve();
    return 0;
}