Deep_Kevin的娱乐空间

正题 最小生成树 Kruskal 每次找出联通两个不同联通块的最短的边，将两个联通块合并，可以通过反证法证明得到的生成树最小。 同时，如果要求次小生成树或者严格次小生成树，只会改变恰好一条边，改两条边或以上不会更优。 Prim 维护已经在最小生成树中的点集 SSS ，每次找出 SSS 向外连出的最短边，将该边的另一端点加入 SSS中。 Boruvka 对于每个联通块先求出一条到该点所在联通块外的最短边，最后一起合并即可。 这样每次会至少减少⌈n2⌉\lceil \frac n 2\rceil⌈2n​⌉个点，

正题 看到这样的性质就可以想到圆方树,而两点之间贡献的答案就是路径上的圆点数量,为了去重,我们只需要将虚树建出来求路径上的点权和就行了,实际上并不需要建出来,可以发现按照dfs序排一下之后就可以考虑欧拉回路,只需要将每个点的深度加起来-相邻两点的lca深度即可,这里的深度是带权深度,相当于点到根的圆点数量,最后这个虚树的权值也并不是正确的,因为在所有点的lca的父亲到根节点的圆点实际上并不会贡献答案,减一下就可以了. #include<bits/stdc++.h> using ...

正题 首先要先知道一个常识,对于一个点双联通分量,对于其中互不相同的三个点(a,b,c),总是存在一条a->b->c的简单路径(不经过重复的点与边),这个可以用网络流最小割证明: 考虑常见的二分图拆点建图模型,左边为出点,右边为入点,要找一条a->b->c的路径,就是要找一条b->a,b->c的简单路径,我们由每个入点向出点连一条容量为1的边,表示这个点只能经过一次,b点除外,对于边(x,y)我们从x的出点向y的入点连一条边,y的出点也向x的入...