题目描述

给出一棵包含 \(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\) 的值。相邻整数之间用一个空格隔开。

由于杭电 OJ 的特性，出题人无法直接开大栈空间。如果你需要开大栈空间，例如 dfs 遍历链状的树等，可以使用内嵌汇编语句手动调整。具体来说：

int main() {
int size(256<<20);  // 256M
__asm__ ( "movq %0, %%rsp\\n"::"r"((char*)malloc(size)+size));

// your code

exit(0);
// notice
}

样例输入

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

样例输出

2 4 2 4 6