题目描述

有一课大树，这棵树非常巨大，树上有 $n$ 个位置可以种树，对于第 $i$ 个位置来说，在这里种的树一般来说会长成 $x_i$ 克，但如果一棵树旁边还有种有别的树，那他们就会争抢营养，这棵树会变为 $\frac{x_i}{cnt_i+1}$ 克（$cnt_i$ 为第 $i$ 棵树旁边种的树的个数）。

种树人希望让种下的树的总质量最大，他希望你帮他找出一种优秀的种树的方法和其结果。

输入格式

本题有多组测试

第一行一个整数 $T$，表示测试组数。

对于每组测试，第一行一个整数 $n$，表示树的大小。

第二行 $n$ 个整数 $x_i$，表示树上每个点的点权。

第三行到第 $n+1$ 行，每行两个整数 $u,v$，表示树上 $u,v$ 之间有条边。

输出格式

对于每组测试，第一行一个小数 $p$，表示答案。

第二行长度为 $n$ 的 $0,1$ 串，$0$ 为该位置不种树， $1$ 为该位置种树。

样例

2
3
1 2 3
1 3
2 1
4
1 2 3 4
1 2
3 1
1 4

5.000000
011
9.000000
0111

4
14
99395960 664554897 268124438 239932020 990022138 414803993 186475819 924719063 351228272 363942841 686940432 906248275 775378951 300729898 
2 1
5 3
7 10
3 2
7 11
1 7
8 7
4 3
2 6
9 4
9 12
13 2
14 2
18
901804836 2086381 205484204 564532346 726013079 82479226 918453764 630160749 231765352 967913891 966243596 540679343 550832917 460687196 998349187 681350111 910185194 401634051 
16 7
3 2
3 13
10 14
5 1
11 6
3 4
5 6
5 7
8 2
4 9
10 6
4 12
15 3
1 2
17 6
18 13
20
437483346 454436553 866432551 236378304 208715591 881987722 236913929 230235407 695720520 365501603 723612844 16955636 467036028 212022464 942677764 465777831 950710238 362510320 373197932 765535891 
7 3
9 3
14 12
4 10
6 2
1 2
11 8
4 8
11 12
12 13
4 5
15 1
8 16
2 3
4 3
17 2
14 18
1 19
20 7
20
613953699 603982204 127024755 873851573 200098710 322519707 807793015 724462107 285588233 133305032 299911011 803457517 324224241 440191405 130344964 242108785 29120708 831631347 712641154 627233481 
10 1
2 19
5 2
4 17
1 2
2 4
2 3
6 2
4 7
8 7
9 6
11 6
12 11
13 5
14 11
15 7
5 16
18 7
5 20

5702113571.000000
10011101011111
7616388829.000000
100000111111101010
7373696315.000000
00101100011010111111
6773644735.000000
10110101000111110111

提示

对于样例 $1$ ，其最优答案为 $5$ 。

对于$100\%$的数据：$1\leq n\leq10^6\ ,\ 1\leq x_i\leq 10^9\ ,\ 1\leq u,v\leq n\ ,\ u\neq v\ ,\ T\leq 5\ ,\ \sum n\leq10^6$

若你的输出格式合法，且输出答案和方案的值均与正解的值相差小于等于 $10^{-6}$ ，该测试点为满分。

输出格式合法的情况下，若你的答案与正解相差小于等于 $10^{-6}$ ，但方案不正确，你可以获得该测试点 $60\%$ 的分数

对于每个测试点，其得分为所以测试中的最低分数