<span>关于lct维护动态生成树问题</span>
水管局长数据加强版
题意是要求维护一棵最小生成树，支持删边操作。
删边操作比较难处理，因为如果删掉树上的边，
很难从已经有备选集合中找出连接不同联通块的最小的边。
然而题目并没有要求在线。 所以离线。
问题由删边转化为加边。
考虑加的每一条边：
如果两个点没有联通，直接联通。
如果两个点已经联通，那么两个点之间存在一条唯一路径。
加上当前边，会形成一个简单环。
找出这个简单环上的最大边权，删掉那一条边就可以了。
实际操作中并没有涉及到简单环，其实是查询两点之间的最大边权，并尝试用当前边替换最大边。
GERALD07加强版
一些求联通块问题，比较优秀的解法是：
形成生成树组成的森林，利用每棵树点数-边数=1的性质，答案为总点数-总边数。
本题的做法类似数颜色问题的主席树解法：
从编号为1的边开始尝试插入lct，
如果已经形成简单环，那么替换掉简单环上编号最靠前的边，
并将该边的前趋设为替换的边，将前趋表示在主席树上。
每次询问，其实就是问：
n-区间中有多少用到的边，
后者查询主席树区间[l,r]内，权值小于l的就可以了。
查看9道真题和解析
字节跳动公司氛围 527人发布