给定一颗$n$个节点的有根树，其中根节点为$1$号节点，第$i$号节点的颜色是$a_i$，第$i$号节点的权值为$b_i$，如果一个颜色在以$i$为根的子树中数量出现最多，那么出现数量最多的这种颜色的节点权值的最大值我们称为幸运值，那么同一颗子树内可能会有很多幸运值，因为可能会有多种颜色出现数量都是最多的。你需要求出从$1$到$n$的所有节点中，每个节点以自己为根的子树内的幸运值之和。

输入输出格式

输入格式：

• 第一行一个整数$n$，表示节点个数
• 第二行$n$个整数，第$i$个整数为$a_i$，表示第$i$个节点的颜色
• 第三行$n$个整数，第$i$个整数为$b_i$，表示第$i$个节点的权值
• 第四行到第$n+2$行，每行两个整数$x$和$y$，表示节点$x$与节点$y$之间有一条无向边

输出格式：

• 输出$n$行，每行一个整数，第$i$行的整数表示以$i$节点为根的子树内的幸运值之和

输入输出样例

输入样例1:

3
1 1 1
1 2 3
1 2
2 3

输出样例1：

3
3
3

样例1说明：

我们会发现三个节点的颜色相同，所以以$1$节点为根的子树内幸运值之和为$3$，以$2$节点为根的子树内幸运值之和为$3$，以$3$节点为根的子树内幸运值之和为$3$，都是$3$节点的权值。

测试点

| 语言 | C | C++ | Python | JAVA | | -------------- | ------ | ------ | ------ | ------ | | 每个测试点时限 | 1.0 秒 | 1.0 秒 | 1.0 秒 | 2.0 秒 | | 内存限制 | 256MB | 256MB | 256MB | 256MB | | 测试点数目 | 20 | 20 | 20 | 20 | | 测试点是否等分 | 是 | 是 | 是 | 是 |

数据范围：

• 对于前 20%的数据，满足所有节点颜色相同
• 对于前 40%的数据，满足 $n \le 5000$
• 对于 100%的数据，满足 $1 \le n \le 1*10^5，1 \le a_i \le n，1 \le b_i \le 10^9，1 \le x \le n，1 \le y \le n$