<span>LCT 题解乱写</span>
LCT
水管局长
问题是要求支持删边,询问给定两点之间路径的边权最大值的最小值。
可以通过动态最小生成树解决。
因为不强制在线,考虑将删边转化为加边。
于是只要维护链上的最大权值,每次尝试割最大边权边并加入当前边就好了。
GERALD07
对于树形结构,联通块数=点数-边数。
通过主席树维护区间内的边数。
具体做法是,维护一条链上出现最早的边,在加入最后一条边时尝试替换这条最不优的边就好了。
魔法森林
将所有的边按a排序。
对于固定的a,问题转化为动态最小生成树问题。