Tree Inversion

题目描述

给定一棵有 $N$ 个顶点的树 $T$：顶点 $1$、顶点 $2$、$\ldots$、顶点 $N$。 第 $i$ 条边 $(1\leq i\lt N)$ 连接顶点 $u_i$ 和 $v_i$。 对于树中顶点 $u$，定义 $f(u)$ 如下：

$f(u)\coloneqq$ 满足下列两个条件的顶点对 $v$ 和 $w$ 的数量： 顶点 $w$ 包含在连接顶点 $u$ 和 $v$ 的路径上。 $v\lt w$。

在此，当 $u=w$ 或 $v=w$ 时，也视为顶点 $w$ 包含在连接顶点 $u$ 和 $v$ 的路径上。 求 $f(1),f(2),\ldots,f(N)$ 的值。

输入格式

输入给出自标准输入，格式如下： $N$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_{N-1}$ $v_{N-1}$

输出格式

按此顺序输出 $f(1),f(2),\ldots,f(N)$ 的值，使用空格分隔。

7
1 2
2 3
2 4
4 5
4 6
6 7

0 1 3 4 8 9 15

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

36 29 32 29 48 37 45 37 44 42 33 36 35 57 35

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

20 20 41 20 21 20 28 28 43 44 36 63 40 46 34 40 59 28 53 53 66 42 62 63

提示

$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)$ 给定的图是树。 所有输入值均为整数。给定的树如下所示： 例如，$f(4)=4$。 确实，对于 $u=4$，四个对 $(v,w)=(1,2),(1,4),(2,4),(3,4)$ 满足条件。
给定的树如下所示： $f(14)$ 的值为 $57$，它是序列 $(14,9,1,6,12,2,15,4,11,13,3,8,10,7,5)$ 的逆序数。

标签: AtCoder|abc337G

来源

AtCoder|abc337G