最后,小 与他的女神一起来到了一片神秘丛林中。丛林的结构是一颗树型结构,他们想要探寻丛林的秘密。
丛林中有 个宝藏,每个宝藏有一个种类 ,定义一条路径 的宝藏数量 为在 的简单路径上不同的 个数。
例如:若经过的 可以写成 ,那么其宝藏数量为 。
女神想知道,对于每个点 ,求出 。
第一行包含一个整数 。第二行有 个整数,表示 。接下来 行,每行 ,描述树上的一条边。
第一行包含一个整数 。
第二行有 个整数,表示 。
接下来 行,每行 ,描述树上的一条边。
输出共 行,每行输出一个整数表示当前点为 的答案。
5 2 2 1 3 4 3 2 1 5 3 1 4 1
9 11 11 12 12
。