P8867

缩点 首先考虑对于一个边双内的边是可以任意看守或者不看守的，所以可以缩点，这样缩完点的图就成了一棵树。 对于缩完点后的每一个边双，我们设 \(E_{i}\) 表示边双 \(i\) 内的边的个数，\(siz_{i}\) 表示边双内点的个数。 那么只考虑一个边双的情况的话，边能任选的方案数就是 \(2^ ......

面对他。 题面： 求选择关键点和不会被割的边，使得任意割去一条边关键点不会有不连通的方案。 考虑缩边双，然后这样边双内随便选。 你考虑画出一颗树，考虑分类情况，容易发现就是三种： 1.没有选。 2.全部连通上 \(x\)。(即一个尚未孤立的连通块)。 3.有不联通到 \(x\) 的点。(即孤立的一个 ......

这道题想了很久，终于想出来了，非常抽象。 经过一番无脑推导，我们发现u里面有没有军营，是否与根连通，u的子树有没有军营，……都对方案数有影响，然后我就一直修修改改，事实证明，当发现越来越多题目条件中被忽略的细节时，一定不要嫌麻烦，要从头开始设置状态。 首先我们发现，子树中有没有军营对于与子树相连的边 ......