给定一棵由 $$$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}$$$ 时,您的答案才会被接受。
示例
输入复制
331011 22 35100101 22 33 42 530101 22 3
输出复制
1.000000000000000000004.500000000000000000002.00000000000000000000
注意
在第一个测试用例中,只有一个黑色节点,它只有两个红色邻居,因此,如果我们首先将操作应用于第二个节点,则只需一次操作即可得到一棵红色树。