这题呢 就边权会在某一时刻变掉…众所周知LCT不支持删边的qwq…
所以考虑线段树分治… 直接码一发
如果 R+1 这个时间修改 那就当做 [L,R] 插入了一条边… 然后删的边和加的边存起来到栈 好删除贡献
注意一下最后一段加边…… 这题没了
#include <bits/stdc++.h>
#define rep(i , x , y) for(register int i = (x) , _## i = ((y) + 1) ; i < _## i ; i ++)
#define Rep(i , x , y) for(register int i = (x) , _## i = ((y) - 1) ; i > _## i ; i --)
using namespace std ;
#define int long long
using ll = long long ;
using pii = pair < int , int > ;
const static int _ = 1 << 20 ;
char fin[_] , * p1 = fin , * p2 = fin ;
inline char gc() { return (p1 == p2) && (p2 = (p1 = fin) + fread(fin , 1 , _ , stdin) , p1 == p2) ? EOF : * p1 ++ ; }
inline int read() {
bool sign = 1 ; char c = 0 ; while(c < 48) ((c = gc()) == 45) && (sign = 0) ;
int x = (c & 15) ; while((c = gc()) > 47) x = (x << 1) + (x << 3) + (c & 15) ;
return sign ? x : -x ;
}
template < class T > void print(T x , char c = '
') {
(x == 0) && (putchar(48)) , (x < 0) && (putchar(45) , x = -x) ;
static char _st[100] ; int _stp = 0 ;
while(x) _st[++ _stp] = x % 10 ^ 48 , x /= 10 ;
while(_stp) putchar(_st[_stp --]) ; putchar(c) ;
}
template < class T > void cmax(T & x , T y) { (x < y) && (x = y) ; }
template < class T > void cmin(T & x , T y) { (x > y) && (x = y) ; }
const int N = 5e4 + 10 ;
struct edge {
int u , v , w ;
}e[N << 2];
int n , m , q ;
vector < int > t[N << 2] ;
struct LCT {
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
int ch[N << 2][2] , fa[N << 2] , rev[N << 2] , mx[N << 2] , v[N << 2] ;
bool isroot(int x) { return ls(fa[x]) != x && rs(fa[x]) != x ; }
void pushdown(int x) {
if(rev[x]) {
if(ls(x)) rev[ls(x)] ^= 1 ;
if(rs(x)) rev[rs(x)] ^= 1 ;
rev[x] ^= 1 ; swap(ls(x) , rs(x)) ;
}
}
void pushup(int x) {
mx[x] = x ;
if(ls(x) && v[mx[ls(x)]] > v[mx[x]]) mx[x] = mx[ls(x)] ;
if(rs(x) && v[mx[rs(x)]] > v[mx[x]]) mx[x] = mx[rs(x)] ;
}
bool getr(int x) { return rs(fa[x]) == x ; }
void rotate(int x) {
int y = fa[x] , z = fa[y] , k = getr(x) , w = ch[x][k ^ 1] ;
if(! isroot(y)) ch[z][getr(y)] = x ;
fa[fa[fa[ch[ch[x][k ^ 1] = y][k] = w] = y] = x] = z ;
pushup(y) ; pushup(x) ;
}
void pushall(int x) {
if(! isroot(x)) pushall(fa[x]) ; pushdown(x) ;
}
void splay(int x) {
pushall(x) ;
while(! isroot(x)) {
int y = fa[x] ;
if(! isroot(y)) rotate(getr(x) ^ getr(y) ? x : y) ;
rotate(x) ;
}
}
void access(int x) {
for(int tp = 0 ; x ; x = fa[tp = x]) { splay(x) ; rs(x) = tp ; pushup(x) ; }
}
int findroot(int x) {
access(x) ; splay(x) ; while(ls(x)) x = ls(x) ; return x ;
}
void makeroot(int x) { access(x) ; splay(x) ; rev[x] ^= 1 ; }
void split(int x , int y) { makeroot(x) ; access(y) ; splay(y) ; }
void cut(int x, int y) { split(x , y) ;fa[x] = ls(y) = 0 ;pushup(y) ;}
void link(int x , int y) { makeroot(x) ; fa[x] = y ; }
int query(int x , int y) { return split(x , y) , mx[y] ; }
} T ;
void modify(int a , int b , int l , int r , int x , int rt) {
if(a > b) return ;
if(a <= l && r <= b) { t[rt].push_back(x) ;return ;}
int mid = l + r >> 1 ;
if(a <= mid) modify(a , b , l , mid , x , rt << 1) ;
if(b > mid) modify(a , b , mid + 1 , r , x , rt << 1 | 1) ;
}
int ss[N << 2] , st[N << 2] ;
int Ans = 0 , ans[N] , stop = 0 ;
void query(int l , int r , int rt) {
const int Stop = stop , mid = l + r >> 1 ;
for(auto p : t[rt]) {
int u = e[p].u ; int v = e[p].v ; int w = e[p].w ;
if(T.findroot(u) == T.findroot(v)) {
int mx = T.query(u , v) ;
if(T.v[mx] > w) {
T.cut(e[mx - n].u , mx) ; T.cut(e[mx - n].v , mx) ;
Ans -= e[mx - n].w ;
ss[++ stop] = mx - n ; st[stop] = 1 ;
}
else continue ;
}
T.link(p + n , u) ; T.link(p + n , v) ;
Ans += w ; ss[++ stop] = p ; st[stop] = -1 ;
}
if(l == r) ans[l] = Ans ;
else query(l , mid , rt << 1) , query(mid + 1 , r , rt << 1 | 1) ;
while(stop != Stop) {
if(st[stop] < 0) {
T.cut(ss[stop] + n , e[ss[stop]].u) ; T.cut(ss[stop] + n , e[ss[stop]].v) ;
Ans -= e[ss[stop]].w ;
}
else {
T.link(ss[stop] + n , e[ss[stop]].u) ; T.link(ss[stop] + n , e[ss[stop]].v) ;
Ans += e[ss[stop]].w ;
} stop -- ;
}
}
int L[N] , pos[N] , cnt ;
signed main() {
#ifdef _WIN64
freopen("testdata.in" , "r" , stdin) ;
#endif
n = read() ; m = read() ; q = read() ; cnt = m ;
rep(i , 1 , m) pos[i] = i , L[i] = 1 ;
rep(i , 1 , m) {
int u (read()) , v (read()) , w (read()) ; e[i] = { u , v , w } ;
}
rep(i , 1 , q) {
int k = read() , val = read() , x = pos[k] ;
modify(L[k] , i - 1 , 1 , q , x , 1) ;
L[k] = i ; e[++ cnt] = e[x] ; e[cnt].w = val ; pos[k] = cnt ;
}
rep(i , 1 , cnt) T.v[i + n] = e[i].w ;
rep(i , 1 , m) modify(L[i] , q , 1 , q , pos[i] , 1) ;
query(1 , q , 1) ; rep(i , 1 , q) print(ans[i]) ;
return 0 ;
}