#P11509. [2022省队模拟]树

[2022省队模拟]树

【问题描述】

​ 一棵根为 11 的树 TT,定义一个非空点集 S⊂TS \subset T ,易证 SS 有 2n−12^{n}-1 种选法。

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

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

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

【输入格式】

​ 第一行一个整数 nn 。

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

【输出格式】

​ 输出一共 nn 行,第 ii 表示 G(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.intree/tree2.in 与 tree/tree2.anstree/tree2.ans。

【数据范围及约定】

对于所有数据有 n,Q≤105,Ai,d≤109n,Q\leq10^{5},A_{i},d\leq10^{9}

测试点 性质 分数
测试点1 n≤10n\leq 10 10
测试点2 n≤100n\leq 100
测试点3
测试点4 n≤1000n\leq 1000
测试点5
测试点6 n≤100000n\leq 100000
测试点7
测试点8
测试点9
测试点10