【题解】

  我们把操作倒过来做,就变成了加边而不是删边。于是用LCT维护动态加边的最小生成树就好了。同样要注意把边权变为点权。

  

 #include<cstdio>
#include<algorithm>
#define N 200010
#define rg register
#define ls (c[u][0])
#define rs (c[u][1])
using namespace std;
int n,m,q,top,tot;
int f[N],fa[N],c[N][],rev[N],mx[N],pos[N],val[N],st[N],ans[N],num[][];
bool bro[][];
struct edge{
int u,v,dis;
}e[N];
struct question{
int opt,x,y;
}que[N];
inline int read(){
int k=,f=; char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(''<=c&&c<='')k=k*+c-'',c=getchar();
return k*f;
}
inline int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
inline bool cmp(edge a,edge b){return a.dis<b.dis;}
inline int max(int x,int y){return x>y?x:y;}
inline bool isroot(int u){return c[fa[u]][]!=u&&c[fa[u]][]!=u;}
inline bool which(int u){return c[fa[u]][]==u;}
inline void pushup(int u){
pos[u]=u; mx[u]=val[u];
if(mx[ls]>mx[u]) pos[u]=pos[ls],mx[u]=mx[ls];
if(mx[rs]>mx[u]) pos[u]=pos[rs],mx[u]=mx[rs];
}
inline void pushdown(int u){
rev[u]=; rev[ls]^=; rev[rs]^=; swap(ls,rs);
}
inline void rotate(int u){
int f=fa[u],g=fa[f],wh=which(u);
if(!isroot(f)) c[g][which(f)]=u;
fa[u]=g; fa[f]=u; fa[c[u][wh^]]=f;
c[f][wh]=c[u][wh^]; c[u][wh^]=f;
pushup(f); pushup(u);
}
inline void splay(int u){
st[top=]=u;
for(rg int i=u;!isroot(i);i=fa[i]) st[++top]=fa[i];
for(rg int i=top;i;i--) if(rev[st[i]]) pushdown(st[i]);
while(!isroot(u)){
if(!isroot(fa[u])) rotate(which(u)==which(fa[u])?fa[u]:u);
rotate(u);
}
}
inline void access(int u){
for(rg int s=;u;s=u,u=fa[u]) splay(u),c[u][]=s,pushup(u);
}
inline void makeroot(int u){access(u); splay(u); rev[u]^=;}
inline int findroot(int u){
access(u); splay(u);
while(ls) u=ls; return u;
}
inline void split(int x,int y){makeroot(x); access(y); splay(y);}
inline void link(int x,int y){makeroot(x); fa[x]=y;}
inline void cut(int x,int y){
split(x,y); int t=c[y][];
if(t==x&&!c[t][]) fa[x]=,c[y][]=;
else{
while(c[t][]) t=c[t][];
if(t==x) fa[x]=,c[y][]=;
}
}
inline void build(){
sort(e+,e++m,cmp);
for(rg int i=;i<=n;i++) f[i]=i;
for(rg int i=;i<=m;i++){
val[i+n]=e[i].dis;
num[e[i].u][e[i].v]=num[e[i].v][e[i].u]=i;
}
int cnt=;
for(rg int i=;i<=m;i++){
int u=e[i].u,v=e[i].v;
if(bro[u][v]) continue;
if(find(u)!=find(v)){
cnt++; link(u,i+n); link(v,i+n);
f[find(u)]=find(v);
}
if(cnt>=n-) break;
}
}
inline void work(){
for(rg int i=q;i;i--){
int opt=que[i].opt,x=que[i].x,y=que[i].y;
if(opt==){
split(x,y); ans[++tot]=mx[y];
}
else{
int ne=num[x][y];
split(x,y);
if(e[ne].dis<mx[y]){
int oe=pos[y]-n;
cut(e[oe].u,oe+n); cut(e[oe].v,oe+n);
link(e[ne].u,ne+n); link(e[ne].v,ne+n);
}
}
}
for(rg int i=tot;i;i--) printf("%d\n",ans[i]);
}
int main(){
n=read(),m=read(),q=read();
for(rg int i=;i<=m;i++) {
e[i].u=read(),e[i].v=read(),e[i].dis=read();
}
for(rg int i=;i<=q;i++){
que[i].opt=read(); que[i].x=read(); que[i].y=read();
if(que[i].opt==)
bro[que[i].x][que[i].y]=bro[que[i].y][que[i].x]=;
}
build();
work();
return ;
}

最新文章

  1. CSS布局基础之二认识Viewport
  2. 查找表或其他对象在某个Server上的存在
  3. bzoj3036: 绿豆蛙的归宿
  4. JavaWeb之 JSP:自定义标签
  5. HAOI2007 理想的正方形
  6. WCF简单教程
  7. 20151214--JSTL
  8. 维吉尼亚密码java代码实现根据密钥长度计算IC值过程
  9. 安装 sublime package control
  10. 在自学java路上遇上的南墙
  11. Arcgis for js开发之直线、圆、箭头、多边形、集结地等绘制方法
  12. Java面向对象 第4节 类的多态性
  13. 解决linux下node.js全局模块找不到的情况
  14. Chapter3:Qt5布局管理
  15. HDU 6205 (模拟) card card card
  16. 【Java】java.lang.NullPointerException的两个原因
  17. Entity Framework 复杂类型(转)
  18. vue 基础笔记
  19. 第三章 广义线性模型(GLM)
  20. iOS中 三种随机数方法详解

热门文章

  1. POJ1584 A Round Peg in a Ground Hole 凸包判断 圆和凸包的关系
  2. python调用java程序--jpype
  3. js滚轮事件需要注意的兼容性问题
  4. v-contextmenu的使用(右键菜单)
  5. bzoj 1047: [HAOI2007]理想的正方形【单调队列】
  6. bzoj 1705: [Usaco2007 Nov]Telephone Wire 架设电话线【dp】
  7. springboot(三)配置日志
  8. ASP.NET 之页面重定向和传值
  9. Hbase源码分析:server端RPC
  10. 【IIS7.5】Asp文件上传限制,加载页面大小限制