A14339 | $MEX Tree$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

You are given a tree with $n$ nodes, numerated from $0$ to $n-1$ . For each $k$ between $0$ and $n$ , inclusive, you have to count the number of unordered pairs $(u,v)$ , $u \neq v$ , such that the MEX of all the node labels in the shortest path from $u$ to $v$ (including end points) is $k$ . The MEX of a sequence of integers is the smallest non-negative integer that does not belong to the sequence.

The first line contains a single integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases. The first line of each test case contains a single integer $n$ ( $2 \le n \le 2 \cdot 10^{5}$ ). The next $n-1$ lines of each test case describe the tree that has to be constructed. These lines contain two integers $u$ and $v$ ( $0 \le u,v \le n-1$ ) denoting an edge between $u$ and $v$ ( $u \neq v$ ). It is guaranteed that the given edges form a tree. It is also guaranteed that the sum of $n$ for all test cases does not exceed $2 \cdot 10^{5}$ .

For each test case, print $n+1$ integers: the number of paths in the tree, such that the MEX of all the node labels in that path is $k$ for each $k$ from $0$ to $n$ .

输入 #1

输出 #1

1 2 1 1 1 
0 0 1

C++ 编辑器

输入

输出