luogu P5405 [CTS2019] 氪金手游()

题面传送门

可以发现，题目中的限制就是一棵树，但是方向不定，不是简单的内向树或者外向树。

如果是外向树该怎么做呢？发现这样的话设 \(i\) 及其子树内合法的概率为 \(f_i\)，那么要么不选到 \(i\) 子树内，要么要先选到 \(i\) ，然后再分成若干个独立的子树。这样的话概率是 \(\frac{W_i}{W}\)。

发现这个只和子树内 \(W\) 的总和有关，因此可以 \(O(n^2)\) 的 dp 解决。

现在不是外向树，考虑容斥，将内向边的概率变成没有这个限制的概率减去外向边的概率，也可以树上背包。

submission

————————

题面传送门

可以发现，题目中的限制就是一棵树，但是方向不定，不是简单的内向树或者外向树。

如果是外向树该怎么做呢？发现这样的话设 \(i\) 及其子树内合法的概率为 \(f_i\)，那么要么不选到 \(i\) 子树内，要么要先选到 \(i\) ，然后再分成若干个独立的子树。这样的话概率是 \(\frac{W_i}{W}\)。

发现这个只和子树内 \(W\) 的总和有关，因此可以 \(O(n^2)\) 的 dp 解决。

现在不是外向树，考虑容斥，将内向边的概率变成没有这个限制的概率减去外向边的概率，也可以树上背包。

submission