← 返回题目列表

AtCoder · abc337_g

G. 树反转

中文机器翻译题面 查看原题

分数: 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