离线做,把删边转化为加边,那么如果加边的两个点不连通,直接连就行了.如果联通就找他们之间的瓶颈边,判断一下当前边是否更优,如果更优就cut掉瓶颈边,加上当前边.
那怎么维护瓶颈边呢?把边也看做点,向两个点分别连边,那么只用维护最大值就行了.维护的时候保存编号,比较的时候就比较编号对应的边权,这样方便询问时删边.
还有读入后注意储存 边(u,v)或者断边(u,v) 的时候,把较小值设为u,较大值设为v. 如果不这样的话在BZOJ上能A,但是在洛谷上会WA,因为BZOJ上的数据保证前面给出的边(u,v),在断边的时候给出的顺序仍然是(u,v).而洛谷上的官方数据可能给出的顺序是(v,u)
CODE(这个代码是加强版数据的范围)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
template<typename T>inline void read(T &num) {
char ch; int flg = 1;
while((ch=getchar())<'0'||ch>'9')if(ch=='-')flg=-flg;
for(num=0;ch>='0'&&ch<='9';num=num*10+ch-'0',ch=getchar());
num*=flg;
}
const int N = 100005;
const int MAXN = 200005;
const int MAXM = 1000005;
const int MAXQ = 100005;
int n, m, Q;
struct edge { int u, v, len, id; bool po; }E[MAXM];
struct Query { int op, x, y, id; }q[MAXQ];
namespace LCT {
#define ls ch[x][0]
#define rs ch[x][1]
int ch[MAXN][2], fa[MAXN], mx[MAXN], w[MAXN], ID[MAXN];
bool rev[MAXN];
inline bool isr(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; }
inline bool get(int x) { return x == ch[fa[x]][1]; }
inline void upd(int x) {
mx[x] = x;
if(ls && w[mx[ls]] > w[mx[x]]) mx[x] = mx[ls];
if(rs && w[mx[rs]] > w[mx[x]]) mx[x] = mx[rs];
}
inline void rot(int x) {
int y = fa[x], z = fa[y], l = get(x), r = l^1;
if(!isr(y)) ch[z][get(y)] = x;
fa[ch[x][r]] = y; fa[y] = x; fa[x] = z;
ch[y][l] = ch[x][r]; ch[x][r] = y;
upd(y), upd(x);
}
inline void mt(int x) { if(rev[x]) rev[x] ^= 1, rev[ls] ^= 1, rev[rs] ^= 1, swap(ls, rs); }
void mtpath(int x) { if(!isr(x)) mtpath(fa[x]); mt(x); }
inline void splay(int x) {
mtpath(x);
for(; !isr(x); rot(x))
if(!isr(fa[x])) rot(get(x)==get(fa[x])?fa[x]:x);
}
inline int access(int x) { int y=0;
for(; x; x=fa[y=x]) splay(x), ch[x][1]=y, upd(x);
return y;
}
inline void bert(int x) { access(x), splay(x), rev[x] ^= 1; }
inline int sert(int x) {
access(x), splay(x);
for(; ch[x][0]; x=ch[x][0]);
return x;
}
inline void link(int x, int y) {
bert(x);
if(sert(y) == x) return;
fa[x] = y;
}
inline void cut(int x, int y) {
bert(x), access(y), splay(y);
if(sert(y) != x || fa[x] != y || ch[x][1] != 0) return;
fa[x] = ch[y][0] = 0; upd(y);
}
inline int split(int x, int y) {
bert(x), access(y), splay(y);
return y;
}
inline int query(int x, int y) {
split(x, y);
if(sert(y) != x) return -1;
return mx[y];
}
}
using namespace LCT;
inline bool cmp1(const edge &i, const edge &j) { return i.len < j.len; }
inline bool cmp2(const edge &i, const edge &j) { return i.u == j.u ? i.v < j.v : i.u < j.u; }
inline bool cmp3(const edge &i, const edge &j) { return i.id < j.id; }
int f[N], tot;
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
inline void Kruskal() {
for(int i = 1; i <= n; ++i) f[i] = i;
sort(E + 1, E + m + 1, cmp3);
tot = 0;
for(int i = 1; i <= m; ++i)
if(!E[i].po) {
int x = find(E[i].u), y = find(E[i].v);
if(x != y) {
f[x] = y, ++tot;
mx[tot+n] = tot+n;
w[tot+n] = E[i].len;
ID[tot+n] = i;
link(E[i].u, n+tot);
link(E[i].v, n+tot);
if(tot == n-1) return;
}
}
}
inline int pos(int U, int V) { //二分找编号
int l = 1, r = m, mid;
while(l < r) {
mid = (l + r) >> 1;
if(E[mid].u < U || (E[mid].u == U && E[mid].v < V)) l = mid + 1;
else r = mid;
}
return l;
}
int ans[MAXQ];
int main () {
read(n), read(m), read(Q);
for(int i = 1; i <= m; ++i) {
read(E[i].u), read(E[i].v), read(E[i].len);
if(E[i].u > E[i].v) swap(E[i].u, E[i].v);
}
sort(E + 1, E + m + 1, cmp1);
for(int i = 1; i <= m; ++i) E[i].id = i;
sort(E + 1, E + m + 1, cmp2);
for(int i = 1; i <= Q; ++i) {
read(q[i].op), read(q[i].x), read(q[i].y);
if(q[i].x > q[i].y) swap(q[i].x, q[i].y);
if(q[i].op == 2) {
int k = pos(q[i].x, q[i].y);
q[i].id = E[k].id; E[k].po = 1;
}
}
Kruskal();
for(int i = Q; i >= 1; --i)
if(q[i].op == 1) ans[i] = w[query(q[i].x, q[i].y)];
else {
int t = query(q[i].x, q[i].y);
if(t == -1) { //不连通
++tot;
mx[n+tot] = n+tot; ID[n+tot] = q[i].id, w[n+tot] = E[q[i].id].len;
link(q[i].x, n+tot), link(q[i].y, n+tot);
}
else if(w[t] > E[q[i].id].len) {
cut(E[ID[t]].u, t), cut(E[ID[t]].v, t);
mx[t] = t; ID[t] = q[i].id; w[t] = E[q[i].id].len; //回收使用t这个编号,这样LCT的点数可以只开2*n
link(q[i].x, t), link(q[i].y, t);
}
}
for(int i = 1; i <= Q; ++i)
if(q[i].op == 1) printf("%d
", ans[i]);
}