题目描述

给出一棵包含 $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, \dots, A_N$。
• 接下来 $N-1$ 行，每行包含两个整数 $u$ 和 $v$，表示节点 $u$ 和 $v$ 之间有一条边。

输出格式

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

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

2 4 2 4 6