题面

初见LCT,动态最小生成树+链上查询max,具体做法是把边转换成点(LCT只能维护点)

时光倒流,先把最后剩的连起来。然后查询就看链上最大值,修改看看链上最大值是否大于当前边,如果是就断开原来的改成当前边

 #include<map>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
struct a{int x,y,c;}mst[N];
struct b{int x,y,typ;}qry[N];
map<pair<int,int>,int> mmp;
int fth[N],son[N][],val[N];
int maxx[N],stk[N],outp[N];
bool brk[N],rev[N];
int n,m,T,p,t1,t2,cnt,top;
bool cmp(a xx,a yy)
{
return xx.c<yy.c;
}
void Pushup(int nde)
{
maxx[nde]=val[nde];
int &mx=maxx[nde],&mx1=maxx[son[nde][]],&mx2=maxx[son[nde][]];
if(mst[mx1].c>mst[mx].c) mx=mx1; if(mst[mx2].c>mst[mx].c) mx=mx2;
}
void Release(int nde)
{
if(rev[nde])
{
int &lson=son[nde][],&rson=son[nde][];
rev[lson]^=,rev[rson]^=,rev[nde]^=;
swap(lson,rson);
}
}
bool Nottop(int nde)
{
int fa=fth[nde];
return son[fa][]==nde||son[fa][]==nde;
}
void Rotate(int nde)
{
int fa=fth[nde],gr=fth[fa],isl=nde==son[fa][];
if(Nottop(fa)) son[gr][son[gr][]==fa]=nde;
fth[nde]=gr,fth[fa]=nde,fth[son[nde][isl]]=fa;
son[fa][isl^]=son[nde][isl],son[nde][isl]=fa;
Pushup(fa),Pushup(nde);
}
void Splay(int nde)
{
stk[top=]=nde;
for(int i=nde;Nottop(i);i=fth[i])
stk[++top]=fth[i];
while(top) Release(stk[top--]);
while(Nottop(nde))
{
int fa=fth[nde],gr=fth[fa];
if(Nottop(fa))
Rotate(((son[fa][]==nde)==(son[gr][]==fa))?fa:nde);
Rotate(nde);
}
}
void Access(int nde)
{
int lst=,mem=nde;
while(nde)
{
Splay(nde),son[nde][]=lst;
Pushup(nde),lst=nde,nde=fth[nde];
}
Splay(mem);
}
void Turnroot(int nde)
{
Access(nde),rev[nde]^=;
}
int Getroot(int nde)
{
Access(nde);
while(son[nde][])
nde=son[nde][];
return nde;
}
void Split(int x,int y)
{
Turnroot(x),Access(y);
}
int Query(int x,int y)
{
Split(x,y);
return maxx[y];
}
void Link(int x,int y)
{
Turnroot(x);
if(Getroot(y)!=x) fth[x]=y;
}
void Cut(int x,int y)
{
Turnroot(x);
if(Getroot(y)==x&&fth[x]==y&&!son[x][])
son[y][]=fth[x]=;
}
int main()
{
scanf("%d%d%d",&n,&m,&T);
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&t1,&t2,&mst[i].c);
if(t1>t2) swap(t1,t2); mst[i].x=t1,mst[i].y=t2;
}
sort(mst+,mst++m,cmp);
for(int i=;i<=m;i++)
mmp[make_pair(mst[i].x,mst[i].y)]=i;
for(int i=;i<=T;i++)
{
scanf("%d%d%d",&qry[i].typ,&t1,&t2);
if(t1>t2) swap(t1,t2); qry[i].x=t1,qry[i].y=t2;
if(qry[i].typ==) brk[mmp[make_pair(t1,t2)]]=true;
}
for(int i=;i<=m;i++)
val[i+n]=maxx[i+n]=i;
for(int i=;i<=m&&cnt<n-;i++)
if(!brk[i])
{
int tx=mst[i].x,ty=mst[i].y;
Turnroot(tx);
if(Getroot(ty)!=tx)
cnt++,Link(tx,i+n),Link(ty,i+n);
}
for(int i=T;i;i--)
if(qry[i].typ==)
outp[++p]=mst[Query(qry[i].x,qry[i].y)].c;
else
{
int tx=qry[i].x,ty=qry[i].y;
int id=mmp[make_pair(tx,ty)],me=Query(tx,ty);
if(mst[id].c<mst[me].c)
{
Cut(mst[me].x,me+n),Cut(mst[me].y,me+n);
Link(tx,id+n),Link(ty,id+n);
}
}
while(p)
printf("%d\n",outp[p--]);
return ;
}

最新文章

  1. [luogu2964][USACO09NOV][硬币的游戏A Coin Game] (博弈+动态规划)
  2. Spring系列之Spring常用注解总结
  3. java笔记--关于线程同步(7种同步方式)
  4. 再谈vertical-align与line-height
  5. ios蓝牙开发(四)app作为外设被连接的实现-转发
  6. jQuery MD5加密实现代码
  7. akka cluster sharding source code 学习 (2/5) handle off
  8. linux安全
  9. 关于delegate, category和subclass
  10. Oracle PL/SQL 事物处理 银行转账
  11. CI框架篇之辅助函数篇--基本(1)
  12. River Hopscotch(二分)
  13. 对数的操作 开始我的JAVA历程
  14. AMQP协议学习
  15. Java集合框架(一)—— Collection、Iterator和Foreach的用法
  16. 【IOS 开发】Object-C 运算符
  17. ve2.0 v-for循环报错的解决方案
  18. temp-重庆银行
  19. Python大法之告别脚本小子系列—信息资产收集类脚本编写(下)
  20. 实例详解Java中如何对方法进行调用

热门文章

  1. Spring入门学习笔记(2)——基于Java的配置
  2. Hyperledger Fabric服务器配置及修改Docker容器卷宗存储根目录/位置
  3. eclipse创建spring boot项目加载不到application.properties配置文件
  4. TensorFlow中的卷积函数
  5. oracle查看用户表
  6. 《找出1到正整数N中出现1的次数》
  7. servlet的方法解析
  8. “吃神么,买神么”的第二个Sprint计划
  9. 运行时错误 429,ACTIVEX部件不能创建对象的解决方法小结
  10. SCRUM:周日周一任务实现情况