← 返回题目列表

Codeforces · 2219/C

C. 为红黑树着色

中文机器翻译题面 查看原题

给定一棵由 $$$n$$$ 节点组成的树,编号从 1 到 $$$n$$$ 以及长度为 $$$n$$$ 的二进制字符串 $$$s$$$,其中 $$$s_i = 1$$$ 表示第 $$$i$$$ 个节点为红色,$$$s_i = 0$$$ 表示第 $$$i$$$ 个节点为黑色。您可以执行以下操作:

  • 选择节点 $$$a$$$ ($$$1 \le a \le n$$$)。
  • $$$a$$$ 的邻居 $$$b$$$ 是随机均匀选择的。
  • 使用 $$$b$$$ 的颜色重新着色节点 $$$a$$$。 请注意,这会更改您选择的顶点的颜色,而不是统一选择的顶点的颜色。

您希望通过执行任意次数(可能为零)的操作将树中的所有节点着色为红色。如果您以最佳方式执行这些操作,请计算所需的最小预期操作数。最初至少有一个红色节点。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。

第二行包含大小为 $$$n$$$ 的二进制字符串 $$$s$$$。

下面的 $$$n-1$$$ 行每行包含两个整数,其中第 $$$i$$$ 包含 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$),这意味着节点 $$$u_i$$$ 和 $$$v_i$$$ 之间有一条边。

保证给定的图是一棵树,至少有一个红色节点,并且所有测试用例的 $$$n$$$ 之和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个表示最小预期操作数的实数。

如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则视为正确。

正式来说,让您的答案为 $$$x$$$,陪审团的答案为 $$$y$$$。当且仅当 $$$\frac{|x - y|}{\max{(1, |y|)}} \le 10^{-6}$$$ 时,您的答案才会被接受。

示例

输入
复制

3
3
101
1 2
2 3
5
10010
1 2
2 3
3 4
2 5
3
010
1 2
2 3

输出
复制

1.00000000000000000000
4.50000000000000000000
2.00000000000000000000

注意

在第一个测试用例中,只有一个黑色节点,它只有两个红色邻居,因此,如果我们首先将操作应用于第二个节点,则只需一次操作即可得到一棵红色树。