正确解题

#include <bits/stdc++.h>
using namespace std;

/*

• A21358 鍩庡競寤鸿 (HNOI2010 / BZOJ2001 / 娲涜胺P3206) 鈥斺€?鍔ㄦ€佹渶灏忕敓鎴愭爲
• 瑙ｆ硶锛氬璇㈤棶鏃堕棿杞村仛鍒嗘不(CDQ/绾挎鏍戝垎娌?锛屾瘡涓妭鐐瑰仛涓ゆ瑙勬ā缂╁噺锛?
• Reduction(缂╄竟)锛氫粎鐢ㄥ浐瀹氳竟(鏈尯闂村唴鏉冨€间笉鍙樼殑杈?璺?Kruskal锛岃惤閫夊浐瀹氳竟

•                琚竴鏉″叏鍥哄畾涓旀洿杞荤殑璺緞鏇夸唬锛屼换浣曟椂鍒婚兘涓嶅彲鑳借繘 MST锛屼涪寮冿紱
  

• Contraction(缂╃偣)锛氭妸鍔ㄦ€佽竟瑙嗕綔 -inf 鎺掑簭鍚庝笌鍥哄畾杈逛竴璧疯窇 Kruskal锛?

•                浠嶅叆閫夌殑鍥哄畾杈瑰湪浠讳綍鏉冨€间笅蹇呴€夛紝鏉冨€煎苟鍏ョ瓟妗堛€佷袱绔缉鎴愪竴鐐广€?
  

• 缂╃偣鍚庡姩鎬佽竟涓庡墿浣欏浐瀹氳竟浼犵粰瀛愬尯闂达紝瑙勬ā闄嶄负 O(鍖洪棿闀?锛?
• 鐢ㄥ彲鎾ら攢骞舵煡闆?鎸夊ぇ灏忓悎骞躲€佹棤璺緞鍘嬬缉)鏀寔鍥炴函銆?
• 鏉冨€奸噰鐢ㄥ叏灞€鏁扮粍 + 鍙跺瓙澶勨€滀慨鏀逛负 d鈥濈殑璇箟锛屾寜鏃堕棿椤哄簭璁块棶鍙跺瓙锛?
• 宸﹀崐鍖虹殑淇敼鑷姩瀵瑰彸鍗婂尯鐢熸晥锛屾棤闇€鏄惧紡浼犻€掓潈鍊兼洿鏂般€?
• 澶嶆潅搴︼細O((m + q log q) log n) 绾у埆銆?
  */

struct Edge { int u, v, id; };

int n, m, q;
int U[50005], V[50005], W[50005]; // 鍏ㄥ眬绔偣/鏉冨€硷紙W 闅忓彾瀛愭帹杩涜淇敼锛?
int K[50005], D[50005]; // 绗?t 鏉¤闂細杈?K[t] 浠ｄ环鏀逛负 D[t]
int inDyn[50005], curStamp;

// ---- 鍙挙閿€骞舵煡闆?----
vector<int> fa, sz;
struct Rec { int c, p, sp; };
vector<Rec> stk;
inline int findx(int x) { while (fa[x] != x) x = fa[x]; return x; }
inline bool unite(int a, int b) {
a = findx(a); b = findx(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b);
stk.push_back({b, a, sz[a]});
fa[b] = a; sz[a] += sz[b];
return true;
}
inline void rollback(size_t snap) {
while (stk.size() > snap) {
Rec s = stk.back(); stk.pop_back();
fa[s.c] = s.c; sz[s.p] = s.sp;
}
}

long long curAns, res[50005];

