今天摆了。
上午打 S 组模拟赛，T1 五分钟切了，T2 划拉了划拉切了，但是写的时候键盘寄了???，jimmy 帮忙搞了一个小时才搞好??，然后想了两个小时 T3 想到了 dp 做法，但是边界写挂了?。T4 直接 \(O(nq)\) 打 60pts?。
最终得分：\(100+100+20+60=280pts\)，rk10，菜逼??
下午 jimmy D 了一顿我们不用 noilinux，虽然我觉得 jimmy 说的逆天，但是我觉得 pjw 也做的有点极端了?。
ytq 你再说珂朵莉
ytq 18:54:13
这T4是不是可以珂朵莉
Chess 被 crimson000 禁言1小时
ytq 19:00:55
我现在看见一个题不会做就开始瞎jb想珂朵莉
haosen 19:01:24
@ytq 不应该想谷树？
Tokai Teio 19:01:57
应该想GCY上XZT
ytq 19:02:21
@haosen 古树运行的太快了，虽然都是爆蛋的分数，但是珂朵莉可以多卡一会儿评测机（）
haosen 19:02:37
草
crimson114514 19:02:43
你先把镜中的昆虫写了再给我来这说珂朵莉
虚了
指打 CF
无端联想（
你画我猜精选
答案：乌贼
推歌：亡霊 -あよ
虽然但是这首歌是我从戴老师的推歌里面赫来的（
CF605E
我们设 \(f_u\) 为 \(u\to n\) 的期望步数，那么显然 \(f_n=0\)。我们考虑转移。
我们可以发现，如果有一条 \((u, v)\) 的边出现了，那么当 \(f_v>f_u\) 时，我们一定不会去走 \((u, v)\) 这条边。因为我们这样走的期望步数还会增加，还不如直接走个自环。而当如果所有 \(f_{v'}<f_v\) 的 \((u, v')\) 这条边不存在时，我们才会走 \((u, v)\) 这条边。
因此我们可以初步写出一个方程：
移项得到：
这就是我们要的转移式子。
我们再考虑如何更新。我们可以发现一个点如果考虑的点越多，它的 \(f\) 是不增的，同时不可能会用更大的 \(f\) 来更新它。换句话说就是如果一个点的 \(f\) 是全局最小，那么就没有别的点会更新它，也就是它的 \(f\) 值已经固定了。我们就可以用类似 dijkstra 的思路来更新了。
时间复杂度 \(O(n^2)\)。
感谢 haosen 给我讲上面这道题 ??????????????
