#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<map>
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
inline ll read() {
char ch = getchar(); ll x = 0; int op = 1;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') op = -1;
for(; isdigit(ch); ch = getchar()) x = x*10+ch-'0';
return x*op;
}
inline void write(ll a) {
if(a < 0) putchar('-'), a = -a;
if(a >= 10) write(a/10); putchar('0'+a%10);
}
const int N = 100010, M = 1000010;
int n, m, que;
int ans[N];
bool vis[M];
map<pii, int> id;
struct edge { int x, y, z; } e[M];
struct questions { int opt, x, y, flag; } q[N];
const bool cmp(const edge &a, const edge &b) { return a.z < b.z; }
const int S = N+M;
int rev[S], fa[S], c[S][2], mx[S], val[S];
inline bool isroot(int x) { return c[fa[x]][0] != x && c[fa[x]][1] != x; }
inline void pushup(int x) {
mx[x] = val[x];
if(e[mx[c[x][0]]].z > e[mx[x]].z) mx[x] = mx[c[x][0]];
if(e[mx[c[x][1]]].z > e[mx[x]].z) mx[x] = mx[c[x][1]];
}
inline void rot(int x) {
if(isroot(x)) return;
int y = fa[x], z = fa[y], f = c[y][1] == x;
c[y][f] = c[x][f^1]; if(c[x][f^1]) fa[c[x][f^1]] = y;
fa[x] = z; if(!isroot(y)) c[z][c[z][1] == y] = x;
fa[y] = x; c[x][f^1] = y;
pushup(y); pushup(x);
}
inline void pushdown(int x) {
if(!rev[x]) return;
rev[c[x][0]] ^= 1; rev[c[x][1]] ^= 1; swap(c[x][0], c[x][1]);
rev[x] = 0;
}
int st[N], top;
inline void pushtag(int x) {
top = 0;
while(x) { st[++ top] = x; x = fa[x]; }
while(top) pushdown(st[top --]);
}
inline void splay(int x) {
pushtag(x);
while(!isroot(x)) {
int y = fa[x], z = fa[y];
if(!isroot(y)) rot(((c[z][0] == y) == (c[y][0] == x))?y:x);
rot(x);
}
}
inline void access(int x) {
int t = 0;
while(x) {
splay(x); c[x][1] = t; pushup(x);
t = x; x = fa[x];
}
}
inline void rever(int x) { access(x); splay(x); rev[x] ^= 1; }
inline void link(int x, int y) { rever(x); fa[x] = y; }
inline void split(int x, int y) { rever(x); access(y); splay(y); }
inline void cut(int x, int y) { split(x, y); fa[x] = c[y][0] = 0; }
inline int find(int x) {
access(x); splay(x); pushdown(x);
while(c[x][0]) { x = c[x][0]; pushdown(x); }
return x;
}
inline void init(int x, int y) {
fa[x] = c[x][0] = c[x][1] = rev[x] = 0;
mx[x] = val[x] = y;
}
int main() {
/*freopen("tube.in", "r", stdin);
freopen("tube.out", "w", stdout);*/
n = read(), m = read(), que = read();
for(int i = 1; i <= m; i ++) {
e[i].x = read(); e[i].y = read(); e[i].z = read();
if(e[i].x > e[i].y) swap(e[i].x, e[i].y);
}
sort(e+1, e+1+m, cmp);
for(int i = 1; i <= m; i ++) id[mp(e[i].x, e[i].y)] = i;
for(int i = 1; i <= que; i ++) {
q[i].opt = read(); q[i].x = read(); q[i].y = read();
if(q[i].x > q[i].y) swap(q[i].x, q[i].y);
if(q[i].opt == 2) {
int d = id[mp(q[i].x, q[i].y)];
q[i].flag = d;//flag表示q[i]这条边在e中的编号
vis[d] = 1;
}
}
int all = n+m, sum = 0; e[0].z = 0;
for(int i = 1; i <= all; i ++) init(i, i<=n?0:(i-n));
for(int i = 1, x, y; i <= m; i ++) if(!vis[i]) {
if(sum == n-1) break;
x = e[i].x; y = e[i].y;
if(find(x) == find(y)) continue;
link(x, i+n); link(y, i+n);
sum ++;
}
for(int i = que, x, y; i >= 1; i --) {
x = q[i].x; y = q[i].y;
if(q[i].opt == 1) {
split(x, y); ans[i] = e[mx[y]].z;
} else {
split(x, y);
int d = q[i].flag, t = mx[y];
if(e[d].z < e[mx[y]].z) {
cut(e[t].x, t+n); cut(e[t].y, t+n);
link(x, d+n); link(y, d+n);
}
}
}
for(int i = 1; i <= que; i ++) if(q[i].opt == 1) write(ans[i]), puts("");
return 0;
}
by 麟落 @ 2018-11-22 19:50:45
~~我调了一个上午 早上九点开始做了一个小时然后吃了个中饭回来又调了一个小时才A 心力憔悴~~
by Owen_codeisking @ 2018-12-02 13:52:26