时间限制： 1.0 秒 2.0 秒

空间限制： 512 MB

题目描述

小粽有一棵粽子树。这棵树有 $n$ 个结点，编号依次为 $1$ 到 $n$，根节点的编号为 $n$。这棵树的每个点都会结出一个粽子。第 $i$ 个点的粽子种类可以用一个整数 $a_i$ 表示。

小粽没事的时候喜欢爬树玩耍。这天，小粽想到了一个问题：对于任意的点 $i$，如何求出 $i$ 到根节点简单路径上不同粽子的种类数呢？

这个问题对小粽来说太难了，你能帮她算出来吗？

输入格式

从标准输入读入数据。

输入第一行为一个整数，表示树的节点数目。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示树上编号为 $u,v$ 的两点之间存在一条边。

接下来一行输入 $n$ 个整数，第 $i$ 个数为 $a_i$，表示编号为 $i$ 的节点上结出的粽子的种类。

输出格式

输出到标准输出。

输出一行，包含 $n$ 个正整数，第 $i$ 个数表示编号为 $i$ 的点到根的路径上不同粽子的种类数。相邻两个数之间用一个空格分隔。

3
3 1
3 2
1 2 1

1 2 1

子任务

对于 $20\%$ 的数据，$1\le n\le 10^2, 1\le a_i\le 10^2$。

对于 $50\%$ 的数据，$1\le n \le 10^3,1\le a_i\le 10^3$。

对于 $80\%$ 的数据，$1\le n\le 10^5,1\le a_i\le 10^5$。

对于 $100\%$ 的数据，$1\le n\le 10^6,-2147483648\le a_i\le 2147483647$。