CSP-S 前要多做树上问题 （主要是因为去年 NOIP D1T3、D2T1、D2T3 全是树上问题，然后爆炸了） 。

这题一看就是树形DP，状态也是一眼就能想到的。

令 $f_{i,j}$ 表示 $i$ 这个点染成 $j$ 的方案数，枚举 $son_i$ 的颜色来转移。

最后答案即为 $\sum_{i=1}^{m}f_{1,i}$。

作为一道英文题先解释一下题意。

用 $T$ 秒时间按顺序听 $N$ 首歌，第 $i$ 首歌播放时间为 $t_i$ 秒，且每播放一秒都会有 $p_i$ 的概率被识别出来，跳到下一首。某首歌播放时间过完默认被识别，也跳到下一首。若时间有剩余而歌已全部听完则直接结束。求识别出歌数量的期望。

看见题目就想到期望DP。

第一眼想到的方程是设 $f_{i,j}$ 表示第 $i$ 秒识别到第 $j$ 首歌的期望，不难想出一个 $O(n^3)$ 的算法。

枚举一个 $k$ 表示第 $j$ 首歌已经放了几秒，注意一下边界即可。

我们根据题意，发现这是一个 DP 题，定义 $f_{i,j}$ 表示在高度为 $i$，当前要爬的树为 $j$ 所能获得的最大柿子数。

易得状态转移方程：$f_{i,j}=max(f_{i-1,j},f_{i-delta,k}) (1\leq k \leq n)$，当 $i>delta$ 时后一项成立。

于是我们得到了一个时间复杂度为 $O(H \times N^2)$，空间复杂度为 $O(N \times H)$ 的算法啦。。