CF2222G.Statistics on Tree

Nanatsukaze - Aria

You are given a tree of $n$ vertices. We define the value of a pair $(u,v)$ ($1\leq u\leq v\leq n$) as the size of the largest component after removing all edges on the path from $u$ to $v$ in the original tree.

For every $1\leq i\leq n$, you have to find the number of pairs $(u,v)$ satisfying that its value is $i$.

Nanatsukaze - Aria

给你一棵包含 $n$ 个顶点的树。我们定义一对顶点 $(u,v)$（其中 $1\leq u\leq v\leq n$）的值为：在原树中删去从 $u$ 到 $v$ 的路径上的所有边后，所得图中最大连通分量的大小。

对每个 $1\leq i\leq n$，你需要求出满足其值恰好为 $i$ 的顶点对 $(u,v)$ 的数量。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1\leq n \leq 10^5$) — the number of vertices.

Then $n-1$ lines follow, the $i$-th line containing two integers $u$ and $v$ ($1\leq u,v\leq n$) — the two vertices that the $i$-th edge connects.

It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5\cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1\leq n \leq 10^5$）——顶点的数量。

接下来是 $n-1$ 行，其中第 $i$ 行包含两个整数 $u$ 和 $v$（$1\leq u,v\leq n$）——表示第 $i$ 条边所连接的两个顶点。

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

保证所有测试用例的 $n$ 之和不超过 $5\cdot 10^5$。

For each test case, output $n$ integers, the $i$-th of which denotes the number of distinct pairs $(u,v)$ satisfying its value is $i$.

对于每个测试用例，输出 $n$ 个整数，其中第 $i$ 个整数表示满足其值为 $i$ 的不同数对 $(u,v)$ 的数量。

In the first test case, the value of pair $(1, 1)$ is $1$.

In the second test case, the values of pairs $(1, 1)$ and $(2, 2)$ are both $2$, because no edges will be removed. The value of pair $(1, 2)$ is $1$, because edge $(1, 2)$ is on the path from $1$ to $2$ in the tree, and after removing it, there will be $2$ components left, which are ${1}$ and ${2}$, and the size of the largest component is $1$.

In the sixth test case, the value of pair $(4, 6)$ is $3$, because edges $(3, 4)$, $(2, 3)$, and $(2, 6)$ are on the path from $4$ to $6$ in the tree, and after removing them, there will be $4$ components left, which are ${1, 2, 5}$, ${3, 7}$, ${4}$, and ${6}$, and the size of the largest component is $3$.

在第一个测试用例中，数对 $(1, 1)$ 的值为 $1$。

在第二个测试用例中，数对 $(1, 1)$ 和 $(2, 2)$ 的值均为 $2$，因为不会删除任何边。数对 $(1, 2)$ 的值为 $1$，因为在树中从节点 $1$ 到节点 $2$ 的路径上包含边 $(1, 2)$，删除该边后将剩下 $2$ 个连通分量，即 $\{1\}$ 和 $\{2\}$，其中最大连通分量的大小为 $1$。

在第六个测试用例中，数对 $(4, 6)$ 的值为 $3$，因为在树中从节点 $4$ 到节点 $6$ 的路径上包含边 $(3, 4)$、$(2, 3)$ 和 $(2, 6)$，删除这三条边后将剩下 $4$ 个连通分量，即 $\{1, 2, 5\}$、$\{3, 7\}$、$\{4\}$ 和 $\{6\}$，其中最大连通分量的大小为 $3$。