U412495 粽子树

**时间限制：** 1.0 秒 **空间限制：** 512 MB 注 : 本题最后两个数据经过了刻意设计，在原题 1.0 秒的时限下会略微卡常。但是由于原题设置如此，故此题时空限制均不做改动。我们提供以下几种卡常思路： - 使用更快的输入输出方法； - 使用访问时间常数和空间占用常数更小的存储粽子树以及粽子种类的结构； - 将搜索过程用栈进行迭代模拟，本题空间占用可以优化到空间限制的十分之一以内。

小粽有一棵粽子树。这棵树有 $n$ 个结点，编号依次为 $1$ 到 $n$ ，根节点的编号为 $n$ 。这棵树的每个点都会结出一个粽子。第 $i$ 个点的粽子种类可以用一个整数 $a_i$ 表示。 小粽没事的时候喜欢爬树玩耍。这天，小粽想到了一个问题：对于任意的点 $i$ ，如何求出 $i$ 到根节点简单路径上不同粽子的种类数呢？ 这个问题对小粽来说太难了，你能帮她算出来吗？

从标准输入读入数据。 输入第一行为一个整数，表示树的节点数目。 接下来 $n-1$ 行，每行两个整数 $u,v$ ，表示树上编号为 $u,v$ 的两点之间存在一条边。 接下来一行输入 $n$ 个整数，第 $i$ 个数为 $a_i$ ，表示编号为 $i$ 的节点上结出的粽子的种类。

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

### 数据范围 对于 $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$ 。