CatOJ C140（初中）
\(100+93+100+10=303\)，Rank 1。
是个 dp 场，A 题期望 dp，B 题神奇猜结论，C 题换根 dp，D 题树上博弈 dp。
A 题设 \(f_u\) 为填满子树 \(u\) 的期望次数，\(s_u\) 为 \(u\) 子树大小，容易得到 \(f_u=f_v+\frac{1}{s_u}\)。
B 题若 \(n\) 是偶数，考虑数列里随便取一个数将其变成奇数，然后按 \(a\) 从小到大排序，先取最后一个，然后按顺序每两个数为一组，一组中取 \(b\) 大的，证明略。
C 题设 \(u\) 的子树中至少有 \(x_u\) 个节点染黑，\(u\) 的子树外至少有 \(y_u\) 个节点染黑，考虑一次根节点向下的 dp 和一次叶子节点向上的 dp，最后 \(x_u\) 和 \(y_u\) 拼起来取最大。复杂度显然 \(\mathcal{O}(n)\)，吊打标算 \(\mathcal{O}(n\log n)\)。
D 题不会，咕了。
标签：Contest,VP,模拟,mathcal,100,节点,dp From： https://www.cnblogs.com/kowenxrz/p/17337938.html