寻找宝藏
题号:NC219484
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 1024 M,其他语言2048 M
64bit IO Format: %lld

题目描述

最后,小  与他的女神一起来到了一片神秘丛林中。丛林的结构是一颗树型结构,他们想要探寻丛林的秘密。

丛林中有  个宝藏,每个宝藏有一个种类  ,定义一条路径  的宝藏数量  为在  的简单路径上不同的  个数。

例如:若经过的  可以写成  ,那么其宝藏数量为  。

女神想知道,对于每个点  ,求出  。

输入描述:

第一行包含一个整数  。

第二行有  个整数,表示  。

接下来  行,每行  ,描述树上的一条边。

输出描述:

输出共  行,每行输出一个整数表示当前点为  的答案。
示例1

输入

复制
5
2 2 1 3 4
3 2
1 5
3 1
4 1

输出

复制
9
11
11
12
12

备注:

 。