CF2220F 题解

前言

好想哭啊

思路

定义 $f_2(u)$ 为：在从根到 $u$ 的路径上的点的点权构成的集合中插入 $f(u)$ 后，新集合的 $\operatorname{mex}$ 值。开局先预处理所有 $f(u)$ 和 $f_2(u)$ 的值，在 dfs 时用 set 维护从根到 $u$ 的集合的补集即可。

考虑对 $u$ 进行操作后对其子树的影响。

• 首先特判 $f(u)=p_u+1$ 的情况，此时操作后树上没有 $p_u$，整个 $u$ 子树内的点的 $f$ 值都会变为 $p_u$。
• 我们考虑将一次操作拆成两次：插入 $f(u)$ 和删除 $p_u$。
  • 插入 $f(u)$ 时，对于所有 $u$ 子树中的点 $v$，若 $f(v)=f(u)$ 则 $f(v)$ 会变成 $f_2(v)$，否则没有影响。
  • 删除 $p_u$ 时，对于所有 $f(v)>p_u$，$f(v)$ 会变成 $p_u$。否则没有影响。

将两次的贡献合并，可以得到暴力做法：对于所有 $u$ 子树中的点 $v$，若 $f(v)=f(u)$ 则贡献为 $\min(f_2(v),p_u)$，否则为 $\min(f(v),p_u)$。把 $\min$ 拆开，会变成三个三维偏序问题，但其中一维限制是等号或不等号，可以像二位偏序一样用扫描线求解，用 $\mathcal{O}(n)$ 棵动态开点线段树维护等号或不等号。复杂度 $\mathcal{O}(n\log n)$。