离线后倒过来做，这样就跟魔法森林差不多了，缩边为点就可以统计边的权值了。
1A真是爽，可惜常数炸上了天，这是滥用stl容器和无脑link，cut的后果
#include<map>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100003;
const int M = 1000003;
void read(int &k) {
k = 0; int fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = (k << 1) + (k << 3) + c - '0';
k = k * fh;
}
struct node *null;
struct node {
node *ch[2], *fa;
int mx, mxid, d, id;
short rev;
bool pl() {return fa->ch[1] == this;}
bool check() {return fa == null || (fa->ch[0] != this && fa->ch[1] != this);}
void push() {if (rev) {rev = 0; swap(ch[0], ch[1]); ch[0]->rev ^= 1; ch[1]->rev ^= 1;}}
void count() {
mxid = id; mx = d;
if (ch[0]->mx > mx) {mx = ch[0]->mx; mxid = ch[0]->mxid;}
if (ch[1]->mx > mx) {mx = ch[1]->mx; mxid = ch[1]->mxid;}
}
void setc(node *r, bool c) {ch[c] = r; r->fa = this;}
} pool[N + M];
struct Quee{int op, u, v;} Q[N];
struct Data{int u, v, e;} E[M];
struct maa{
int u, v;
bool operator < (const maa data) const
{return u == data.u ? v < data.v : u < data.u;}
};
bool cmp(Data A, Data B) {return A.e < B.e;}
map <maa, int> ma;
bool cannot[M];
namespace LCT {
int fa[N];
int find(int x) {return fa[x] == x ? x : (fa[x] = find(fa[x]));}
void rotate(node *r) {
node *f = r->fa;
bool c = r->pl();
if (f->check()) r->fa = f->fa;
else f->fa->setc(r, f->pl());
f->setc(r->ch[!c], c);
r->setc(f, !c);
f->count();
}
void update(node *r) {if (!r->check()) update(r->fa); r->push();}
void splay(node *r) {
update(r);
for(; !r->check(); rotate(r))
if (!r->fa->check()) rotate(r->pl() == r->fa->pl() ? r->fa : r);
r->count();
}
node *access(node *r) {node *y = null; for(; r != null; y = r, r = r->fa) splay(r), r->ch[1] = y; return y;}
void changert(node *r) {access(r)->rev ^= 1; splay(r);}
void link(node *r, node *t) {changert(r); r->fa = t;}
void cut(node *r, node *t) {changert(r); access(t); splay(t); t->ch[0]->fa = null; t->ch[0] = null;}
node *findrt(node *r) {access(r); splay(r); while (r->ch[0] != null) r = r->ch[0]; return r;}
void newnode(int k, int num) {
pool[k].ch[0] = pool[k].ch[1] = pool[k].fa = null;
pool[k].id = pool[k].mxid = k; pool[k].d = pool[k].mx = num; pool[k].rev = 0;
}
int A[N];
void Build(int n, int m, int q) {
null = &pool[0];
null->ch[0] = null->ch[1] = null->fa = null;
null->id = null->d = null->mx = null->mxid = null->rev = 0;
int u, v, e;
for(int i = 1; i <= n; ++i) newnode(i, 0);
for(int i = 1; i <= m; ++i) {
read(u); read(v); read(e);
if (u > v) swap(u, v);
E[i] = (Data) {u, v, e};
}
sort(E + 1, E + m + 1, cmp);
for(int i = 1; i <= m; ++i) {
ma[(maa) {E[i].u, E[i].v}] = i;
newnode(i + n, E[i].e);
}
for(int i = 1; i <= q; ++i) {
read(Q[i].op); read(Q[i].u); read(Q[i].v);
if (Q[i].u > Q[i].v) swap(Q[i].u, Q[i].v);
if (Q[i].op == 2) cannot[ma[(maa) {Q[i].u, Q[i].v}]] = 1;
}
node *tox, *toy, *toe;
int cnt = 0, x, y, fx, fy;
for(int i = 1; i <= n; ++i) fa[i] = i;
for(int i = 1; i <= m; ++i) {
x = E[i].u; y = E[i].v;
fx = find(x); fy = find(y);
if (fx != fy && !cannot[e = ma[(maa) {x, y}]]) {
++cnt;
fa[fx] = fy;
tox = &pool[x]; toy = &pool[y]; toe = &pool[e + n];
link(tox, toe); link(toy, toe);
if (cnt == n - 1) break;
}
}
cnt = 0;
for(int i = q; i >= 1; --i) {
if (Q[i].op == 1) {
tox = &pool[Q[i].u]; toy = &pool[Q[i].v];
changert(tox); access(toy); splay(toy);
A[++cnt] = toy->mx;
} else {
tox = &pool[Q[i].u]; toy = &pool[Q[i].v];
e = ma[(maa) {Q[i].u, Q[i].v}];
changert(tox); access(toy); splay(toy);
if (E[e].e < toy->mx) {
u = toy->mxid - n;
tox = &pool[E[u].u]; toy = &pool[E[u].v]; toe = &pool[u + n];
cut(tox, toe); cut(toy, toe);
tox = &pool[Q[i].u]; toy = &pool[Q[i].v]; toe = &pool[e + n];
link(tox, toe); link(toy, toe);
}
}
}
for(int i = cnt; i; --i) printf("%d
", A[i]);
}
}
int n, m, q;
int main() {
read(n); read(m); read(q);
LCT::Build(n, m, q);
return 0;
}
模板一定不能写残啊，想起一个月前Round1Day1调LCT的模板调了4h，查出各种手残的错误QAQ然而并没有什么用。