NOI2026 D2T2 题解

_Ch1F4N_ · 2026-07-22 21:57:31 · 题解

场上过了写个题解。

考虑从 Prüfer 序列还原树（认为最大点为根），维护当前的叶子集合 S，每次取出最小的确定父亲，并且假如父亲是最后一次出现就将其加入 S 集合。

考虑对于一组询问的 x,y 找出其的父亲，下面以考虑找出 u 的父亲为例。考虑不维护 S 集合而是直接维护 \sum_{x \in S} [x < u] 的值，过程大概是从前往后扫描，如果遇到的位置是当前的数最后一次出现且 <u 那么值不变，否则减 1（所有没出现过的数会给初始值加 1），在碰到 u 最后一次出现时会让值对 0 chkmax，在 u 最后一次出现之后如果某个时刻操作完值变成 0 了那么下个位置就是 u 的父亲。

考虑对 r_i 扫描线，用树套树维护每个值在序列中最后一次出现位置，回答询问就取出 [0,u) 中的值在内层线段树的出现位置信息，先计算一下初始值再多树二分找出被减到 0 的时刻即可（由于是线段树，多树二分可以直接把 \log n 个根传进去），时间复杂度 O(n \log^2 n)。

直接实现这个可以获得 40 分的好成绩，因为常数太大了，考虑这样一个事情：对于 x,y 而言最后一次出现位置靠前的一定是作为儿子，那么我们只用找一次父亲而不是两次，如此便可以将常数砍半，可以通过。

至于空间问题，虽然空间是 O(n \log^2 n) 但是常数为 1，算一下刚好开的下。