前言
米奇妙妙 \(\rm{dp}\) , 也是高端计数
这种题看得懂想不出, 还是非常难蚌
能不能多想想再去看 \(\rm{TJ}\) 啊
算法
注意到除了割边, 其他的边都没有影响, 显然可以缩 \(\rm{e}\)-\(\rm{DCC}\) 再进行处理
这里发现缩完之后形成一棵树, 考虑树形 \(\rm{dp}\)
这里我有一个误区, 就是答案必须要是几个 \(f_x\) 组合到一起, 但是实际上完全不用
对于树这种特殊结构, \(f_{root}\) 已经包含了所有情况
因此令 \(f_{x, 0/1}\) 表示只在 \(x\) 的子树之内建造军营, 军营的
首先考虑答案式子, 我们注意到, 答案应该是多种情况累加, 因为 \(f_{x, 1}\) 实际上是不重不漏的, 主要需要处理的是那些无关紧要的边, 我们选择守或者不守
注意到如果缩完点之后当前子树的大小为 \(Size_x\) , 我们就有 \(Size_x - 1\) 条割边要守, 其中子树外的 \(m - Size_x + 1\) 条边可以任选
这里有一个超级巨大的问题: 对于当前节点到父节点的边, 一定不能选, 因为对于父节点, \(f_{fa, 1}\) 实际上考虑了这条边, 选上之后会导致重复, 因此记录答案时不能算这条边
事实上如果最早就有关于答案式的思路, 可以通过手推样例/观察性质发现这种性质, 但是我还是大为震撼
所以答案为
\[\sum_{i = 1, i \neq root}^{n} f_{i, 1} \times 2 ^ {m - Size_x} + f_{root, 1} \times 2 ^ {m - Size_x + 1} \]太有实力啦
考虑递推
首先我们需要知道, 如果对于 \(x\) 的子树 \(son\) , 其中 \(son\) 内部有军营, 那么 \(x \to son\) 这条边必须要守, 其他无所谓
所以有
\[f_{x, 1} \gets f_{son, 1} \times f_{x, 0} + f_{son, 1} \times f_{x, 1} \]\[f_{x, 0} \gets f_{x, 0} \times f_{son, 0} \times 2 \]\[f_{x, 1} \gets f_{x, 1} \times f_{son, 0} \times 2 \]初始化
\[f_{x, 0} \gets 1, f_{x, 1} \gets 2 ^ {Siz_x} - 1 \]注意这里表示的是只选 \(x\) 这一 \(\rm{e}\)-\(\rm{DCC}\) 中点的可能性, 反正可以随便选, 边随便选的情况在计算答案时统计
代码
后补
总结
神秘计数方法
\(\rm{dp}\) 式子考虑不到的, 可以在统计答案时考虑
注意计数不重不漏, 注意初始化
标签：gets,答案,建造,son,军营,NOIP2022,rm,times,Size From： https://www.cnblogs.com/YzaCsp/p/18561058