k - 路径（easy vension）
题号：NC277176
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

这是问题的简单版本。三个版本的做法之间可能有交集。

给定一颗 n 个点的无根树，每个节点有类型和权值，分别用 c 和 w 表示。一条简单路径的权值为这条路径包含的节点权值之和。

假设一条简单路径至少经过一个类型为 k 的节点，那么这条路径是 k - 路径。

对于所有的 k=1,2,3,...n，输出一个整数，表示所有 k - 路径的最大权值，假如不存在，输出 -1。

提示：本题输入输出数据量较大，建议选手使用快速的输入输出方式。

输入描述:

第一行输入一个整数 T(1\le T\le 10^4)，表示测试数据组数。接下来是 T 个测试用例。

每个测试用例第一行输入一个整数 n(1\le n\le 10^6)。

第二行有 n 个数 c_i(1\le c_i \le n)，表示每个节点的类型。

第三行有 n 个数 w_i(-10^9\le w_i\le 10^9)，表示每个节点的权值。

然后 n-1 行，每一行有两个整数 u,v，表示有一条 u 到 v 的无向边。

保证所有测试用例 n 的和不超过 10^6。

输出描述:

对于每个测试用例，输出一行，包含 n 个空格分隔的整数，表示答案。
示例1

输入

复制 
3
2
1 1
-8 5
2 1
5
5 1 3 4 1
6 6 6 9 10
3 1
4 3
1 5
2 1
4
1 4 1 3
-2 -9 8 10
2 1
1 3
4 1

输出

复制 
5 -1
31 -1 31 31 31
16 -1 16 -1

说明

在第一个测试用例中，简单路径 (2,2) 包含类型为 1 的节点，所以是一条 1 - 路径，权值为 5。简单路径 (1,2) 也包含类型为 1 的节点，权值为 -3。取最大，所以对于 k=1，输出 5。对于 k=2，没有一条路径是 2 -路径，所以输出 -1。

在第二个测试用例中，对于 k=1，简单路径 (4,5) 包含类型为 1 的节点，所以是一条 1 - 路径，权值为31，显然，没有其它任何一条 1 - 路径比这条路径权值更大。
示例2

输入

复制 
6
10
6 8 10 6 4 3 10 2 7 6
-10 5 -10 8 -5 7 -1 -7 3 2
10 3
8 1
8 6
5 6
2 9
2 10
9 7
7 1
9 4
10
10 9 8 4 1 8 4 5 1 9
-1 -9 -10 -10 1 -6 9 -8 -1 -9
9 2
3 8
2 6
10 6
4 7
2 3
5 2
1 6
7 3
10
5 3 1 1 1 5 9 10 8 5
-4 -3 4 -10 -3 -3 -2 1 -2 7
6 2
2 10
8 5
3 7
10 5
6 1
4 7
4 5
9 1
10
3 7 8 3 6 8 3 10 9 10
5 -5 8 -9 5 5 -8 3 -6 2
2 1
7 2
9 3
6 8
6 4
10 1
3 2
9 8
8 5
10
3 7 8 3 6 8 3 10 9 10
5 -5 8 -9 5 5 -8 3 -6 2
2 1
7 2
9 3
6 8
6 4
10 1
3 2
9 8
8 5
5
4 2 5 4 2
4 3 -2 -1 -3
3 1
3 2
3 5
4 1

输出

复制 
-1 0 7 2 -1 18 18 18 -1 10
1 -1 -1 9 -8 -1 -1 -1 -8 -1
5 -1 4 -1 7 -1 -1 -2 2 5
-1 -1 12 -1 -1 13 12 13 12 13
-1 -1 12 -1 -1 13 12 13 12 13
-1 5 -1 5 5