题目描述
有一课大树,这棵树非常巨大,树上有 n 个位置可以种树,对于第 i 个位置来说,在这里种的树一般来说会长成 xi 克,但如果一棵树旁边还有种有别的树,那他们就会争抢营养,这棵树会变为 cnti+1xi 克(cnti 为第 i 棵树旁边种的树的个数)。
种树人希望让种下的树的总质量最大,他希望你帮他找出一种优秀的种树的方法和其结果。
输入格式
本题有多组测试
第一行一个整数 T,表示测试组数。
对于每组测试,第一行一个整数 n,表示树的大小。
第二行 n 个整数 xi,表示树上每个点的点权。
第三行到第 n+1 行,每行两个整数 u,v,表示树上 u,v 之间有条边。
输出格式
对于每组测试,第一行一个小数 p,表示答案。
第二行长度为 n 的 0,1 串,0 为该位置不种树, 1 为该位置种树。
样例
提示
对于样例 1 ,其最优答案为 5 。
测试点编号 |
n |
特殊性质 |
1∼2 |
20 |
无 |
3∼4 |
50 |
5∼7 |
200 |
8∼11 |
2000 |
12∼15 |
2×105 |
每个节点度数小于等于10 |
16∼20 |
106 |
无 |
对于100%的数据:1≤n≤106 , 1≤xi≤109 , 1≤u,v≤n , u=v , T≤5 , ∑n≤106
若你的输出格式合法,且输出答案和方案的值均与正解的值相差小于等于 10−6 ,该测试点为满分。
输出格式合法的情况下,若你的答案与正解相差小于等于 10−6 ,但方案不正确,你可以获得该测试点 60% 的分数
对于每个测试点,其得分为所以测试中的最低分数