<span>LCT 题解乱写</span>

LCT

水管局长

问题是要求支持删边,询问给定两点之间路径的边权最大值的最小值。

可以通过动态最小生成树解决。

因为不强制在线,考虑将删边转化为加边。

于是只要维护链上的最大权值,每次尝试割最大边权边并加入当前边就好了。

 

GERALD07

对于树形结构,联通块数=点数-边数。

通过主席树维护区间内的边数。

具体做法是,维护一条链上出现最早的边,在加入最后一条边时尝试替换这条最不优的边就好了。

 

魔法森林

将所有的边按a排序。

对于固定的a,问题转化为动态最小生成树问题。

全部评论

相关推荐

joe2333:怀念以前大家拿华为当保底的日子
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务