补题记

· · 个人记录

听 @zjy2008 说可以补一下 CTT，按他游记里写的难度排序补一下。

看看能补多少

easy

D1 T2

容易发现对相同颜色相当于括号串里加减括号维护匹配上的集合，对没匹配上的位置放线段树上求全局和与最小前缀和。两部分都是比较套路的。

D2 T1

容易发现答案一定小于等于 2，等于 1 当且仅当满足特殊性质 2，选择度数最大的点，通过反证法易证。

然后考虑随机化，每次选择一个点，查询所有和它相邻的边，若它指向所有其他点，则返回它的标号，否则删除该点和所有它指向的点，每次随机化期望点集大小折半。

随机化，too hard。

D3 T3

我有一个绝妙的做法，操作次数优化到了 3\times n\times\log n 左右，实测次数都在 4\times 10^5 之下

考虑充分发挥“最大的连通块”的性质，第一时间想到的是重心，它具有删去该点后最大的连通块的大小最小的性质，于是我们求出所有点删去该点后最大的连通块的大小，并按照此值从小到大排序。排完序后我们发现这个序列的性质非常的好！首先，以重心为根，所有点的父亲都在这个点之前出现，其次，不管如何连边，所有前缀都是一个连通块！而我们要判断一个点的父亲是否在一个连通块内，只要加入这个点然后看最大联通块大小是否发生变化就行了，于是我们整体二分，轻松取之。

D3 T2

倒着做，然后大力状压，复杂度不明，仙姑了。

medium

D2 T3

神秘结论题。

结论：若非菊花，次数为拓扑深度为 2 的节点的个数。否则为 2。

证明：对每个拓扑深度为 2 的节点及其叶子组成的集合中，一定有至少一个被选为根。

可行性构造：从所有拓扑深度为 2 的点出发 dfs，边的顺序先去访问所有叶子，再去访问非叶子，第二次及以后 reverse 每个节点的叶子顺序。易证这样是可行的。