刚开始做的时候还以为是暴搜，YY了各种剪枝，结果华丽丽的TLE了 正解： 状态压缩DP dp[当前走到的点][状态] 状态： 第i位表示第i个点有没有被消灭 转移： 详见代码 注意： 计算转移cost时要用O(1) 的算法 二分…

有点巧妙啊！ s[x]每次维护的是最小值 我们将边按从大到小排个序,这样编号小的就在前面啦！QAQ 再按最小生成树的LCT的做法来 不过我们每次要用一个book标记前面最小边的编号 每次要更新答案时，一直往前跳，跳到最晚更新的即使最小的…

题目链接 先将边排序，这样就可以按从小到大的顺序维护生成树，枚举到一条未连通的边就连上，已连通则(用当前更大的)替换掉路径上最小的边，这样一定不会更差。 每次构成树时更新答案。答案就是当前边减去生成树上最小边的权值。 LCT…

这也是一道LCT维护生成树的题。 那么我们还是按照套路，先对边进行排序，然后顺次加入。 不过和别的题有所不同的是： 在本题中，我们需要保证LCT中正好有\(n-1\)条边的时候，才能更新\(ans\) 其次，更新答案的时…

洛谷P4234 最小差值生成树 题解 题目链接：P4234 最小差值生成树 题意：给定一个点标号从 1 1 1 到 n n n 的、有 m m m 条边的无向图，求边权最大值与最小值的差值最小的生成树，图可能存在自环 这个题不太好利用kruskal来维护&a…

题目 先把所有边按x从小到大排序。动态添边。x y 已经有一条路径 就把x y路径中最小的边去掉，换成这个边。 每次(numn-1)时 更新答案 ansmin(ans,e[i].w-e[dex].w); dex是当前生成树中最小的边。注意是生成树上，不是路径上，lct搞不来的。 wh…

https://www.luogu.org/problemnew/show/P4234 按照边的权值从小到大排序，依次加入，并删除能够删除的权值最小的一条边，用 set 维护当前所有边的边权，并查集维护联通性，LCT 维护两点间最小值和 link cut 操作即可 #inc…

背景： 春节假期算是结束了… 题目传送门： https://www.luogu.org/problemnew/show/P4234 题意： 求一棵最小差值生成树（最大边权减最小边权最小）。 思路： 离线好打些。 先排序，从小…