我是考场策略大师
A
\(O(|s||x||y|)\) DP 是朴素的,上个 bitset 除个 \(w\) 即可。
B
称花费 \(A\) 的操作为一操作,花费 \(B\) 的操作为二操作。
注意到可以先做一操作(选出若干条边,加它们的重边)再做二操作,
而做完一操作之后,设有 \(k\) 个度数为奇数的点(下称“奇点”),则需要做 \(k/2-1\) 次二操作。
设 \(f_{u,0/1/2}\) 表示做完一操作后,(\(u\) 子树内没有奇点 / \(u\) 是奇点 / \(u\) 不是奇点但 \(u\) 子树内有奇点)时所需的最小代价。
转移比较平凡,分讨时注意细节。
C
根据期望线性性,\(f_u\) 等于 \(\sum\limits_{i_1=1}^n\cdots\sum\limits_{i_k=1}^nP(i_1\dots i_k\text{ 都在 }u\text{ 子树内})\),
也就等于任选出 \(k\) 个点,都在 \(u\) 子树内的概率乘上 \(n^k\)。
虚空加 \(k\) 个附加点 \(n+1\dots n+k\),它们的父亲取 \([1,n]\),
把 \(k\) 个附加点的父亲看成上面任选出的 \(k\) 个点,则需要求附加点的父亲都在 \(u\) 子树内的概率,即附加点都在 \(u\) 子树内的概率。
从后往前构造这棵树,设 \(f_{i,j}\) 表示只留 \(\ge i\) 的点,附加点被分到 \(j\) 棵树中的概率,则需要求出 \(f_{u,1}\)。
考虑转移,\(f_i\) 的状态只比 \(f_{i+1}\) 的状态多加了 \(i\),也就是只选出了若干棵树的根连到了 \(i\),
若在 \(f_{i+1,j}\) 的状态中选出 \(l\) 棵树的根连到 \(i\),则转移到 \(f_{i,j-l+1}\),有转移:
\[f_{i,j-l+1}\gets f_{i,j-l+1}+f_{i+1,j}\times{j\choose l}(i-1)^{j-l}/i^j \]枚举 \(l\) 转移即可。