\(\text{Luogu2860}\)
题目简述
给定一张 \(n\) 个点 \(m\) 条边的无向图，问至少添加多少条边才可以将图补成一张边双图。
思路点拨
警钟长鸣：图可能不连通。
我们考虑如果一个子图就是边双那么就可以不管他，自然缩边双之后考虑树上问题。怎么补全呢？就是每一次挑选出树的直径然后将叶子连边，一直操作到不可以操作为止。时间复杂度 \(O(n^2)\) 。但是我们发现这个操作等价于叶子树除二向上取整，所以可以做到 \(O(n)\) 。
建造军营
题目简述
有一张 \(n\) 个点， \(m\) 条边的无向图，你需要从中选择一些关键点（至少一个）和关键边使得不存在一条非关键边边满足割掉之后使两个关键点不连通。求分配关键点和关键边的方案数。
思路点拨
注意到在同一个边双联通分量内点和边可以随便选，所以考虑缩边双联通分量之后进行树形 dp 。
在 dp 之前，我们统计出每一个边双的节点个数 \(a_i\) 和边个数 \(b_i\) 。下文，我们乘一个边双就是一个树上的节点。
如果一个节点被选择了军营，并且这个它的子树外还有军营，那么他向父亲一定是需要连边的。如果一个节点被选择军营，但是他的子树外没有军营了，那么子树外的边是可以任意选的。按照常规的手段，我们定义状态 \(f_{i,0/1,0/1}\) 表示考虑到节点 \(i\) ，子树内是否存在军营被选择，子树外是否存在军营被选择的方案数对 \(1e9+7\) 取余数的值。
上述的状态转移无疑是十分复杂的，我们发现可以简化状态。如果一个节点的子树内不存在军营，不论字数外是否有军营，它的贡献都是固定的。他可能会向某些祖先选择关键边，我们在祖先处统计。由此，我们得到了终极的状态：
\(f_i\) 表示考虑到节点 \(i\) 的子树，子树内存在军营并且所有军营都连边连向子树的根的方案。\(g_i\) 表示节点 \(i\) 的子树内的边的数量，\(g\) 的转移自然不必多说。
考虑节点 \(i\) 的可能性，显然有 \(2^{a_i+b_i}\) 种分配的方案，我们以此作为 dp 的边界。对于一个儿子 \(v\)，我们考虑如果这个儿子，没有被建造军营，答案就是 $f_i=f_i\times 2^{sum_v} $ 。如果建造了军营答案就是 \(f_i=f_i\times f_v\) 。最后，我们减去子树内都不选的情况也就是 \(2^{sum_i}\) 。那么节点 \(i\) 的贡献还要考虑子树外的边（不能有他连向父亲的那条边，不然会算重），\(ans=ans\times f_i\times 2^{m-sum_i-1}\) 。当然如果是根，他没有父亲，那么 \(ans=ans\times f_i\times 2^{m-sum_i}\) 。
这种做法为什么是对的，因为对于任意一种方案，只要有军营，就会在深度最小的点处被统计恰好一次，所以正确性显然。