- 考虑维护一颗最小生成树,那么询问两个点的答案就是树上两点路径上的边权最大值.
- 边权不便于维护,可以将 (i) 号边对应 (i+n) 号额外点,这个点连接原来的边连接的两点,点权为原边权,其他点权为 (0) .这样就把维护路径上边权最大值转换成了维护路径上点权最大值.
- 在最小生成树上,删边必然会导致加入另一条边来维持树的形态,而加入哪一条边却不便于找出.
- 由于可以离线,使用常见套路,将操作全部读进来,反着做,这样每次处理到删边操作时,将这条边加入最小生成树中,再断掉环上最大的那条边(即断掉对应的额外点),即可完成操作.
- 综上,用 (Kruskal) 找出最小生成树后,我们只需要维护路径点权最大值,资瓷删边加边,即可完成所有操作.
- 用一颗 (LCT) 来维护即可.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
inline int read()
{
int x=0;
bool pos=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar())
if(ch=='-')
pos=0;
for(;isdigit(ch);ch=getchar())
x=x*10+ch-'0';
return pos?x:-x;
}
const int MAXN=1e6+10;
int n,m,Q,ans[MAXN];
struct edge{
int u,v,val;
int id;//边的编号
int d;//d=1说明被删除
}e[MAXN];
int cmp1(const edge &a,const edge &b)
{
return a.val<b.val;
}
int cmp2(const edge &a,const edge &b)
{
return a.u==b.u?a.v<b.v:a.u<b.u;
}
int cmp3(const edge &a,const edge &b)
{
return a.id<b.id;
}
struct query{
int type,u,v;
int id;//操作2删除边的编号
}q[MAXN];
struct LCT{
int stk[MAXN],tp;
struct node{
int mx;
int ch[2];
int fa;
int rev;
int val;
node()
{
ch[0]=ch[1]=0;
fa=0;
val=0;
}
}tree[MAXN];
#define root tree[x]
#define lson tree[root.ch[0]]
#define rson tree[root.ch[1]]
void pushup(int x)
{
root.mx=root.val;
if(e[lson.mx].val>e[root.mx].val)
root.mx=lson.mx;
if(e[rson.mx].val>e[root.mx].val)
root.mx=rson.mx;
}
void inverse(int x)
{
swap(root.ch[0],root.ch[1]);
root.rev^=1;
}
inline bool isroot(int x)
{
int y=root.fa;
return tree[y].ch[0]!=x && tree[y].ch[1]!=x;
}
void rotate(int x)
{
int y=tree[x].fa,z=tree[y].fa;
int k=tree[y].ch[1]==x;
if(!isroot(y))
tree[z].ch[tree[z].ch[1]==y]=x;
tree[x].fa=z;
tree[y].ch[k]=tree[x].ch[k^1];
tree[tree[x].ch[k^1]].fa=y;
tree[x].ch[k^1]=y;
tree[y].fa=x;
pushup(y);
}
void pushdown(int x)
{
if(root.rev)
{
if(root.ch[0])
inverse(root.ch[0]);
if(root.ch[1])
inverse(root.ch[1]);
root.rev=0;
}
}
void splay(int x)
{
tp=0;
stk[++tp]=x;
for(int pos=x;!isroot(pos);pos=tree[pos].fa)
stk[++tp]=tree[pos].fa;
while(tp)
pushdown(stk[tp--]);
while(!isroot(x))
{
int y=tree[x].fa,z=tree[y].fa;
if(!isroot(y))
(tree[y].ch[0]==x) ^ (tree[z].ch[0]==y) ? rotate(x) : rotate(y) ;
rotate(x);
}
pushup(x);
}
void Access(int x)
{
for(int y=0;x;y=x,x=tree[x].fa)
{
splay(x);
tree[x].ch[1]=y;
pushup(x);
}
}
void makeroot(int x)
{
Access(x);
splay(x);
inverse(x);
}
int findroot(int x)
{
Access(x);
splay(x);
while(tree[x].ch[0])
x=tree[x].ch[0];
return x;
}
void split(int x,int y)
{
makeroot(x);
Access(y);
splay(y);
}
void Link(int x,int y)
{
makeroot(x);
tree[x].fa=y;
}
void cut(int x,int y)
{
split(x,y);
tree[x].fa=tree[y].ch[0]=0;
}
}T;
int Findedge(int x,int y)//找到x->y这条边的编号
{
int l=1,r=m;
while(l<=r)
{
int mid=(l+r)>>1;
if(e[mid].u<x || (e[mid].u==x && e[mid].v<y))
l=mid+1;
else if(e[mid].u==x && e[mid].v==y)
return mid;
else
r=mid-1;
}
return 0;
}
int Fa[MAXN];
int Findfa(int x)
{
return x==Fa[x]?x:(Fa[x]=Findfa(Fa[x]));
}
bool Union(int x,int y)
{
int u=Findfa(x),v=Findfa(y);
if(u==v)
return false;
Fa[u]=v;
return true;
}
void Kruskal()
{
for(int i=1;i<=n;++i)
Fa[i]=i;
sort(e+1,e+1+m,cmp3);
int tot=0;
for(int i=1;i<=m;++i)
{
if(e[i].d)
continue;
int x=e[i].u,y=e[i].v;
if(Union(x,y))
{
T.Link(x,i+n);
T.Link(y,i+n);
++tot;
}
if(tot==n-1)
return;
}
}
int main()
{
n=read(),m=read(),Q=read();
for(int i=1;i<=m;++i)
{
e[i].u=read();
e[i].v=read();
e[i].val=read();
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<=m;++i)
{
e[i].id=i;
T.tree[i+n].val=i;
}
sort(e+1,e+1+m,cmp2);
for(int i=1;i<=Q;++i)
{
q[i].type=read();
q[i].u=read();
q[i].v=read();
if(q[i].u>q[i].v)
swap(q[i].u,q[i].v);
if(q[i].type==2)
{
int t=Findedge(q[i].u,q[i].v);
q[i].id=e[t].id;
e[t].d=1;
}
}
Kruskal();
for(int i=Q;i;--i)
{
if(q[i].type==1)
{
T.split(q[i].u,q[i].v);
ans[i]=e[T.tree[q[i].v].mx].val;
}
else
{
int x=q[i].u,y=q[i].v;
T.makeroot(x);
if(T.findroot(y)!=x)
{
T.Link(x,q[i].id+n);
T.Link(y,q[i].id+n);
continue;
}
if(e[T.tree[y].mx].val > e[q[i].id].val)
{
int t=T.tree[y].mx;
T.cut(t+n,e[t].u);
T.cut(t+n,e[t].v);
T.Link(q[i].id+n,x);
T.Link(q[i].id+n,y);
}
}
}
for(int i=1;i<=Q;++i)
if(q[i].type==1)
printf("%d
",ans[i]);
return 0;
}