题解:
对整个修改的区间进行分治。对于当前修改区间来说,我们对整幅图中将要修改的边权都先改成-inf,跑一遍最小生成树,然后对于一条树边并且他的权值不为-inf,那么这条边一定就是树边了。然后我们把这些点都缩成一个点。然后,我们继续对当前修改区间来说,我们把要修改的边的边权都修改成inf,跑一遍最小生成树,然后对于一条非树边来说,他的边权不为inf,那么这条边一点是非树边了,然后我们每层缩点,减边,这样图就会越来越小,然后当l == r的时候,我们还原修改操作,最后把跑最小生成树计算答案。
一道神奇的cdq题目。
代码:
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod = (int)1e9+;
const int N = 1e5 + ;
struct Node{
int u, v, c, id;
bool operator < (const Node & x) const{
return c < x.c;
}
}e[][N], f[N], g[N];
int a[N], b[N], ct[N], mapid[N];
int pre[N];
int to[N];
void link(int u, int v){
mapid[to[v]] = ;
mapid[u] = v;
to[v] = u;
}
int Find(int x){
if(x == pre[x]) return x;
return pre[x] = Find(pre[x]);
}
LL ans[N];
void Clear(int tot){
for(int i = ; i <= tot; i++){
pre[f[i].u] = f[i].u;
pre[f[i].v] = f[i].v;
}
}
void contraction(int &tot, LL &sum){
Clear(tot);
sort(f+, f++tot);
int u, v, zz = ;
for(int i = ; i <= tot; i++){
u = Find(f[i].u), v = Find(f[i].v);
if(u != v){
pre[u] = v;
if(f[i].c != -inf){
sum += f[i].c;
g[++zz] = f[i];
}
}
}
Clear(tot);
for(int i = ; i <= zz; i++){
u = Find(g[i].u); v = Find(g[i].v);
pre[u] = v;
}
zz = ;
for(int i = ; i <= tot; i++){
u = Find(f[i].u), v = Find(f[i].v);
if(u != v){
f[++zz] = f[i];
f[zz].u = u;
f[zz].v = v;
mapid[f[i].id] = zz;
}
}
tot = zz;
return ;
}
void reduction(int &tot){
Clear(tot);
sort(f+, f++tot);
int u, v, zz = ;
for(int i = ; i <= tot; i++){
u = Find(f[i].u); v = Find(f[i].v);
if(u != v){
pre[u] = v;
f[++zz] = f[i];
}
else if(f[i].c == inf)
f[++zz] = f[i];
}
tot = zz;
return ;
}
void cdq(int l, int r, int now, int tot, LL sum){
if(l == r) ct[a[l]] = b[l];
for(int i = ; i <= tot; i++){
e[now][i].c = ct[e[now][i].id];
mapid[e[now][i].id] = i;
//link(e[now][i])
f[i] = e[now][i];
}
if(l == r){
ans[l] = sum;
Clear(tot);
sort(f+, f++tot);
int u, v;
for(int i = ; i <= tot; i++){
u = Find(f[i].u), v = Find(f[i].v);
if(u != v){
pre[u] = v;
ans[l] += f[i].c;
}
}
return ;
}
for(int i = l; i <= r; i++) f[mapid[a[i]]].c = -inf;
contraction(tot, sum);
for(int i = l; i <= r; i++) f[mapid[a[i]]].c = inf;
reduction(tot);
for(int i = ; i <= tot; i++) e[now+][i] = f[i];
int mid = l+r >> ;
cdq(l, mid, now+, tot, sum);
cdq(mid+, r, now+, tot, sum); }
int main(){
int n, m, q;
scanf("%d%d%d", &n, &m, &q);
for(int i = ; i <= m; i++){
scanf("%d%d%d", &e[][i].u, &e[][i].v, &e[][i].c);
e[][i].id = i;
ct[i] = e[][i].c;
}
for(int i = ; i <= q; i++)
scanf("%d%d", &a[i], &b[i]);
cdq(,q,,m,);
for(int i = ; i <= q; ++i)
printf("%lld\n", ans[i]);
return ;
}