CSPS2025游寄

初赛阿克了，然后不知道为什么被挂出来展示，所以几乎所有来我们考点考试的人都会看到我的神秘照片。

A 一眼题，B 首先可以只保留原图 MST 上的边，然后可以 $2^k$ 枚举乡村的状态，然后 kruskal 就可以 $O(2^kn(\log n+k))$ 或 $O(2^knk\log n)$，但我的脑袋忽然变成了浆糊，于是就直接跳了？还好大样例只跑了 0.05s。

upd：我好像不小心写成 $O(2^knk^2)$ 了，期待挂分。

然后就是一些神秘操作，C 很快会了一个二维数点做法，但是空间看成了 512MB，于是怒写压缩 trie，拍了一个 4.4k 的东西上去。还好过了大样例。

然后就没啥时间做 D 了，随便打了 36pts，最后（可能）会了个 $O(n^4)$ 做法，但是好像巨大难写，没写完就摆了。

upd：其实这个做法是 $O(n^3)$ 的，赛后写了一发过了。但也没啥用了。

总结一下，BC 各犯了一个唐，D 感觉其实也不是不能做的题，怎么会打成这样呢？感觉下周要被拷打说我 flagle 玩太多了，老是分心去做别的事了。

还好这不是 noip。

upd：$100+100+100+36=336$。冷知识：通过 t2 的方法是多 $k$ 或者少 $k$。