← 返回题目列表

AtCoder · ttpc2019_m

M. 树的逆序数

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

配点 : 100 点

問題文

1 减去 N 有 N 有一个包含 个顶点的树。 i 第一条边是顶点 A_i 与边缘 B_i 。

对这棵树的顶点 r 当以 为根时,倒置数定义如下。

  • 頂点 r 到顶点 u 简单路径的端点或边上包含顶点 v 的组合 (u, v) \ (u \lt v) 的个数

1 以上 N 以下所有整数 请回答以下有关 r ,顶点 r 求以 为根时的倒置数。

制約

  • 所有输入均为整数
  • 2 \leq N \leq 10^{5}
  • 1 \leq A_i, B_i \leq N
  • 给定的图是一棵树。

入力

输入是按以下格式从标准输入给出的。

N
A_1 B_1
\vdots
A_{N-1} B_{N-1}

出力

N 行。i 顶点在行中 它表明 i 输出以 为根时的倒置数。


入力例 1

3
1 3
2 3

出力例 1

1
2
2
  • 頂点 1 以 为根时的倒置数为(u, v) = (2, 3) 捻 1 是
  • 頂点 2 以 为根时的倒置数为(u, v) = (1, 2), (1, 3) 捻 2 是
  • 頂点 3 以 为根时的倒置数为(u, v) = (1, 3), (2, 3) 捻 2 。

入力例 2

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

出力例 2

2
3
4
3
7
7
9