今天终于找到了一种比较方便好懂的用LCT维护生成树的办法。
以前用(mrclr)的方法……不是很理解，然后我写在这道题的时候还错了……
首先先看一下这道题。这很明显就是让我们动态的维护一个最小生成树。不过因为删边的过程很难维护，所以我们改成先把边存起来，之后倒序回加。
一开始我们先用LCT模拟kruskal，之后如果遇到一个环，那么我们就找到当前路径上边权最大的边与加入的边进行比较即可。
查询的时候提取路径并输出答案。
至于维护，我们可以把边看成一个点，之后把这条边所连接的两个点分别与它连边，切开的时候也是这样。对于维护最大值所在的位置，我们在pushup的时候，分别用左右儿子的pos更新即可。
代码写的比较丑……比较长……我是用邻接矩阵存的两点之间边的编号（因为数据范围小），也可以使用pair或者map。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define B puts("oops");
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
#define enter putchar('
')
#define pr pair<int,int>
#define mp make_pair
#define fi first
#define sc second
using namespace std;
typedef long long ll;
const int M = 200005;
const int N = 10000005;
int read()
{
int ans = 0,op = 1;char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') op = -1;ch = getchar();}
while(ch >='0' && ch <= '9') ans = ans * 10 + ch - '0',ch = getchar();
return ans * op;
}
int n,m,k,head[M],ecnt,sta[M],top,q,x,y,G[1005][1005],ans[M],cnt;
bool vis[M<<1];
struct ask
{
int x,y,op;
}a[M<<1];
struct edge
{
int next,from,to,id,v;
bool operator < (const edge &g) const {return v < g.v;}
}e[M<<1];
struct tree
{
int rev,fa,ch[2],pos;
}t[M<<2];
bool nroot(int x) {return t[t[x].fa].ch[0] == x || t[t[x].fa].ch[1] == x;}
bool get(int x) {return t[t[x].fa].ch[1] == x;}
void rever(int x) {swap(t[x].ch[0],t[x].ch[1]),t[x].rev ^= 1;}
void pushup(int x)
{
t[x].pos = x;
if(e[t[x].pos].v < e[t[t[x].ch[0]].pos].v) t[x].pos = t[t[x].ch[0]].pos;
if(e[t[x].pos].v < e[t[t[x].ch[1]].pos].v) t[x].pos = t[t[x].ch[1]].pos;
}
void pushdown(int x) {if(t[x].rev) rever(t[x].ch[0]),rever(t[x].ch[1]),t[x].rev = 0;}
void rotate(int x)
{
int y = t[x].fa,z = t[y].fa,k = get(x);
if(nroot(y)) t[z].ch[get(y)] = x;
t[x].fa = z,t[y].ch[k] = t[x].ch[k^1],t[t[y].ch[k]].fa = y;
t[x].ch[k^1] = y,t[y].fa = x;
pushup(y),pushup(x);
}
void splay(int x)
{
int p = x;sta[++top] = p;
while(nroot(p)) p = t[p].fa,sta[++top] = p;
while(top) pushdown(sta[top--]);
while(nroot(x))
{
int y = t[x].fa,z = t[y].fa;
if(nroot(y)) ((t[y].ch[0] == x) ^ (t[z].ch[0] == y)) ? rotate(x) : rotate(y);
rotate(x);
}
}
void access(int x) {for(int g = 0;x;g = x,x = t[x].fa) splay(x),t[x].ch[1] = g,pushup(x);}
void makeroot(int x) {access(x),splay(x),rever(x);}
int findroot(int x)
{
access(x),splay(x);
while(t[x].ch[0]) pushdown(x),x = t[x].ch[0];
return x;
}
void split(int x,int y) {makeroot(x),access(y),splay(y);}
void link(int x,int y){makeroot(x);if(findroot(y) != x) t[x].fa = y;}
void cut(int x,int y) {split(x,y),t[x].fa = t[y].ch[0] = 0,pushup(y);}
int main()
{
n = read(),m = read(),q = read();
rep(i,1,m) e[i].from = read() + m,e[i].to = read() + m,e[i].v = read();
sort(e+1,e+1+m);
rep(i,1,m) e[i].id = i,G[e[i].from-m][e[i].to-m] = e[i].id,G[e[i].to-m][e[i].from-m] = e[i].id;
rep(i,1,q)
{
a[i].op = read(),a[i].x = read() + m,a[i].y = read() + m;
if(a[i].op == 2) vis[G[a[i].x - m][a[i].y - m]] = 1;
}
int tot = 0,cur = 0;
while(tot < n-1)
{
if(vis[e[++cur].id]) continue;
int L = e[cur].from,R = e[cur].to;
makeroot(L);
if(findroot(R) == L) continue;
link(L,e[cur].id),link(e[cur].id,R),tot++;
}
per(i,q,1)
{
if(a[i].op == 1) split(a[i].x,a[i].y),ans[++cnt] = e[t[a[i].y].pos].v;
else
{
int f = G[a[i].x-m][a[i].y-m];
split(a[i].x,a[i].y);
int g = t[a[i].y].pos;
if(e[f].v > e[g].v) continue;
else cut(e[g].from,g),cut(g,e[g].to),link(a[i].x,f),link(f,a[i].y);
}
}
per(i,cnt,1) printf("%d
",ans[i]);
return 0;
}