[WC2023] 树据结构（暂为部分分题解）

1kri · 2023-01-19 15:55:24 · 个人记录

一些碎碎念：考完后大概想了 \text{20min} 胡出来一个 O(n \log n) 的做法，写了 \text{20min} 发现假了，但又花了大概 \text{40min} 就修好了。所以如果考场上我写完 2 的基础分就跑路，可能能拿到这 68 分吧。

考虑先将所有边权随机打乱。然后花费一些步数调整使得每条边权值小于子树内的所有边，并记录每个节点到父结点的边权。调整过程如下：动态维护出所有点的 \text{query} 值，每次取出最小的一个 \text{query} 值（记为 x）对应的集合。同时，我们记录当前未被确定的最小值 y。若 x \not = y，则 \text{exchange} 一下 x 和 y。这时，有且仅有 \text{query} 值为 x 的集合需要分裂，直接分裂即可。会出现仅一个点的 \text{query} 值等于 y，将这个点对应的边权记录为 y 。

这个调整过程的期望次数容易分析是 O(n \log n) 的。

然后我们确定了这棵树的结构，接下来按照对应边权从小到大来加点。每次添加点时，尝试二分它的父结点对应的边权。如果 \text{exchange} 当前枚举的边权 i 和二分的边权 mid 后，\text{query} 的结果不是 i 或 mid，那么我们直接就确定了父结点。否则若结果为 mid，就说明父结点边权小于 mid；若结果为 i，就说明父结点在 mid 对应的子树内，其边权就大于等于 mid。那么直接二分就可以了。

这时还有一个问题，我们的 \text{exchange} 次数最坏是 2 \log n 的，在特殊性质 \text{A} 中会被卡常。这里有一个很大的优化，就是每次可以直接询问是否挂在上一个结点下，直接这样就可以通过前 17 个测试点了（指样例 1-6）。