Day -11

GG.

P3750 [六省联考2017]分手是祝愿

先考虑 n = k 时，若不能重复开关某一盏灯，有且仅有一种操作序列能将灯全部关闭，我们称该操作序列里所有灯为关键灯。更强的性质：一个关键灯无法被任意多个灯取代。

设状态 f_i 表示将操作序列里存在 i 盏关键灯转移到操作序列里存在 i - 1 盏关键灯，则状态转移方程为 f_i = \frac{i}{n} \times 1 + \frac{n-i}{n} \times (1 + f_{i + 1} + f_i).

解释就是，有 \frac{i}{n} 的概率会刚好按到关键灯，有 \frac{n-i}{n} 的概率会按到其他的灯，是关键灯集合大小 +1。 再按灭当前的灯。

附：为什么要从 n 开始 dp 而不是从 tot (当前序列关键点集合大小）开始。因为一定存在一种序列使得关键灯集合大小为 n 故需要从 n 开始 dp。

火枪打怪

二分。judge 时拆掉二次函数按照单项式分别加入队列，维护队列内和。

？？？

晚上在校园里走竟然能踩到钉子？？？？还扎穿了鞋底扎破了皮？？？

晚上颓 ow。

Day -10

早上困困困，直接在机房睡到 8:45.

天天爱跑步

神仙题。

树上问题好像一般都得分类讨论。

考虑一个观察员 i 能观测到路径，起点 s 或终点 t 至少一个在 i 的子树里。

若 s 在 i 子树中，则能被 i 观测到的条件为 dep[s] - dep[i] = w[i]，移项后发现 dep[s] = dep[i] + w[i] ，故使用动态开点线段树维护，下标为深度（非绝对深度）。

若 t 在 i 子树中，则能被 i 观测到的条件为 dis(s, t) - (dep[t] - dep[i]) = w[i] 套路性移项得到 ```dep[s] - 2dep[lca] = w[i] - dep[i]$。

树上差分维护即可。