#PU1334. USACO 2023 US Open Contest, Platinum — Problem 3. Triples of Cows

    ID: 1647 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:open23来源:usaco.orgscoring:equal_test_cases树上算法倍增分块

USACO 2023 US Open Contest, Platinum — Problem 3. Triples of Cows

USACO 2023 US Open Contest, Platinum — Problem 3. Triples of Cows

题目描述

There are initially N−1N-1 pairs of friends among FJ's NN (2≤N≤2⋅1052\le N\le 2\cdot 10^5) cows labeled 1…N1\dots N, forming a tree. The cows are leaving the farm for vacation one by one. On day ii, the iith cow leaves the farm, and then all pairs of the iith cow's friends still present on the farm become friends. For each ii from 11 to NN, just before the iith 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 N−1N-1 lines contain two integers uiu_i and viv_i denoting that cows uiu_i and viv_i are initially friends (1≤ui,vi≤N1\le u_i,v_i\le N).

输出格式

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

数据范围

Inputs 4-5: N≤500N\le 500 Inputs 6-10: N≤5000N\le 5000 Inputs 11-20: No additional constraints. Problem credits: Aryansh Shrivastava, Benjamin Qi

样例

样例 1

3
1 2
2 3
2
0
0
$(1,2,3)$ and $(3,2,1)$ are the triples just before cow $1$ leaves.
After cow
$1$ leaves, there are less than $3$ cows left, so no triples are possible.

样例 2

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

样例 3

5
3 5
5 1
1 4
1 2
8
10
2
0
0