0%

uoj#372 题解 - 【UR#17】滑稽树前做游戏

题目链接

首先这种鬼题都是独立性非常难考虑,所以一般来讲都是直接对整个图考虑,做子集 DP。

显然用限制条件(边)肯定比一个单个的元素(好)。所以我们下面直接对图讨论了。

我们的函数显然肯定有一维 $x$ 表示要求答案 $\le x$,但是这显然是不够的,我们再考虑加一维 $y$ 表示要求所有点权 $\le y$。

设 $F(s,x,y)$ 表示当前考虑的子图为 $s$,$x,y$ 的含义如上,的概率。

考虑枚举点权最大值 $w$。

$2w<x$。此时一切约束都被满足。发生这种情况必然有所有点权 $\le \dfrac x 2$,所以概率为 $\left(\dfrac x 2\right)^{|s|}$。

$2w>x$。此时,设点 $i$ 取到了最大值。考虑和 $i$ 有边的 $j$,显然除了 $(i,j)$ 我们可以不考虑任何其他 $j$ 连出的边。显然对于 $j$ 我们要求它 $\le x-w$,对于其他点,我们只要求 $\le w$ 且答案还是 $\le y$。

设去掉 $i$ 和 $j$ 的图为 $s_i’$。我们得到方程

大力 DP 即可。注意 $s$ 可能不连通,这时候拆成数个连通块跑。加上这个优化就莫名能跑 $n=25$ 了,非常神必。