分数: 600 点
问题陈述
你得到一棵树 T 与 N 顶点:顶点 1,顶点 2, \ldots,顶点 N。 的 i第边缘 (1\leq i\lt N) 连接顶点 u_i 和 v_i.
对于顶点 u in T,定义 f(u) 如下:
- f(u)\coloneqq 顶点对的数量 v 和 w in T 满足以下两个条件:
- 顶点 w 包含在连接顶点的路径中 u 和 v.
- v\lt w.
这里,顶点 w 包含在连接顶点的路径中 u 和 v 还当 u=w or v=w.
查找以下值 f(1),f(2),\ldots,f(N).
约束
- 2\leq N\leq2\times10^5
- 1\leq u_i\leq N\ (1\leq i\leq N)
- 1\leq v_i\leq N\ (1\leq i\leq N)
- 给定的图是一棵树。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
输出
打印以下值 f(1),f(2),\ldots,f(N) 按此顺序,用空格分隔。
示例输入 1
7 1 2 2 3 2 4 4 5 4 6 6 7
示例输出 1
0 1 3 4 8 9 15
给定的树如下:

例如, f(4)=4。 确实,对于 u=4,四对 (v,w)=(1,2),(1,4),(2,4),(3,4) 满足条件。
示例输入 2
15 14 9 9 1 1 6 6 12 12 2 2 15 15 4 4 11 11 13 13 3 3 8 8 10 10 7 7 5
示例输出 2
36 29 32 29 48 37 45 37 44 42 33 36 35 57 35
给定的树如下:

的值 f(14) is 57,这是序列的反转数 (14,9,1,6,12,2,15,4,11,13,3,8,10,7,5).
示例输入 3
24 7 18 4 2 5 8 5 15 6 5 13 8 4 6 7 11 23 16 6 18 24 16 14 21 20 15 16 18 3 16 11 10 9 11 15 14 12 19 5 1 9 17 5 22 11 19
示例输出 3
20 20 41 20 21 20 28 28 43 44 36 63 40 46 34 40 59 28 53 53 66 42 62 63