Score: $600$ points

问题描述

给定一棵包含 $N$ 个顶点的树 $T$：顶点 $1$、顶点 $2$，…，顶点 $N$。第 $i$ 条边（$1\leq i < N$）连接顶点 $u_i$ 和 $v_i$。

对于树 $T$ 中的顶点 $u$，定义函数 $f(u)$ 如下：

• $f(u)\coloneqq$ 满足以下两个条件的顶点 $v$ 和 $w$ 的对数：
  • 顶点 $w$ 在连接顶点 $u$ 和 $v$ 的路径上。
  • $v < w$。

这里，当 $u=w$ 或者 $v=w$ 时，顶点 $w$ 也被认为是在连接顶点 $u$ 和 $v$ 的路径上。

求解 $f(1)$、$f(2)$，…，$f(N)$ 的值。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given a tree $T$ with $N$ vertices: vertex $1$, vertex $2$, $\ldots$, vertex $N$. The $i$-th edge $(1\leq i\lt N)$ connects vertices $u_i$ and $v_i$.

For a vertex $u$ in $T$, define $f(u)$ as follows:

• $f(u)\coloneqq$ The number of pairs of vertices $v$ and $w$ in $T$ that satisfy the following two conditions:
  • Vertex $w$ is contained in the path connecting vertices $u$ and $v$.
  • $v\lt w$.

Here, vertex $w$ is contained in the path connecting vertices $u$ and $v$ also when $u=w$ or $v=w$.

Find the values of $f(1),f(2),\ldots,f(N)$.

Constraints

• $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)$
• The given graph is a tree.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$

$u_1$ $v_1$

$u_2$ $v_2$

$\vdots$

$u_{N-1}$ $v_{N-1}$

Output

Print the values of $f(1),f(2),\ldots,f(N)$ in this order, separated by spaces.

Sample Input 1

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

Sample Output 1

0 1 3 4 8 9 15

The given tree is as follows:

For example, $f(4)=4$. Indeed, for $u=4$, four pairs $(v,w)=(1,2),(1,4),(2,4),(3,4)$ satisfy the conditions.

Sample Input 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

Sample Output 2

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

The given tree is as follows:

The value of $f(14)$ is $57$, which is the inversion number of the sequence $(14,9,1,6,12,2,15,4,11,13,3,8,10,7,5)$.

Sample Input 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

Sample Output 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

update @ 2024/3/10 01:28:42