void solve(int l, int r, vector<Edge> E) {
if (l == r) {
// 搴旂敤姘镐箙淇敼锛氳竟 K[l] 鏉冨€煎彉涓?D[l]
W[K[l]] = D[l];
size_t snap = stk.size();
long long ansIn = curAns;
sort(E.begin(), E.end(), [](const Edge &a, const Edge &b) { return W[a.id] < W[b.id]; });
for (const Edge &e : E)
if (unite(e.u, e.v)) curAns += W[e.id];
res[l] = curAns;
rollback(snap);
curAns = ansIn;
return;
}
int mid = (l + r) >> 1;
long long ansIn = curAns;

// 鏍囪鏈尯闂村唴浼氳淇敼鐨勮竟锛堝姩鎬佽竟锛?
++curStamp;
vector<int> touched;
for (int t = l; t <= r; ++t)
    if (inDyn[K[t]] != curStamp) { inDyn[K[t]] = curStamp; touched.push_back(K[t]); }
auto isDyn = [&](int id) { return inDyn[id] == curStamp; };

// ---- Reduction锛氬浐瀹氳竟鍗曠嫭 Kruskal锛岃惤閫夊浐瀹氳竟姘镐箙鏃犵敤锛屼涪寮?----
vector<Edge> fixed, dyn, Fsel;
for (const Edge &e : E) (isDyn(e.id) ? dyn : fixed).push_back(e);
sort(fixed.begin(), fixed.end(), [](const Edge &a, const Edge &b) { return W[a.id] < W[b.id]; });
{
    size_t snap = stk.size();
    for (const Edge &e : fixed)
        if (unite(e.u, e.v)) Fsel.push_back(e);
    rollback(snap);
}

// ---- Contraction锛氬姩鎬佽竟瑙嗕綔 -inf锛屼笌 Fsel 涓€璧?Kruskal锛屽叆閫夌殑鍥哄畾杈瑰繀閫夊苟缂╃偣 ----
vector<Edge> all;
all.reserve(Fsel.size() + dyn.size());
for (const Edge &e : dyn)  all.push_back(e);              // -inf 娈?
for (const Edge &e : Fsel) all.push_back(e);
sort(all.begin() + dyn.size(), all.end(),
     [](const Edge &a, const Edge &b) { return W[a.id] < W[b.id]; });
size_t snapB = stk.size();
vector<int> isLocked(all.size(), 0);
for (size_t i = 0; i < all.size(); ++i)
    if (unite(all[i].u, all[i].v) && i >= dyn.size()) isLocked[i] = 1;
rollback(snapB);

// 鍙悎骞跺繀閫夊浐瀹氳竟锛屾瀯閫犵缉鐐瑰悗瑙勬ā鏇村皬鐨勫瓙闂杈归泦
size_t snapC = stk.size();
for (size_t i = dyn.size(); i < all.size(); ++i)
    if (isLocked[i]) { unite(all[i].u, all[i].v); curAns += W[all[i].id]; }

vector<Edge> E2;
E2.reserve(all.size());
for (size_t i = 0; i < all.size(); ++i)
    if (!isLocked[i]) E2.push_back({findx(all[i].u), findx(all[i].v), all[i].id});

for (int id : touched) inDyn[id] = 0;   // 瀛愬尯闂翠細鎸夎嚜宸辩殑鑼冨洿閲嶆柊鏍囪

solve(l, mid, E2);
solve(mid + 1, r, E2);

rollback(snapC);
curAns = ansIn;

}

int main() {
if (scanf("%d%d%d", &n, &m, &q) != 3) return 0;
for (int i = 1; i <= m; ++i) scanf("%d%d%d", &U[i], &V[i], &W[i]);
for (int t = 1; t <= q; ++t) scanf("%d%d", &K[t], &D[t]);

fa.resize(n + 1); sz.assign(n + 1, 1);
for (int i = 0; i <= n; ++i) fa[i] = i;
stk.reserve(1 << 18);

vector<Edge> E;
E.reserve(m);
for (int i = 1; i <= m; ++i) E.push_back({U[i], V[i], i});

solve(1, q, E);

for (int t = 1; t <= q; ++t) printf("%lld\n", res[t]);
return 0;

}