CF2219C Coloring a Red Black Tree

给定一个有 $n$ 个结点的树，结点编号从 1 到 $n$。另外还给出了一个长度为 $n$ 的二进制字符串 $s$，其中 $s_i = 1$ 表示第 $i$ 个结点被染成红色，$s_i = 0$ 表示第 $i$ 个结点被染成黑色。你可以进行以下操作： - 选择某个结点 $a$（$1 \le a \le n$）。 - 均匀随机选择结点 $a$ 的一个相邻结点 $b$。 - 将结点 $a$ 的颜色变为结点 $b$ 的颜色。注意，改变颜色的是你选择的 $a$ 结点，而不是被随机选择的 $b$ 结点。 你的目标是通过任意多次（也可以一次都不做）上述操作，将整棵树的所有结点都染成红色。请你计算出，在最优策略下，使所有结点最终都变成红色所需操作次数的最小期望值。 保证一开始至少有一个结点为红色。

每组测试数据包含多组测试用例。第一行为测试用例数 $t$（$1 \le t \le 1000$）。每组测试用例的描述如下： 第一行为一个整数 $n$（$1 \le n \le 2 \times 10^5$）。 第二行为一个长度为 $n$ 的二进制字符串 $s$。 接下来的 $n-1$ 行，每行有两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$），表示结点 $u_i$ 和 $v_i$ 之间有一条边。 保证给定的图是一棵树，并且至少有一个结点初始为红色。所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

对于每组测试用例，输出一个实数，表示最小期望操作次数。 如果你的答案与标准答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。 形式化来说，记你的答案为 $x$，标准答案为 $y$，仅当 $\frac{|x - y|}{\max{(1, |y|)}} \le 10^{-6}$ 时，判为正确。

在第一个测试用例中，只有一个结点是黑色，而它有两个红色相邻结点，因此，如果我们首先对第 2 个结点操作，整棵树在一次操作后就会全部变红。 由 ChatGPT 5 翻译