#P9194. [USACO23OPEN] Triples of Cows P

    ID: 10304 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>数学USACO并查集2023仙人掌圆方树

[USACO23OPEN] Triples of Cows P

题目描述

There are initially N1N-1 pairs of friends among FJ's NN cows labeled 1N1\dots N, forming a tree. The cows are leaving the farm for vacation one by one. On day ii, the ii th cow leaves the farm, and then all pairs of the ii th cow's friends still present on the farm become friends.

For each ii from 11 to NN, just before the ii th cow leaves, how many ordered triples of distinct cows (a,b,c)(a,b,c) are there such that none of a,b,ca,b,c are on vacation, aa is friends with bb, and bb is friends with cc?

输入格式

The first line contains NN.

The next N1N-1 lines contain two integers uiu_i and viv_i denoting that cows uiu_i and viv_i are initially friends.

输出格式

The answers for ii from 11 to NN on separate lines.

题目大意

题目描述

最初,农夫 John 的 NN 头编号为 1N1 \dots N 的奶牛中有 N1N-1 对朋友关系,形成一棵树。奶牛们依次离开农场去度假。在第 ii 天,第 ii 头奶牛离开农场,然后所有仍在农场中的第 ii 头奶牛的朋友之间会成为朋友。

对于每个 ii11NN,在第 ii 头奶牛离开之前,有多少个有序三元组 (a,b,c)(a, b, c) 满足以下条件:a,b,ca, b, c 均未离开农场,aabb 是朋友,且 bbcc 是朋友?

输入格式

第一行包含 NN

接下来的 N1N-1 行,每行包含两个整数 uiu_iviv_i,表示奶牛 uiu_iviv_i 最初是朋友。

输出格式

输出 NN 行,第 ii 行表示在第 ii 头奶牛离开之前的答案。

提示

对于第一个样例:

  • 在第 11 头奶牛离开之前,三元组为 (1,2,3)(1, 2, 3)(3,2,1)(3, 2, 1)
  • 在第 11 头奶牛离开后,剩下的奶牛少于 33 头,因此没有三元组。

对于第二个样例:

  • 最初,奶牛 11 与所有其他奶牛是朋友,而其他奶牛之间没有朋友关系,因此三元组为 (a,1,c)(a, 1, c),其中 a,ca, c{2,3,4}\{2, 3, 4\} 中的不同奶牛,共有 32=63 \cdot 2 = 6 个三元组。
  • 在第 11 头奶牛离开后,剩下的三头奶牛彼此都是朋友,因此三元组为这三头奶牛的任意排列,共有 3!=63! = 6 个三元组。
  • 在第 22 头奶牛离开后,剩下的奶牛少于 33 头,因此没有三元组。

2N21052 \le N \le 2 \cdot 10^51ui,viN1 \le u_i, v_i \le N

  • 输入 4-5:N500N \le 500
  • 输入 6-10:N5000N \le 5000
  • 输入 11-20:没有额外限制。
3
1 2
2 3

2
0
0

4
1 2
1 3
1 4

6
6
0
0

5
3 5
5 1
1 4
1 2

8
10
2
0
0

提示

For the first sample:
(1,2,3)(1,2,3) and (3,2,1)(3,2,1) are the triples just before cow 11 leaves.
After cow 11 leaves, there are less than 33 cows left, so no triples are possible.

For the second sample:
At the beginning, cow 11 is friends with all other cows, and no other pairs of cows are friends, so the triples are (a,1,c)(a, 1, c) where a,ca, c are different cows from {2,3,4}\{2, 3, 4\}, which gives 32=63 \cdot 2 = 6 triples.
After cow 11 leaves, the remaining three cows are all friends, so the triples are just those three cows in any of the 3!=63! = 6 possible orders.
After cow 22 leaves, there are less than 33 cows left, so no triples are possible.

2N21052\le N\le 2\cdot 10^5, 1ui,viN1\le u_i,v_i\le N.

  • Inputs 4-5: N500N\le 500.
  • Inputs 6-10: N5000N\le 5000.
  • Inputs 11-20: No additional constraints.