<span>关于lct维护动态生成树问题</span>

水管局长数据加强版

题意是要求维护一棵最小生成树,支持删边操作。

删边操作比较难处理,因为如果删掉树上的边,

很难从已经有备选集合中找出连接不同联通块的最小的边。

然而题目并没有要求在线。 所以离线。

问题由删边转化为加边。

考虑加的每一条边:

如果两个点没有联通,直接联通。

如果两个点已经联通,那么两个点之间存在一条唯一路径。

加上当前边,会形成一个简单环。

找出这个简单环上的最大边权,删掉那一条边就可以了。

实际操作中并没有涉及到简单环,其实是查询两点之间的最大边权,并尝试用当前边替换最大边。

 

 

 

GERALD07加强版

一些求联通块问题,比较优秀的解法是:

形成生成树组成的森林,利用每棵树点数-边数=1的性质,答案为总点数-总边数。

本题的做法类似数颜色问题的主席树解法:

从编号为1的边开始尝试插入lct,

如果已经形成简单环,那么替换掉简单环上编号最靠前的边

并将该边的前趋设为替换的边,将前趋表示在主席树上。

每次询问,其实就是问:

n-区间中有多少用到的边,

后者查询主席树区间[l,r]内,权值小于l的就可以了。

全部评论

相关推荐

04-21 13:50
已编辑
北京理工大学 硬件测试
我们学校连夜发了声明,绝了绝了!看完了全部ppt,震碎三观。一般情况下我是站学生的,但这不是一般情况。这男的不能被取消学位吗?自己吃到了红利,靠着面试泄题得到的保研,又反手举报导师。这导师是《被举报系列》里最惨最恋爱脑的了,当然最可怜的是他的同妻……
牛客小黄鱼:看了ppt的聊天记录,真不知道谁才是受害者!有人为你剥过柚子吗?有人为你雪地里等你吗?有人为你写过情书吗?有人为你规划未来吗?有人为你小心翼翼吗?有人为你整页失眠失眠吗? 有人为你送上自己的科研成果吗?有人为你安排出国留学吗?有人愿意给你一个月2万吗?
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务