水题,发现就是维护一个最小生成树
由于卡时间 ,就不直接用LCT连断边
先做一次Kruscal
化边为点就可以了
不要用map,似乎要被卡空间,每次二分判断
#include<bits/stdc++.h>
using namespace std;
const int RLEN=1<<22|1;
inline char gc(){
static char ibuf[RLEN],*ib,*ob;
(ob==ib)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
return (ob==ib)?EOF:*ib++;
}
inline int read(){
char ch=gc();
int res=0,f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
return f?res:-res;
}
const int N=1500005;
struct E{
int u,v,w,pos;bool des;
}e[N];
inline bool comp(const E&a,const E&b){
return a.w<b.w;
}
inline bool cmp(const E&a,const E&b){
return a.u==b.u?a.v<b.v:a.u<b.u;
}
inline bool cp(const E&a,const E&b){
return a.pos<b.pos;
}
struct oper{
int op,u,v,pos,ans;
}p[N];
int val[N],f[N],n,m,q,cnt,tot;
namespace LCT{
int mx[N],son[N][2],fa[N],que[N];bool rev[N];
#define lc(u) son[u][0]
#define rc(u) son[u][1]
inline bool isrt(int u){
if(!fa[u])return 1;
return lc(fa[u])!=u&&rc(fa[u])!=u;
}
inline bool isrc(int u){
return rc(fa[u])==u;
}
inline void pushup(int u){
mx[u]=u;
if(val[mx[u]]<val[mx[lc(u)]])mx[u]=mx[lc(u)];
if(val[mx[u]]<val[mx[rc(u)]])mx[u]=mx[rc(u)];
}
inline void pushdown(int u){
if(!rev[u])return;
if(lc(u))rev[lc(u)]^=1;
if(rc(u))rev[rc(u)]^=1;
swap(lc(u),rc(u)),rev[u]=0;
}
inline void rotate(int v){
int u=fa[v],z=fa[u];
int t=(rc(u)==v);
if(!isrt(u))son[z][rc(z)==u]=v;
fa[v]=z;
son[u][t]=son[v][t^1],fa[son[v][t^1]]=u;
son[v][t^1]=u,fa[u]=v;
pushup(u),pushup(v);
}
inline void splay(int u){
que[que[0]=1]=u;
for(int v=u;!isrt(v);v=fa[v])que[++que[0]]=fa[v];
for(int i=que[0];i;i--)pushdown(que[i]);
while(!isrt(u)){
if(!isrt(fa[u]))
isrc(fa[u])==isrc(u)?rotate(fa[u]):rotate(u);
rotate(u);
}
pushup(u);
}
inline void access(int u){
for(int v=0;u;v=u,u=fa[u]){
splay(u),rc(u)=v;if(v)fa[v]=u;pushup(u);
}
}
inline void makert(int u){
access(u),splay(u),rev[u]^=1;
}
inline void link(int u,int v){
makert(u),fa[u]=v;
}
inline void cut(int u,int v){
makert(u),access(v),splay(v),lc(v)=fa[u]=0;
}
inline int query(int u,int v){
makert(u),access(v),splay(v);return mx[v];
}
}
using namespace LCT;
char u;
int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
inline int find(int u,int v){
int l=1,r=m;
while(l<=r){
int mid=(l+r)>>1;
if(e[mid].u<u||(e[mid].u==u&&e[mid].v<v))l=mid+1;
else if(e[mid].u==u&&e[mid].v==v)return mid;
else r=mid-1;
}
}a
int main(){
n=read(),m=read(),q=read();
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++){
e[i].u=read(),e[i].v=read(),e[i].w=read();
if(e[i].u>e[i].v)swap(e[i].u,e[i].v);
}
sort(e+1,e+m+1,comp);
for(int i=1;i<=m;i++){
e[i].pos=i;
val[n+i]=e[i].w;
mx[n+i]=n+i;
}
sort(e+1,e+m+1,cmp);
for(int i=1;i<=q;i++){
p[i].op=read(),p[i].u=read(),p[i].v=read();
if(p[i].op==2){
if(p[i].u>p[i].v)swap(p[i].u,p[i].v);
int t=find(p[i].u,p[i].v);
e[t].des=1,p[i].pos=e[t].pos;
}
}
sort(e+1,e+m+1,cp);
for(int i=1;i<=m;i++){
if(e[i].des)continue;
int f1=find(e[i].u),f2=find(e[i].v);
if(f1!=f2){
f[f1]=f2;
link(e[i].u,i+n),link(e[i].v,i+n);
}
}
for(int i=q;i;i--){
if(p[i].op==1)p[i].ans=val[query(p[i].u,p[i].v)];
else{
int u=p[i].u,v=p[i].v,k=p[i].pos;
int t=query(u,v);
if(e[k].w<val[t]){
cut(e[t-n].u,t),cut(e[t-n].v,t);
link(u,k+n),link(v,k+n);
}
}
}
for(int i=1;i<=q;i++)if(p[i].op==1)cout<<p[i].ans<<'\n';
}