线段树分治+LCT，同样做法的老哥跑过了我愣是TLE了，求dalao教教我/kk

https://www.luogu.com.cn/record/123548961

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define mr make_pair
#define fi first
#define se second
using namespace std;
const int N = 3e5 + 5;
int n, m, q;
bool qr[N];
ll sum;
struct Ed{
    int u, v, w, id;
}e1[N], e2[N];

namespace LCT{
    int fa[N], ch[N][2], ma[N], val[N], tag[N], stk[N];
    void pushup(int p) {
        ma[p] = val[p];
        int ls = ma[ch[p][0]], rs = ma[ch[p][1]];
        if(e2[ma[p]].w < e2[ls].w) ma[p] = ls; 
        if(e2[ma[p]].w < e2[rs].w) ma[p] = rs;
        return ; 
    }
    int child(int x) {
        return (ch[fa[x]][1] == x);
    }
    bool notroot(int x) {
        return (ch[fa[x]][0] == x || ch[fa[x]][1] == x);
    }
    void reverse(int x) {
        swap(ch[x][0], ch[x][1]), tag[x] ^= 1;
        return ;
    }
    void pushdown(int x) {
        if(tag[x]) {
            if(ch[x][0]) reverse(ch[x][0]);
            if(ch[x][1]) reverse(ch[x][1]);
            tag[x] = 0;
        }
        return ;
    }
    void rotate(int x) {
        int y = fa[x], z = fa[y], k = child(x), w = ch[x][k ^ 1];
        if(notroot(y)) ch[z][child(y)] = x;
        ch[x][k ^ 1] = y, ch[y][k] = w;
        if(w) fa[w] = y;
        fa[y] = x, fa[x] = z;
        pushup(y); return ;
    }
    void splay(int x) {
        int top = 0, y = x, z;
        stk[++top] = y;
        while(notroot(y)) stk[++top] = (y = fa[y]);
        while(top) pushdown(stk[top--]);
        while(notroot(x)) {
            y = fa[x], z = fa[y];
            if(notroot(y)) {
                if(child(x) == child(y)) rotate(y);
                else rotate(x);
            }
            rotate(x);
        }
        pushup(x); return ;
    }
    void access(int x) {
        for (int y = 0; x; y = x, x = fa[y]) {
            splay(x), ch[x][1] = y, pushup(x);
        }
        return ;
    }
    void makeroot(int x) {
        access(x), splay(x);
        reverse(x); return ;
    }
    int findroot(int x) {
        access(x), splay(x);
        while(ch[x][0]) pushdown(x), x = ch[x][0];
        splay(x); return x;
    }
    void makepath(int x, int y) {
        makeroot(x), access(y), splay(y);
        return ;
    }
    void link(int x, int y) {
        makeroot(x);
        if(findroot(y) != x) fa[x] = y;
    }
    void cut(int x, int y) {
        makeroot(x);
        if(findroot(y) == x && fa[y] == x && (!ch[y][0])) {
            fa[y] = ch[x][1] = 0, pushup(x);
        }
    }
} using namespace LCT;

vector <int> tr[N << 2];
vector <pii> del;

void modify(int p, int l, int r, int x, int y, int v) {
    if(x <= l && r <= y) {
        tr[p].emplace_back(v); return ;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) modify(p << 1, l, mid, x, y, v);
    if(y > mid) modify(p << 1 | 1, mid + 1, r, x, y, v);
    return ;
}

void insert(int d) {
    int u = e2[d].u, v = e2[d].v, w = e2[d].w, id = e2[d].id;
    makeroot(u);
    if(findroot(v) != u) {
        sum += w;
        link(u, id + n), link(v, id + n);
        del.emplace_back(mr(id, -1));
        return ;
    }
    makepath(u, v);
    int mx = ma[v];
    if(w < e2[mx].w) {
        sum -= e2[mx].w, sum += w;
        cut(e2[mx].u, e2[mx].id + n), cut(e2[mx].v, e2[mx].id + n);
        del.emplace_back(mr(mx, 1));
        link(u, id + n), link(v, id + n);
        del.emplace_back(mr(id, -1));
    }
    return ;
}

void undo() {
    int id = del.back().fi, op = del.back().se;
    if(op == 1) {
        link(e2[id].u, e2[id].id + n), link(e2[id].v, e2[id].id + n);
    } 
    else {
        cut(e2[id].u, e2[id].id + n), cut(e2[id].v, e2[id].id + n);
    }
    del.pop_back(); return ;
}

void dele(int cnt) {
    while(del.size() > cnt) undo();
    return ;
}

void query(int p, int l, int r) {
    ll summ = sum; int cnt = del.size();
    for (int i : tr[p]) insert(i);
    if(l == r) {
        if(l <= q) printf("%lld\n", sum);
        sum = summ, dele(cnt);
        return ;
    }
    int mid = (l + r) >> 1;
    query(p << 1, l, mid), query(p << 1 | 1, mid + 1, r);
    sum = summ, dele(cnt);
    return ;
}

vector <pii> tim[N];

int main() {
    scanf("%d %d %d", &n, &m, &q);
    for (int i = 1; i <= m; ++i) {
        scanf("%d %d %d", &e1[i].u, &e1[i].v, &e1[i].w);
        tim[i].emplace_back(mr(e1[i].w, 1));
    }
    for (int i = 1; i <= q; ++i) {
        int k, d; scanf("%d %d", &k, &d);
        tim[k].emplace_back(mr(d, i));
    }
    int mm = 0;
    for (int i = 1; i <= m; ++i) {
        tim[i].emplace_back(mr(e1[i].w, q + 1));
        for (int j = 1; j < tim[i].size(); ++j) {
            int l = tim[i][j - 1].se, r = tim[i][j].se - 1;
            if(l <= r) {
                e2[++mm] = {e1[i].u, e1[i].v, tim[i][j - 1].fi, mm};
                val[mm + n] = mm;
                modify(1, 1, q + 1, l, r, mm);
            }
        }
    }
    m = mm;
    query(1, 1, q + 1);
    return 0;
}