4F. Path Cover Matching

You are given a tree with $n$ vertices.

For each $k$ with $1 \le k \le n-1$, define $f(k)$ as follows.

You choose exactly $k$ edges of the tree and mark them. Then you construct a graph $G$ on the same $n$ vertices, where you add an edge between two distinct vertices $u$ and $v$ if and only if the unique simple path between $u$ and $v$ in the tree contains at least one marked edge.

Let $\nu(G)$ be the size of a maximum matching in $G$.
Then $f(k)$ is the maximum possible value of $\nu(G)$ over all choices of $k$ marked edges.

For each test case, output $f(1), f(2), \ldots, f(n-1)$.

Constraints

• $1 \le t \le 10^4$
• $1 \le n \le 2 \times 10^5$
• The sum of $n$ over all test cases is at most $2 \times 10^5$