题目概述

有 $n$ 个点，$K$ 条特殊边，边权待定，保证无环，还有 $m$ 条普通带权边，现在确定特殊边的边权，使得最小生成树（边权相同选特殊边）包含所有特殊边。求上述条件成立的情况下最大边权和是多少。

解题报告

打vp的时候来不及了，之后发现是斯波题。先加入 $K$ 条边，然后按照边权顺序能加就加 $m$ 条边，用那些没有加上去的边覆盖最小生成树，如果一条特殊边没被覆盖过，那么边权和就可以无穷大，否则边权和就是每条特殊边被覆盖的最小值的总和。

示例程序

两个 $log$ 很虚，然后就被卡了……我把线段树区间覆盖那部分改成常数小点的写法就过了……

#include<cstdio>
#include<cctype>
#include<algorithm>
#define fr first
#define sc second
using namespace std;
typedef long long LL;
const int maxn=500000,maxm=500000,INF=2147483647;

int n,A,B,f[maxn+5];pair<int, pair<int,int> > e[maxm+5];bool vis[maxm+5];
int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5],w[(maxn<<1)+5];
int fa[maxn+5],ID[maxn+5],dep[maxn+5],si[maxn+5],SH[maxn+5],top[maxn+5];
int ti,Lt[maxn+5],MIN[(maxn<<2)+5],tag[(maxn<<2)+5];LL ans;

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
    if (l==r) return EOF;return *l++;
}
inline int readi(int &x){
    int tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return (lst=='-'?x=-tot:x=tot),Eoln(ch);
}
int getfa(int x) {return x==f[x]?x:f[x]=getfa(f[x]);}
#define Add(x,y,z) (son[++E]=(y),w[E]=(z),nxt[E]=lnk[x],lnk[x]=E)
void Dfs(int x,int pre=0){
    fa[x]=pre;dep[x]=dep[pre]+1;si[x]=1;
    for (int j=lnk[x];j;j=nxt[j])
        if (son[j]!=pre){
            ID[son[j]]=w[j];Dfs(son[j],x);si[x]+=si[son[j]];
            if (si[son[j]]>si[SH[x]]) SH[x]=son[j];
        }
}
void HLD(int x,int lst,int pre=0){
    Lt[x]=++ti;top[x]=lst;if (SH[x]) HLD(SH[x],lst,x);
    for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre&&son[j]!=SH[x]) HLD(son[j],son[j],x);
}
void Pushdown(int p){
    int now=tag[p];tag[p]=INF;if (now==INF) return;
    MIN[p<<1]=min(MIN[p<<1],now);MIN[p<<1|1]=min(MIN[p<<1|1],now);
    tag[p<<1]=min(tag[p<<1],now);tag[p<<1|1]=min(tag[p<<1|1],now);
}
void Update(int L,int R,int k,int l=1,int r=n,int p=1){
    if (L==l&&r==R) {MIN[p]=min(MIN[p],k);tag[p]=min(tag[p],k);return;}int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) Update(L,R,k,l,mid,p<<1); else if (L>mid) Update(L,R,k,mid+1,r,p<<1|1);
    else Update(L,mid,k,l,mid,p<<1),Update(mid+1,R,k,mid+1,r,p<<1|1);MIN[p]=min(MIN[p<<1],MIN[p<<1|1]);
}
int Ask(int pos,int l=1,int r=n,int p=1){
    if (l==r) return MIN[p];int mid=l+(r-l>>1);Pushdown(p);
    if (pos<=mid) return Ask(pos,l,mid,p<<1); else return Ask(pos,mid+1,r,p<<1|1);
}
inline void Max(int x,int y,int z){
    while (top[x]^top[y]){
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        Update(Lt[top[x]],Lt[x],z);x=fa[top[x]];
    }if (dep[x]<dep[y]) swap(x,y);if (x^y) Update(Lt[y]+1,Lt[x],z);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    readi(n);readi(A);readi(B);for (int i=1;i<=n;i++) f[i]=i;
    for (int i=1,x,y;i<=A;i++) {readi(x);readi(y);Add(x,y,i);Add(y,x,i);x=getfa(x);y=getfa(y);f[x]=y;}
    for (int i=1;i<=B;i++) readi(e[i].sc.fr),readi(e[i].sc.sc),readi(e[i].fr);sort(e+1,e+1+B);
    for (int i=1;i<=B;i++){
        int fx=getfa(e[i].sc.fr),fy=getfa(e[i].sc.sc);
        if (fx!=fy) Add(e[i].sc.fr,e[i].sc.sc,0),Add(e[i].sc.sc,e[i].sc.fr,0),f[fx]=fy; else vis[i]=true;
    }
    Dfs(1);HLD(1,1);for (int i=1;i<=(n<<2);i++) MIN[i]=tag[i]=INF;
    for (int i=1;i<=B;i++) if (vis[i]) Max(e[i].sc.fr,e[i].sc.sc,e[i].fr);
    for (int i=1;i<=n;i++) if (ID[i]) {int now=Ask(Lt[i]);if (now==INF) return puts("-1"),0;ans+=now;}
    return printf("%lld\n",ans),0;
}