【问题描述】

​ 一棵根为 $1$ 的树 $T$，定义一个非空点集 $S \subset T$ ，易证 $S$ 有 $2^{n}-1$ 种选法。

​ 定义 $LCA(S)$ 表示点集 $S$ 中所有点的最近公共祖先。

​ 定义 $G(x)=\sum_{S}[LCA(S)=x]$ ，表示点集的 LCA 为节点 $x$ 的集合个数。

​ 对于每个节点 $x$ 求出 $G(x)$

【输入格式】

​ 第一行一个整数 $n$ 。

​ 接下来 $n-1$ 行，每行两个数，表示 $u,v$ 表示一条树边。

【输出格式】

​ 输出一共 $n$ 行，第 $i$ 表示 $G(i)$。

【样例输入1】

10
2 1
3 2
4 2
5 1
6 5
7 5
8 6
9 7
10 8

【样例输出1】

953
5
1
1
53
4
2
2
1
1

【样例2】

​ 见选手目录下的 $tree/tree2.in$ 与 $tree/tree2.ans$。

【数据范围及约定】

对于所有数据有 $n,Q\leq10^{5},A_{i},d\leq10^{9}$