hao
D
[deleted]
这个题最核心的考虑是，删掉一个点如何快速重新建立凸包。假设点集是\(p_{1,...,n}\)，求他们的凸包，得到顺时针凸包\(q_{1,...,m}\)。如果删掉凸包上的\(q_i\)，重新求凸包，那么就需要把点集\(p_i\)中所有在\(q_{i-1},q_i,q_{i+1}\)构成的三角形中的点拿出来重新求凸包，把求出来的凸包跟之前的凸包拼起来。如何枚举在\(q_{i-1},q_i,q_{i+1}\)构成的三角形中的点呢？可以考虑把所有点按照相对于\(q_1\)的极角排序，只需要lowerbound找出\(q_{i-1},q_{i+1}\)极角之间的点，然后for一遍找出三角形内部的点就可以了。这样的话，如果要iterate i，由于每个点只会被for两次，复杂度就是对的。删去\(q_1\)特殊处理下。
要讨论的三种情况已经在样例中给出，解决这三种情况就能解决这个题。有了上面的枚举方式，可以很轻松的解决这三种情况。其中，第三个样例对应的情况需要嵌套考虑，枚举删掉的第一个点之后，内部再嵌套一个“删一个点的最小凸包周长”解决就行了。
K
[deleted]
显然这个是树上多出来16条边，那么32个关键点，把虚树扯出来，再建简化图，只有60个点80条边。
然后稍微画一画就能看出来，一个额外边集最多对应一个环。怎么求一个额外边集能不能对应一个环呢？考虑把每个额外边自己在树上形成的单环拉出来，如果这个额外边集内的这些额外边的单环形成的对称差是一个大环就可以，否则就不行。简化图的点很少，可以直接\(2^{16}\times 16 \times 80\)暴力。