题目描述

给出一棵包含 $N$ 个节点的有根树，根节点为 $1$。初始时，每个节点 $i$ 上存放着 $A_i$ 粒沙子。

沙子具有一种向根流动的特性：你可以随时将任意节点上的 $1$ 粒沙子移动到它的直接父节点上。此操作可以进行任意次。 定义一个函数 f[u]：假设此时只有以节点 $u$ 为根的子树存在（即沙子绝对不能移出子树 $u$），在最优操作下，子树 $u$ 中所有节点的沙子数量的最小值，最大能达到多少？

你需要为每一个节点 $u\in [1,N]$ 计算出 f[u] 的值，并输出这 $N$ 个值。

• $1\le T \le 10^5$ （测试用例组数）

• $1 \le N \le 10^6$

• $0 \le A_i \le 10^9$

• 给出的是合法的树结构。

• 保证所有测试用例中 $N$ 的总和不超过 $10^6$。

输入格式

第一行包含一个整数 $T$，表示测试用例的组数。 对于每组测试用例： 第一行包含一个整数 $N$。 第二行包含 $N$ 个整数 $A_1,A_2,…,A_N$。 接下来 $N−1$ 行，每行包含两个整数 $u$ 和 $v$，表示节点 $u$ 和 $v$ 之间有一条边。

输出格式

对于每组测试用例，输出一行 $N$ 个整数，第 $i$ 个整数表示 f[i] 的值。相邻整数之间用一个空格隔开。

输入输出样例 #1

输入 #1

1
5
0 10 2 4 6
1 2
1 3
2 4
2 5

输出 #1

2 4 2 4 6