题解：CF1930G Prefix Max Set Counting

· · 题解

取出所有 u=\max_{v \in sub_u} v 且 u=\max_{u \in sub_v} v 的 u 构成 S，不加证明地给出如下结论（其实很好证我只是懒得写了）：

f(a) 和 f(a) \cap S 构成双射。

接下来把所有不在 S 中的点抹掉，只保留 S 中的点和其构成的虚树结构考虑问题，容易发现此时 S 内的点是所有叶子。

将一个点 u 的所有儿子按照子树内叶子的 \max 从大到小排序并编号，那么答案序列倒过来后如果在 u 子树内依次选了叶子 p_1,p_2,\dots,p_k 则这些叶子对应的儿子子树一定编号递增。

所以将儿子排序后求出先走编号小的儿子的 dfs 序（只保留叶子）L，我们在 L 上 dp。

设 dp_u 表示答案序列是 u \to n 的方案，转移看上去不太好处理？因为跟树的结构有关，考虑在树的结构上处理转移，具体而言我们将 x \to y 的转移在 \text{LCA}(x,y) 处考虑，容易发现如果考虑了 u 的儿子 son_1,son_2,\dots,son_k 要处理 x \in \cup_{i=1}^k son_i,y \in son_{k+1} 的 x \to y 的转移时，只要满足 y 是 son_{k+1} 内最大的叶子且 x>y 就一定合法（并且这也是合法的必要条件），所以我们可以使用线段树维护 son_1 \sim son_k 内的 x>y 的 \sum dp_x，而 k \gets k+1 时就把 son_{k+1} 的线段树和 \cup_{i=1}^k son_i 的线段树合并即可，容易发现可以在 dfs 过程中边线段树合并边求解 dp 值，那么就做到了 O(n \log n)。