2022/8/3 考试总结

时间安排

7:30~8:00

先看了一遍题，感觉一道都不会，非常自闭。

8:00~9:00

写了T2的暴力。

9:00~9:20

写T3的暴力

9:20~10:00

写T3的第二和第三档，但是不知为什么答案总是会大。
于是就放弃了

10:00~11:00

T1可以斯特林拆幂之后容斥做，但是不知道为什么答案总是不对。自闭。

11:00~12:00

想了想T2的$O(n^2)$，写完过了大样例。

考后总结

T1

就是套路的用斯特林数拆幂，转化为组合意义，然后通过容斥进行dp，总之就是非常套路。
考试的时候有个细节写错了，导致挂了。

T2

$O(nlo{g}^{3}n)$

dsu on tree，然后用树链剖分统计$d[y]-2\ast cnt[x][y]$
复杂度$O(nlo{g}^{3}n)$，但是常数不大。不过非常好些。

$O(nlo{g}^{3}n)$

用线段树合并维护，然后还是树链剖分，不过空间是$O(nlo{g}^{2}n)$，很危险。
于是把每一条重链公用一棵线段树，于是空间单log。

T3

就是dp，只不过出题人实现的更妙。
待upd。