时间线

• 20:01-20:02 A
• 20:02-20:09 B
• 20:09-20:20 C
• 20:20-20:34 D
• 20:34-21:40 E

得分

错因分析

E

错因：不会倍增。
倍增可以以 级别的时间复杂度处理跳 步的问题。定义 表示从 出发跳 步到达的点的编号， 表示从 出发跳 步到达的点的编号之和（多次经过重复计算）。预处理一下 ，对于每个询问，对步数进行二进制分解然后跳。

F

错因：没时间。不懂得如何加入新的点。

不难发现，答案就是 。

从加入新的点出发，考虑原来 的点可以被路径 包含，加入新的点 。分类讨论：

• 已在 上，则不变。
• 否则，若 在路径 上，则 ；同理，若 在路径 上，则 。
• 否则，说明 0 到 之间的点不能被一条路径包含，退出循环。 至于如何处理包含路径 的路径条数，按 之间是否有祖孙关系分类讨论，然后求解。