面对他。
题面:
求选择关键点和不会被割的边,使得任意割去一条边关键点不会有不连通的方案。
考虑缩边双,然后这样边双内随便选。
你考虑画出一颗树,考虑分类情况,容易发现就是三种:
1.没有选。
2.全部连通上 \(x\)。(即一个尚未孤立的连通块)。
3.有不联通到 \(x\) 的点。(即孤立的一个连通块)
第三种情况显然就是只存在一个连通块的方案。
记其为 \(f_{x, 1/2/3}\)
\[f_{x, 1} = 2^{edg + m} \prod^{m} f_{y, 1} \]\[f_{x, 2} = 2^{edg + sz_x} \prod^{m} {2 * f_{y, 1} + f_{y, 2}} - 2^{m + edg}\prod f_{y, 1} \]\[f_{x, 3} = 2^{edg}\sum^{m} (2f_{y, 3} + f_{y, 2}) \frac{\prod^{m}f{y,1}}{2f_{y, 1}} \]分开转移即可。
哎,究竟有啥水平呢??哎。
究竟有啥水平呢??