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

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

看见题目就想到期望DP。

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

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

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

题面有点长就不解释了，大家自己翻译吧。

首先有一个 Simple 的想法，直接维护啊，变的节点又不多，修改不是 $O(1)$ 的吗？

然后发现错了。

作为一道英文题，我们先解释一下题意：

给你一棵树和它的一个 BFS 序，让你判断这个 BFS 序是否是一个从节点 1 开始的合法 BFS 序。

接下来我们进入正题。

第一眼看到这题时，大部分人都会想到，既然是树，那么它一定是一层一层地向下 BFS。

也就是说，BFS 序中越后出现的节点，它树上的深度肯定是大于它前面的节点的。

于是照这个思想打完后，发现 Wrong Answer 了。