树

2219C. Coloring a Red Black Tree

• 每个节点初始为红色或黑色。
• 每次选择某个 node $a$，均匀随机选择 $a$ 的一个相邻 node $b$，将 $a$ 的颜色变为 $b$ 的颜色。
• 求使整棵树染成红色的次数的最小期望。
• 期望复杂度 $O(N \log N)$。

状态：

• $f_{u, 0}$：以节点 $u$ 为根的子树，父节点未染，完成目标所需次数的最小期望。
• $f_{u, 1}$：以节点 $u$ 为根的子树，先染父节点，完成目标所需次数的最小期望。

转移：

若 $u$ 初始为红，

$$f_{u, 0} = f_{u, 1} = \sum_{c \in \text{children}(u)} f_{c, 1}$$

若 $u$ 初始为黑，为将节点 $u$ 染红，设 $u$ 有 $k$ 个红色邻居，成功概率为 $\dfrac{k}{\operatorname{deg}(u)}$，期望操作次数是 $\dfrac{\operatorname{deg}(u)}{k}$。

$$f_{u, 0} = \min_{\varnothing \neq S \subset \text{children}(u)} \left\lbrace \frac{\operatorname{deg}(u)}{|S|} + \sum_{c \in S} f_{c, 0} + \sum_{c \in \text{children}(u) \setminus S} f_{c, 1} \right\rbrace$$

$$f_{u, 1} = \min_{S \subset \text{children}(u)} \left\lbrace \frac{\operatorname{deg}(u)}{|S| + 1} + \sum_{c \in S} f_{c, 0} + \sum_{c \in \text{children}(u) \setminus S} f_{c, 1} \right\rbrace$$

处理方程的后半部分，

$$\sum_{c \in S} f_{c, 0} + \sum_{c \in \text{children}(u) \setminus S} f_{c, 1} = \sum_{c \in \text{children}(u)} f_{c, 1} + \sum_{c \in S} (f_{c, 0} - f_{c, 1})$$

若固定 $|S| = i$，则贪心选取 $(f_{c, 0} - f_{c, 1})$ 最小的 $i$ 个。先排序，然后枚举 $|S|$ 转移。

当树的根是 $X$ 时，回答编号为 $[L,R]$ 的节点的 LCA。

【结论 1】根节点为 1 不变时区间 LCA：等价于区间 $[L,R]$ 中 DFN 最小值和最大值对应的两个点的 LCA。

【结论 2】根节点为 $X$ 不变时 $U,V$ 两点的 LCA：是 LCA$(X, U)$、 LCA$(X, V)$、 LCA$(U, V)$ 深度较大的。