CF1527D.MEX Tree

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.

给你一棵包含 $n$ 个节点的树，节点编号从 $0$ 到 $n-1$。对于每个在 $0$ 到 $n$（含）之间的整数 $k$，你需要计算满足以下条件的无序对 $(u,v)$（其中 $u \neq v$）的数目：从 $u$ 到 $v$ 的最短路径（包含端点）上所有节点标签所构成序列的 MEX 值恰好为 $k$。

一个整数序列的 MEX（minimum excluded value）是指不属于该序列的最小非负整数。

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}$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^{5}$）。

每个测试用例的接下来 $n-1$ 行描述了需要构建的树。每行包含两个整数 $u$ 和 $v$（$0 \le u,v \le n-1$），表示节点 $u$ 与 $v$ 之间存在一条边（$u \neq v$）。

保证所给的边构成一棵树。

还保证所有测试用例的 $n$ 值之和不超过 $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$.

对于每个测试用例，输出 $n+1$ 个整数：对于每个从 $0$ 到 $n$ 的 $k$，输出树中满足该路径上所有节点标签的 MEX 值恰好为 $k$ 的路径数量。

1. In example case $1$,

   • For $k = 0$, there is $1$ path that is from $2$ to $3$ as $MEX([2, 3]) = 0$.
   • For $k = 1$, there are $2$ paths that is from $0$ to $2$ as $MEX([0, 2]) = 1$ and $0$ to $3$ as $MEX([0, 2, 3]) = 1$.
   • For $k = 2$, there is $1$ path that is from $0$ to $1$ as $MEX([0, 1]) = 2$.
   • For $k = 3$, there is $1$ path that is from $1$ to $2$ as $MEX([1, 0, 2]) = 3$
   • For $k = 4$, there is $1$ path that is from $1$ to $3$ as $MEX([1, 0, 2, 3]) = 4$.

2. In example case $2$,

   • For $k = 0$, there are no such paths.
   • For $k = 1$, there are no such paths.
   • For $k = 2$, there is $1$ path that is from $0$ to $1$ as $MEX([0, 1]) = 2$.

3. 在样例 1 中，

   • 当 $k = 0$ 时，存在 $1$ 条路径：从节点 $2$ 到节点 $3$，因为 $MEX([2, 3]) = 0$。
   • 当 $k = 1$ 时，存在 $2$ 条路径：从节点 $0$ 到节点 $2$，因为 $MEX([0, 2]) = 1$；以及从节点 $0$ 到节点 $3$，因为 $MEX([0, 2, 3]) = 1$。
   • 当 $k = 2$ 时，存在 $1$ 条路径：从节点 $0$ 到节点 $1$，因为 $MEX([0, 1]) = 2$。
   • 当 $k = 3$ 时，存在 $1$ 条路径：从节点 $1$ 到节点 $2$，因为 $MEX([1, 0, 2]) = 3$。
   • 当 $k = 4$ 时，存在 $1$ 条路径：从节点 $1$ 到节点 $3$，因为 $MEX([1, 0, 2, 3]) = 4$。

4. 在样例 2 中，

   • 当 $k = 0$ 时，不存在满足条件的路径。
   • 当 $k = 1$ 时，不存在满足条件的路径。
   • 当 $k = 2$ 时，存在 $1$ 条路径：从节点 $0$ 到节点 $1$，因为 $MEX([0, 1]) = 2$。