B. 困难的树上MEX问题
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

给定一棵包含 $$$n$$$ 个节点的有根树 $$$T$$$，根节点为 $$$1$$$。

每个节点 $$$u$$$ 都有一个初始点权 $$$w_u$$$，且序列 $$$w_1, w_2, \dots, w_n$$$ 是 $$$0, 1, \dots, n-1$$$ 的一个排列$$$^\dagger$$$。

对于树上的任意节点 $$$u$$$，定义其子树权值 $$$V(u)$$$ 为： $$$$$$V(u) = \max_{v \in T_u} \Big( \text{MEX}^\ddagger \bigl( \text{path}(u, v) \bigr) \Bigr)$$$$$$

其中：$$$T_u$$$ 表示以 $$$u$$$ 为根的子树节点集合。$$$\text{path}(u, v)$$$ 表示从节点 $$$u$$$ 到节点 $$$v$$$ 的简单路径上的所有节点权值的集合。你的任务是求出所有 $$$1 \le u \le n$$$ 对应的 $$$V(u)$$$。

$$$\ddagger\ \text{MEX}(S)$$$：表示集合 $$$S$$$ 中未出现的最小非负整数。例如：$$$\text{MEX}(\{0, 1, 3\}) = 2$$$，$$$\text{MEX}(\{1, 2\}) = 0$$$。

$$$\ddagger$$$ 排列：由 $$$0, 1, \dots, n-1$$$ 共 $$$n$$$ 个不同整数组成的序列。每个数字在序列中恰好出现一次。例如：$$$(1,2,0,3)$$$ 是排列，而 $$$(1,2,2,0,1),(1,0,4,5),(0,2)$$$ 均不是排列。

Input

第一行输入一个正整数 $$$T(1\le T\le 10^4)$$$，表示测试组数。

接下来的 $$$T$$$ 组测试中，对于每组测试，输入格式如下：

  • 第一行输入一个正整数 $$$n(1\le n\le 2\times 10^5)$$$，表示树的节点数。
  • 第二行输入 $$$n$$$ 个非负整数，$$$w_1,w_2,\dots,w_n(0\le w_i\lt n)$$$，表示每个点的权值，保证给出的一定是一个排列。
  • 接下来的 $$$n-1$$$ 行，每行输入两个正整数 $$$u,v(1\le u,v\le n,u\neq v)$$$，表示一条边，且保证给出的边一定能形成一棵树。

此外，数据保证所有测试组 $$$n$$$ 的总和不超过 $$$2\times 10^5$$$，保证给出的所有图一定是一棵树。

Output

对于每组测试组，共输出一行 $$$n$$$ 个非负整数，表示 $$$u$$$ 为根的子树下其权值大小。

Example
Input
4
5
1 0 2 3 4
1 2
2 3
3 4
4 5
5
0 1 2 3 4
1 2
2 3
3 4
4 5
5
1 0 2 4 3
1 2
2 3
1 4
4 5
6
5 0 2 1 4 3
1 2
2 3
2 4
3 5
3 6
Output
5 1 0 0 0
5 0 0 0 0
3 1 0 0 0
2 2 0 0 0 0