描述
有一个无向图，有n个点，m1条第一类边和m2条第二类边。第一类边有边权，第二类边无边权。请为第二类的每条边定义一个边权，使得第二类边可能全部出现在该无向图的最小生成树上，同时要求第二类边的边权总和尽可能大。
注：第二类边不会形成环
输入
第一行三个数n，m2，m1
接下来m2行，每行两个数，描述一条第二类边，分别表示两个端点接下来m1行，每行三个数，描述一条第一类边，分别表示两个端点和边权
对于30%的数据，n ≤ 5
对于60%的数据，n ≤ 1000
对于100%的数据，1 ≤ n ≤ 100000, m1 ≤ 2 × n, m2 < n
输出
输出一个数，表示第二类边的权值总和最大可能为多少。（若可能为无穷大则输出-1）
- 样例输入
-
5 2 3
1 2
4 5
2 3 100
3 4 100
1 5 1000 - 样例输出
-
2000
题解：
将所有第二类边权当作0处理，先构造出生成树。
之后对于不在生成树上的边e，我们尝试加入e，如果构成的环中有一条边大于e则将那条边用e代替更优。
所以我们构造出生成树后，令第二类边权值为x = inf，每次对于一条不在生成树中的边权值w，让环上的第二类边权值x = min(x, w)，即树上的链赋值操作，树链剖分即可。
#include <bits/stdc++.h> #define ll long long
#define ull unsigned long long
#define st first
#define nd second
#define pii pair<int, int>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define tiii tuple<int, int, int>
#define pw(x) ((1LL)<<(x))
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sqr(x) ((x)*(x))
#define SIZE(A) ((int)(A.size()))
#define LENGTH(A) ((int)(A.length()))
#define FIN freopen("A.in","r",stdin);
#define FOUT freopen("A.out","w",stdout);
using namespace std;
/***********/ template<typename T>
bool scan (T &ret) {
char c;
int sgn;
if (c = getchar(), c == EOF) return ; //EOF
while (c != '-' && (c < '' || c > '') ) c = getchar();
sgn = (c == '-') ? - : ;
ret = (c == '-') ? : (c - '');
while (c = getchar(), c >= '' && c <= '') ret = ret * + (c - '');
ret *= sgn;
return ;
}
template<typename N,typename PN>inline N flo(N a,PN b){return a>=?a/b:-((-a-)/b)-;}
template<typename N,typename PN>inline N cei(N a,PN b){return a>?(a-)/b+:-(-a/b);}
template<typename T>inline int sgn(T a) {return a>?:(a<?-:);}
template<class T> int countbit(const T &n) { return (n==)?:(+countbit(n&(n-))); }
template <class T1, class T2>
bool gmax(T1 &a, const T2 &b) { return a < b? a = b, :;}
template <class T1, class T2>
bool gmin(T1 &a, const T2 &b) { return a > b? a = b, :;}
template <class T> inline T lowbit(T x) {return x&(-x);} template<class T1, class T2>
ostream& operator <<(ostream &out, pair<T1, T2> p) {
return out << "(" << p.st << ", " << p.nd << ")";
}
template<class A, class B, class C>
ostream& operator <<(ostream &out, tuple<A, B, C> t) {
return out << "(" << get<>(t) << ", " << get<>(t) << ", " << get<>(t) << ")";
}
template<class T>
ostream& operator <<(ostream &out, vector<T> vec) {
out << "("; for(auto &x: vec) out << x << ", "; return out << ")";
}
void testTle(int &a){
while() a = a*(ll)a%;
}
const ll inf = 0x3f3f3f3f;
const ll INF = 1e17;
const int mod = 1e9+;
const double eps = 1e-;
const int N = +;
const double pi = acos(-1.0); /***********/ struct Edge{
int x, y, w;
};
Edge edge1[N+N], edge2[N];
vector<pii> ve[N]; int n, m1, m2;
int fa[N];
int findf(int x) { return x == fa[x]? x: fa[x] = findf(fa[x]);} int dfn, f[N], fdis[N], d[N], size[N], son[N], top[N], st[N], en[N];
struct Node {
int maxval;
int tag;
};
Node T[N<<];
int a[N]; void pushup(int rt) {
T[rt].maxval = max(T[rt<<].maxval, T[rt<<|].maxval);
}
void pushdown(int rt) {//区间赋的值递增，之后赋的值必大于之前赋的值，故已有赋值则可跳过
if(T[rt].tag) {
if(!T[rt<<].tag&&T[rt<<].maxval > T[rt].tag)
T[rt<<].tag = T[rt].tag;
if(!T[rt<<|].tag&&T[rt<<|].maxval > T[rt].tag)
T[rt<<|].tag = T[rt].tag;
T[rt].tag = ;
}
if(T[rt].tag) {
if(!T[rt<<].tag&&T[rt<<].maxval > T[rt].tag)
T[rt<<].tag = T[rt].tag;
if(!T[rt<<|].tag&&T[rt<<|].maxval > T[rt].tag)
T[rt<<|].tag = T[rt].tag;
T[rt].tag = ;
}
}
void build(int l, int r, int rt) {
if(l == r) {
T[rt] = {a[l], };
return ;
}
int m = (l+r) >> ;
build(lson);
build(rson);
pushup(rt);
}
void update(int L, int R, int val, int l, int r, int rt) {
if(L <= l&&r <= R) {
if(T[rt].tag == ||T[rt].tag > val) T[rt].tag = val;
return ;
}
pushdown(rt);
int m = (l+r) >> ;
if(L <= m) update(L, R, val, lson);
if(R > m) update(L, R, val, rson);
} void dfs(int x){
size[x] = ;
for(pii e: ve[x]) {
int y = e.st;
if(y != f[x]){
f[y] = x, d[y] = d[x]+;
fdis[y] = e.nd;
dfs(y), size[x] += size[y];
if(size[y] > size[son[x]])
son[x] = y;
}
}
}
void dfs2(int x, int y){
st[x] = ++dfn; top[x] = y; a[dfn] = fdis[x];
if(son[x]) dfs2(son[x], y);
for(pii e: ve[x]) {
int y = e.st;
if(y != son[x]&&y != f[x])
dfs2(y, y);
}
en[x]=dfn;
}
//查询x,y两点的lca
int lca(int x,int y){
for(;top[x]!=top[y];x=f[top[x]])if(d[top[x]]<d[top[y]]) swap(x, y);
return d[x]<d[y]?x:y;
}
//x是y的祖先，查询x到y方向的第一个点
int lca2(int x, int y){
int t;
while(top[x]!=top[y])t=top[y],y=f[top[y]];
return x==y?t:son[x];
}
//对x到y路径上的点进行操作
void chain(int x, int y, int val){
for(;top[x]!=top[y];x=f[top[x]]){
if(d[top[x]]<d[top[y]]) swap(x, y);
//change(st[top[x]],st[x]);
update(st[top[x]], st[x], val, , n, );
}
if(d[x]<d[y]) swap(x, y);
//change(st[y],st[x]);
update(st[y], st[x], val, , n, );
} long long ans;
bool solve(int l, int r, int rt) {
if(T[rt].maxval != inf) return true;
if(l == r) {
if(T[rt].tag == ) return false;
ans += T[rt].tag;
return true;
}
pushdown(rt);
int m = (l+r) >> ;
return solve(lson) && solve(rson);
}
int main() {
scanf("%d%d%d", &n, &m2, &m1);
for(int i = , x, y; i < m2; i++) {
scanf("%d%d", &x, &y);
edge2[i] = {x, y, };
}
for(int i = , x, y, w; i < m1; i++) {
scanf("%d%d%d", &x, &y, &w);
edge1[i] = {x, y, w};
} sort(edge1, edge1+m1, [](Edge e1, Edge e2) { return e1.w < e2.w; });
for(int i = ; i <= n; i++) fa[i] = i;
for(int i = ; i < m2; i++) {
Edge e = edge2[i];
int fx = findf(e.x), fy = findf(e.y);
if(fx != fy) {
fa[fx] = fy;
ve[e.x].push_back({e.y, inf});
ve[e.y].push_back({e.x, inf});
}
}
vector<Edge> tmp;
for(int i = ; i < m1; i++) {
Edge e = edge1[i];
int fx = findf(e.x), fy = findf(e.y);
if(fx != fy) {
fa[fx] = fy;
ve[e.x].push_back({e.y, e.w});
ve[e.y].push_back({e.x, e.w});
}
else tmp.push_back(e);//将e.x -> e.y路径上的边w = min(w, e.w);
} dfs();
dfs2(, );
build(, n, );
for(Edge e: tmp) {
int x = e.x, y = e.y, w = e.w;
int ancestor = lca(x, y);
if(ancestor != x) {
int xx = lca2(ancestor, x);
chain(xx, x, w);
}
if(ancestor != y) {
int yy = lca2(ancestor, y);
chain(yy, y, w);
}
}
printf("%lld\n", solve(, n, )? ans: -);
return ;
}