距离询问

一棵以 $1$ 为根的有根树，对于每个点 $x$，都有一个询问 $query[x]$ ，询问 $x$ 子树中有多少个点到 $x$ 的距离为 $query[x]$，点数不超过 $10^6$。

输入

第一行，$n$ 表示此树的结点数，结点编号从 $1$ 到 $n$ ，接下来 $n - 1$ 行，每行两个数 $u ,v$，表示结点 $u$ 与 $v$ 之间有无向边连接。 接下来下 $n$ 行，第 $i$ 行表示结点 $i$ 为根的子树中要查询的 $query[x]$。

输出

$n$ 行， 第 $i$ 行表示结点 $i$ 为根的子树的查询结果。

样例

3
1 2
1 3
1
1
1

2
0
0

Limitation

1s, 1024KiB for each test case.