题解：CF2062E2 The Game (Hard Version)
CReatiQ
·
·
题解
若对任意 w_v>w_u，总有 v \in \text{subtree}_u，选 u 者必败，我们称 u 为坏点。
对于 E1，选 w 最大的不坏点即可，此时对手只能选坏点。
E1 策略告诉我们，只要对方可以选不坏点，我们必败。
所以 E2 策略是：选择迫使对手只能选坏点的点。
假设这样的点为点 u，则对任意 w_v>w_u：
-
要么 v 在 u 子树内。
-
要么对任意 w_t>w_v：
-
-
我们可以将第二点重写为：
- 对任意 w_t>w_v 且 t 不在 v 子树内：t 在 u 子树内。
记 g=\text{lca}(t)，便可进一步重写为：
（顺便提一嘴，求 g 就是求树上点集的 \text{lca}，直接找点集里 dfn 最小最大的两个点，取 \text{lca} 即可。）
于是一个点满足 E2 策略可以写成下面的形式：
\begin{aligned}
&(v_1 \in \text{subtree}_u \text{ or } g_1 \in \text{subtree}_u) \\
\text{ and } &(v_2 \in \text{subtree}_u \text{ or } g_2 \in \text{subtree}_u) \\
\text{ and } &\dots
\end{aligned}
上面的式子可以进行这样的合并：
\begin{aligned}
&(v_1 \in \text{subtree}_u \text{ or } g_1 \in \text{subtree}_u) \\
\text{ and } &(v_2 \in \text{subtree}_u \text{ or } g_2 \in \text{subtree}_u) \\
\end{aligned}
\Leftrightarrow
\begin{aligned}
&\text{deeper}(\text{lca}(v_1,v_2),\text{lca}(v_1,g_2)) \in \text{subtree}_u\\
\text{ or } &\text{deeper}(\text{lca}(g_1,v_2),\text{lca}(g_1,g_2)) \in \text{subtree}_u
\end{aligned}
其中 \text{deeper}(u.v) 代表 u,v 中深度更大的点。
这样所有 v 对 u 产生的约束最后都会合并为 (a \in \text{subtree}_u \text{ or } b \in \text{subtree}_u) 的形状。
实现上，将点按 w 分组，从大到小扫过每个组，考虑当前点是否满足约束以及当前点对后续点带来的约束即可。