描述

有一个无向图，有n个点，m₁条第一类边和m₂条第二类边。第一类边有边权，第二类边无边权。请为第二类的每条边定义一个边权，使得第二类边可能全部出现在该无向图的最小生成树上，同时要求第二类边的边权总和尽可能大。
注：第二类边不会形成环

输入

第一行三个数n，m₂，m₁

接下来m₂行，每行两个数，描述一条第二类边，分别表示两个端点接下来m₁行，每行三个数，描述一条第一类边，分别表示两个端点和边权

对于30%的数据，n ≤ 5

对于60%的数据，n ≤ 1000

对于100%的数据，1 ≤ n ≤ 100000, m₁ ≤ 2 × n, m₂ < n

输出

输出一个数，表示第二类边的权值总和最大可能为多少。（若可能为无穷大则输出-1）

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

const int inf=1e9;

int x[maxn],y[maxn],Laxt[maxn],Next[maxn],To[maxn],Len[maxn];

int fa[maxn],Mx[maxn],tot,N,cnt,dep[maxn];

int a[maxn],sz[maxn],son[maxn],Top[maxn],p[maxn],q[maxn];

struct in{ int u,v,cost; }s[maxn];

bool cmp(in p,in q){ return p.cost<q.cost;}

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

void add(int u,int v,int c){

    Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; Len[cnt]=c;

}

void dfs1(int u,int f){

    dep[u]=dep[f]+; fa[u]=f; sz[u]=;

    for(int i=Laxt[u];i;i=Next[i])

       if(To[i]!=f) {

         dfs1(To[i],u),sz[u]+=sz[To[i]];

         a[To[i]]=Len[i];

         if(sz[To[i]]>sz[son[u]]) son[u]=To[i];

    }

}

void dfs2(int u,int top)

{

    Top[u]=top; p[++tot]=u; q[u]=tot;

    if(son[u]) dfs2(son[u],top);

    for(int i=Laxt[u];i;i=Next[i]){

        if(To[i]!=son[u]&&dep[To[i]]>dep[u])

          dfs2(To[i],To[i]);

    }

}

void build(int Now,int L,int R)

{

    if(L==R) { Mx[Now]=a[p[L]]; return ;}

    int Mid=(L+R)>>;

    build(Now<<,L,Mid); build(Now<<|,Mid+,R);

    Mx[Now]=max(Mx[Now<<],Mx[Now<<|]);

}

int query(int Now,int L,int R,int l,int r)

{

    if(Mx[Now]<inf) return ;

    if(L==R){Mx[Now]=; return ;}

    int Mid=(L+R)>>,res=;

    if(l<=Mid) res+=query(Now<<,L,Mid,l,r);

    if(r>Mid) res+=query(Now<<|,Mid+,R,l,r);

    Mx[Now]=max(Mx[Now<<],Mx[Now<<|]);

    return res;

}

int Query(int u,int v)

{

    int f1=Top[u],f2=Top[v],res=;

    while(f1!=f2){

        if(dep[f1]<dep[f2]) swap(f1,f2),swap(u,v);

        res+=query(,,N,q[f1],q[u]);

        u=fa[f1]; f1=Top[u];

    }

    if(u!=v){

        if(dep[u]>dep[v]) swap(u,v);

        res+=query(,,N,q[son[u]],q[v]);

    }

    return res;

}

int main()

{

    int A,B; ll ans=;

    scanf("%d%d%d",&N,&A,&B);

    rep(i,,N) ff[i]=i;

    rep(i,,A){

        scanf("%d%d",&x[i],&y[i]);

        int fu=find(x[i]),fv=find(y[i]);

        ff[fu]=fv;

        add(x[i],y[i],inf); add(y[i],x[i],inf);

    }

    rep(i,,B) scanf("%d%d%d",&s[i].u,&s[i].v,&s[i].cost);

    sort(s+,s+B+,cmp);

    rep(i,,B) {

        int fu=find(s[i].u),fv=find(s[i].v);

        if(fu==fv) s[++tot]=s[i];

        else { ff[fu]=fv;

            add(s[i].u,s[i].v,s[i].cost);

            add(s[i].v,s[i].u,s[i].cost);

        }

    }

    B=tot; tot=;

    dfs1(,); dfs2(,);

    build(,,N); tot=;

    rep(i,,B){

        tot=Query(s[i].u,s[i].v);

        ans+=(ll)tot*s[i].cost;

    }

    if(Mx[]==inf) puts("-1");

    else printf("%lld\n",ans);

    return ;

}