CF_Edu

¶Edu181-D. Segments Covering

$dp[i]$: 前$i$ 段被精准覆盖一次的概率
$dp[i]=\sum_{\{l,r==i,p,q\}} dp[l-1]\times\frac{p}{q}\times\frac{T_i}{T_{l-1}\times\frac{q-p}{q}}$
$T[i]$: 右端点在 $i$ 左端的线段都不存在的概率
$\frac{T_i}{T_{l-1}}$: 右端点在 $l,r$ 的线段都不存在的概率

¶Edu180-D. Reachability and Tree

任意相邻边方向相反可以保证 $n-1$ 对满足条件的对。
找到一条度数为 2 的点，使其两边方向相同，形成一条为长度为 2 的路径，此时对数 +1。

¶Edu180-E. Tree Colorings

首先考虑给定一颗树，如何求美丽染色的方案数。
$dp[i]$: 以 $i$ 为根的子树美丽染色的方案数。
根节点涂绿色，子节点 $j$ 可涂绿色，方案数为 $dp[j]$ ，或者整棵树涂蓝色或黄色，所以总方案数为 $dp[j]+2$。
$dp[i]=\prod_{j\in son\{i\}} (dp[j]+2)$
注意叶子节点的方案数为 $dp[leaf]=3$ ,且每次 $dp$ 都+2，奇偶性不变，一直是奇数，所以方案数只可能是奇数。

回到问题本身，方案数为 $m$ 的一棵树，他的方案数 $m$ 是由多个奇数乘积得到，而这棵树本身是由多棵子树拼接得到。
如 $m=m_1 \times m_2 \times m_3 ...$,
树的大小 $size=size_1 + size_2 + size_3 ...$。
此时设 $dp[m]$:方案数为 $m$ 的最小需要节点数。
$dp[m]=min\{dp[m_1]+dp[m_2 - 2]\}, m_1 \times m_2 = m$ 。