20210716 世界线,时间机器,weight

终于有一场在晚上考了

T1 随便画了画就发现要求每个点的后继个数，想起来有 dfs 和 toposort 两种方法，感觉很稳

T2 裸的网络流有 70pts？！真香

一看 T3 就想起了 Mst，随便建个 MST 然后枚举非树边在树上搞搞就行了，画了画图发现可行（但心里对这个算法对正确性并不太肯定）。在树剖+线段树和 LCT 之间选择了 LCT，毕竟刚背了 LCT少个 \(\log\)

感觉这次题都比较可做，暴力分也很多，rk1 可能要 250+，决定冲 T3 的数据结构

19.00 就开始写了，绝望的发现 T1 不会做，先写了暴力 bitset，发现极限数据也跑得挺快，就是会 MLE。尝试 dfs 出一颗生成树，然后树上差分，画了画图发现不行。不管了

T2 飞快写完 ISAP，一遍过样例。部分分太香+着急写 T3 就没多想。又回头看 T1，仔细回想 受欢迎的牛 和 bitset 水过去的 连通数，悔不当初。（当时以为有 \(O(n)\) 在 DAG 上 DP 的方法）

19.40 终于开始写 T3，先后经历了 CE WA RE，20.50 过样例，想了想还是写了对拍，但只是把树上更新的部分换成了暴力跳 fa，只能拍出 LCT 有没有写挂，算法正确性无法保证（不会写其他暴力）。结果从 9.10 开始拍，LCT 和暴力轮流挂，直到快 9.30 才稳定拍上，最终只拍了一百多组。此时发现 T1 还有图退化成树的 20pts 没写，Rush 了 10min 写完了，在结束前 40s 提交。

ycx 说听到我一直在敲键盘。。。今天默板子是真爽

rk1 40+60+100

T1 树的分还是没拿到（默认了根是 \(1\)）

T2 挂了第 1 个点（由于存边的数组开了 \(N*N\)，因此 \(N\) 没敢开大，而第一个点恰好是 \(n=1,m=5\times10^4\)）

rk3 ycx 60+70+30

rk4 贾一丰 40+100+0

正解就是 bitset。。。

防止被卡空间要开成 <code>bitset&lt;N/2&gt; siz[N];</code>，然后每次只在 bitset 中转移一半点。

code

贪心。

按 \(low\) 从小到大考虑每个结点，每次在 \(l\le low\) 的电阻中匹配 \(high\le r\) 且 \(r\) 最小的，暴力是 \(O(nm)\) 的，可以用 set 或权值线段树优化这个查找的过程。

显然 set 中可能有重复元素，要开 multiset，但实测不开可过。hack：

正确性：断开一条树边后形成两个连通块，考虑连接这两个连通块的边何时一定比其它边优

我的 LCT 被树剖+线段树吊打。。。

考场 code