http://www.lydsy.com/JudgeOnline/problem.php?id=2594 (题目链接)
题意
给出一个带边权的无向简单，要求维护两个操作，删除${u,v}$之间的连边；求${u,v}$之间某条路径使路径上的权值最大边最小。
Solution
我们把询问倒过来做，于是删边就变成了加边，然后就可以LCT啦。
mdzz卡了一上午常数，下面讲一讲我卡常数的心得→_→：
1.pushdown写成非递归的
2.初始连边时一定要写克鲁斯卡尔，而不是直接LCT维护删边加边
3.find函数用并查集写
4.不要用STL的stack。。。
5.inline加上
6.读入优化
7.因为保证任何时刻图连通，所以我们对询问进行操作时，加入的边的两个端点一定在同一连通块内，于是省去了2次find→_→
代码
// bzoj2594
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<ctime>
#define LL long long
#define inf (1ll<<30)
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;
inline int gi() {
int x=0,f=1;char ch=getchar();
while (ch<'0' || ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=100010,maxm=1100010;
int a[maxm],mx[maxm],fa[maxm],tr[maxm][2],rev[maxm],ans[maxn],vis[maxm];
int n,m,Q,f[maxm],st[maxm];
struct ask {int k,x,y,id;}q[maxn];
struct edge {int u,v,w,id;}e[maxm];
inline bool cmp1(edge a,edge b) {return a.u==b.u ? a.v<b.v : a.u<b.u;}
inline bool cmp2(edge a,edge b) {return a.w<b.w;}
inline bool cmp3(edge a,edge b) {return a.id<b.id;}
inline void pushup(int x) {
if (a[mx[tr[x][0]]]>a[mx[tr[x][1]]]) mx[x]=mx[tr[x][0]];
else mx[x]=mx[tr[x][1]];
if (a[x]>a[mx[x]]) mx[x]=x;
}
inline void pushdown(int x) {
st[0]=0;
while (tr[fa[x]][0]==x || tr[fa[x]][1]==x) st[++st[0]]=x,x=fa[x];
st[++st[0]]=x;
for (int i=st[0];i>=1;i--) {
x=st[i];
if (rev[x]) {
swap(tr[x][0],tr[x][1]);
rev[tr[x][0]]^=1;rev[tr[x][1]]^=1;rev[x]^=1;
}
}
}
inline void rotate(int x) {
int y=fa[x],z=fa[y],l,r;
l=tr[y][1]==x;r=l^1;
if (tr[z][0]==y || tr[z][1]==y) tr[z][tr[z][1]==y]=x;
fa[x]=z;fa[y]=x;fa[tr[x][r]]=y;
tr[y][l]=tr[x][r];tr[x][r]=y;
pushup(y);pushup(x);
}
inline void splay(int x) {
pushdown(x);
while (tr[fa[x]][0]==x || tr[fa[x]][1]==x) {
int y=fa[x],z=fa[y];
if (tr[z][0]==y || tr[z][1]==y) {
if (tr[z][0]==y ^ tr[y][0]==x) rotate(x);
else rotate(y);
}
rotate(x);
}
}
inline void access(int x) {
for (int y=0;x;y=x,x=fa[x])
splay(x),tr[x][1]=y,pushup(x);
}
inline void makeroot(int x) {
access(x);splay(x);rev[x]^=1;
}
inline void link(int x,int y) {
makeroot(x);fa[x]=y;
}
inline void cut(int x,int y) {
makeroot(x);access(y);splay(y);
tr[y][0]=fa[x]=0;pushup(y);
}
inline int query(int x,int y) {
makeroot(x);access(y);splay(y);
return mx[y];
}
inline int find(int x) {
return f[x]==x ? x : f[x]=find(f[x]);
}
inline int Lower_bound(int x,int y) {
int l=1,r=m,res;
while (l<=r) {
int mid=(l+r)>>1;
if (x<e[mid].u || (x==e[mid].u && y<=e[mid].v)) res=mid,r=mid-1;
else l=mid+1;
}
return e[res].id;
}
int main() {
n=gi(),m=gi(),Q=gi();
for (int i=1;i<=m;i++) {
e[i].u=gi(),e[i].v=gi(),e[i].w=gi(),e[i].id=i;
if (e[i].u>e[i].v) swap(e[i].u,e[i].v);
}
sort(e+1,e+1+m,cmp1);
for (int i=1;i<=Q;i++) {
q[i].k=gi(),q[i].x=gi(),q[i].y=gi();
if (q[i].x>q[i].y) swap(q[i].x,q[i].y);
if (q[i].k==2) q[i].id=Lower_bound(q[i].x,q[i].y),vis[q[i].id]=1;
}
sort(e+1,e+1+m,cmp2);
for (int i=1;i<=n+m;i++) a[i]=0,f[i]=i;
for (int i=1;i<=m;i++) if (!vis[e[i].id]) {
a[n+e[i].id]=e[i].w;
int r1=find(e[i].u),r2=find(e[i].v);
if (r1!=r2) {
link(e[i].u,n+e[i].id),link(e[i].v,n+e[i].id);
f[r1]=r2;
}
}
sort(e+1,e+1+m,cmp3);
for (int i=Q;i>=1;i--) {
if (q[i].k==1) ans[i]=a[query(q[i].x,q[i].y)];
else {
int t=q[i].id;
a[t+n]=e[t].w;
int xx=query(e[t].u,e[t].v);
if (a[xx]<=a[n+t]) continue;
cut(e[xx-n].u,xx),cut(e[xx-n].v,xx);
link(e[t].u,n+t),link(e[t].v,n+t);
}
}
for (int i=1;i<=Q;i++) if (q[i].k==1) printf("%d
",ans[i]);
return 0;
}