题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2594
时间倒序一下，就是 魔法森林 那道题；
有个不解的地方，是 access 里面关于 pushup 的地方，两种写法都可以，但不明白没有注释掉的写法为什么也可以。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int const maxn=,maxm=1e6+;
int n,m,Q,val[maxn],mx[maxn],fa[maxn],pre[maxn],c[maxn][],sta[maxn],rev[maxn];
struct N{int hd,to,w,id; bool b;}edge[maxm];
struct T{int u,v,ans,f,id;}q[];
bool cmp(N x,N y){return x.w<y.w;}
bool cmp2(N x,N y){return x.hd<y.hd || (x.hd==y.hd && x.to<y.to);}
bool cmpp(N x,N y){return x.id<y.id;}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int rd()
{
int ret=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return ret*f;
}
int get(int x,int y)
{
int l=,r=m;
while(l<=r)
{
int mid=((l+r)>>);
if(edge[mid].hd==x && edge[mid].to==y)return mid;
if(edge[mid].hd<x || (edge[mid].hd==x && edge[mid].to<y))l=mid+;
else r=mid-;
}
}
bool isroot(int x)
{
return c[pre[x]][]!=x && c[pre[x]][]!=x;
}
void pushup(int x)
{
int ls=c[x][],rs=c[x][];
mx[x]=x;
if(val[mx[ls]]>val[mx[x]])mx[x]=mx[ls];
if(val[mx[rs]]>val[mx[x]])mx[x]=mx[rs];
}
void reverse(int x)
{
int ls=c[x][],rs=c[x][];
if(rev[x])
{
rev[ls]^=; rev[rs]^=; rev[x]=;
swap(c[x][],c[x][]);
}
}
void rotate(int x)
{
int y=pre[x],z=pre[y],d=(c[y][]==x);
if(!isroot(y))c[z][c[z][]==y]=x;
pre[x]=z; pre[y]=x; pre[c[x][!d]]=y;
c[y][d]=c[x][!d]; c[x][!d]=y;
pushup(y); pushup(x);
}
void splay(int x)
{
int top=; sta[++top]=x;
for(int i=x;!isroot(i);i=pre[i])sta[++top]=pre[i];
for(int i=top;i;i--)reverse(sta[i]);
for(;!isroot(x);rotate(x))
{
int y=pre[x],z=pre[y];
if(isroot(y))continue;
((c[y][]==x)^(c[z][]==y))?rotate(x):rotate(y);
}
pushup(x);//和下面配套
}
void access(int x)
{
for(int t=;x;c[x][]=t,t=x,x=pre[x])splay(x);//这样为什么也可以？
}
//void access(int x)
//{
// int t=0;
// while(x)
// {
// splay(x);c[x][1]=t;pushup(x);t=x;x=pre[x];
// }
//}
void makeroot(int x)
{
access(x); splay(x); rev[x]^=;
}
void link(int x,int y)
{
makeroot(x); pre[x]=y;//
}
void cut(int x,int y)
{
makeroot(x); access(y); splay(y);
pre[x]=; c[y][]=;
}
int query(int x,int y)
{
makeroot(x); access(y); splay(y); return mx[y];
}
int main()
{
n=rd(); m=rd(); Q=rd();
for(int i=;i<=n;i++)fa[i]=i;
for(int i=;i<=m;i++)
{
edge[i].hd=rd(); edge[i].to=rd(); edge[i].w=rd();
if(edge[i].hd>edge[i].to)swap(edge[i].hd,edge[i].to);
}
sort(edge+,edge+m+,cmp);//w
for(int i=;i<=m;i++)
{
edge[i].id=i;
val[i+n]=edge[i].w; mx[i+n]=i+n;//
}
sort(edge+,edge+m+,cmp2);//u,v
for(int i=;i<=Q;i++)
{
q[i].f=rd(); q[i].u=rd(); q[i].v=rd();
if(q[i].f==)
{
if(q[i].u>q[i].v)swap(q[i].u,q[i].v);
int t=get(q[i].u,q[i].v);
// edge[t].b=1; q[i].id=edge[i].id;
edge[t].b=; q[i].id=edge[t].id;
}
}
sort(edge+,edge+m+,cmpp);//w
for(int i=,tot=;i<=m;i++)
{
if(edge[i].b)continue;//kruskal 连不删的边
int u=edge[i].hd,v=edge[i].to;
if(find(u)!=find(v))
{
fa[find(u)]=find(v);
link(u,i+n); link(v,i+n);
tot++;
if(tot==n-)break;
}
}
for(int i=Q;i;i--)
{
int u=q[i].u,v=q[i].v;
if(q[i].f==)q[i].ans=val[query(u,v)];
else
{
int k=q[i].id,t=query(u,v);
if(edge[k].w<val[t])
{
cut(t,edge[t-n].hd); cut(t,edge[t-n].to);
link(u,k+n); link(v,k+n);
}
}
}
for(int i=;i<=Q;i++)
if(q[i].f==)printf("%d\n",q[i].ans);
return ;
}