树链剖分

CodeForces Round #502 Problem G – The Tree

这是lty数据结构专题里唯二自己做出来的题目中的一道。

如果不包含“将 $x$ 的子树全部染白”的操作，应当怎样处理？

题目所给操作可以这样转述：令 $x$ 为本次染色操作的节点。若 $x$ 为白色，则立刻染黑并退出；否则我们找到其子树中的，与 $x$ 相连的黑色连通块，则对于每个连通块底部节点，若其不是叶子节点，我们将其儿子染黑。

由于本题的树没有特殊性质，且将来加入回退操作，故而难以维护整个连通块以及其叶子节点。因此，我们可以从“在何种情况下，节点 $x$ 被染黑”的方向考虑。

显然，只有从在 $x$ 到根的路径上的节点开始的染色操作，才可能波及到 $x$。假如最终 $x$ 被染黑的一瞬，它被包含在了以 $\text{comprt}$ 为根的连通块中。令链 $\langle\text{comprt}, x\rangle$ 为 $\left\{x_1,x_2,\dots,x_n \right\},x_1=\text{comprt},x_n=x$，那么自然想到，一种一定合法的染色序列是 $\{y_1,y_2,\cdots,y_n\}$，其中有 $\forall k \in [1, n] \cap \mathbb{Z},y_k \in \{x_1,\cdots,x_k\}$，也即我们每一步都在该连通块内部，并将连通块的最大深度推进一层。

这种序列确实合法（它是充分条件），但这真的是 $x$ 被染黑的必要条件么？ （更多…）