You
Contest: Codeforces Round 735 (Div. 2)
Difficulty rating: 2600
Tags: dfs and similar, dp, math, number theory

You are given a tree with $$$n$$$ nodes. As a reminder, a tree is a connected undirected graph without cycles.

Let $$$a_1, a_2, \ldots, a_n$$$ be a sequence of integers. Perform the following operation exactly $$$n$$$ times:

- Select an unerased node $$$u$$$. Assign $$$a_u :=$$$ number of unerased nodes adjacent to $$$u$$$. Then, erase the node $$$u$$$ along with all edges that have it as an endpoint.

For each integer $$$k$$$ from $$$1$$$ to $$$n$$$, find the number, modulo $$$998\,244\,353$$$, of different sequences $$$a_1, a_2, \ldots, a_n$$$ that satisfy the following conditions:

- it is possible to obtain $$$a$$$ by performing the aforementioned operations exactly $$$n$$$ times in some order.
- $$$\operatorname{gcd}(a_1, a_2, \ldots, a_n) = k$$$. Here, $$$\operatorname{gcd}$$$ means the greatest common divisor of the elements in $$$a$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10\,000$$$)  — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$).

Each of the next $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$) indicating there is an edge between vertices $$$u$$$ and $$$v$$$. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, print $$$n$$$ integers in a single line, where for each $$$k$$$ from $$$1$$$ to $$$n$$$, the $$$k$$$-th integer denotes the answer when $$$\operatorname{gcd}$$$ equals to $$$k$$$.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
In the first test case,

- If we delete the nodes in order $$$1 \rightarrow 2 \rightarrow 3$$$ or $$$1 \rightarrow 3 \rightarrow 2$$$, then the obtained sequence will be $$$a = [2, 0, 0]$$$ which has $$$\operatorname{gcd}$$$ equals to $$$2$$$.
- If we delete the nodes in order $$$2 \rightarrow 1 \rightarrow 3$$$, then the obtained sequence will be $$$a = [1, 1, 0]$$$ which has $$$\operatorname{gcd}$$$ equals to $$$1$$$.
- If we delete the nodes in order $$$3 \rightarrow 1 \rightarrow 2$$$, then the obtained sequence will be $$$a = [1, 0, 1]$$$ which has $$$\operatorname{gcd}$$$ equals to $$$1$$$.
- If we delete the nodes in order $$$2 \rightarrow 3 \rightarrow 1$$$ or $$$3 \rightarrow 2 \rightarrow 1$$$, then the obtained sequence will be $$$a = [0, 1, 1]$$$ which has $$$\operatorname{gcd}$$$ equals to $$$1$$$.

Note that here we are counting the number of different sequences, not the number of different orders of deleting nodes.

Example input:
2
3
2 1
1 3
2
1 2

Example output:
3 1 0
2 0

Editorial:
Let's find which sequences of $$$a$$$ are possible to obtain by performing the mentioned operations exactly $$$n$$$ times in some order.
(Critical) Observation 1: Consider all $$$a_i = 0$$$ initially. For each edge $$$(u, v)$$$, either increase $$$a_u$$$ by $$$1$$$ (assign $$$(u, v)$$$ to $$$u$$$) or increase $$$a_v$$$ by $$$1$$$ ((assign $$$(u, v)$$$ to $$$v$$$). The final sequences are the only possible sequences that $$$a$$$ can possibly be. You can observe it by noticing that when we select a node and delete it, the existing edges adjacent to the node gets assigned to it.
Notice that, the final sequences are unique. So there are $$$2^{n - 1}$$$ distinct sequences possible. That's because there are $$$n - 1$$$ edges and for each edge $$$(u, v)$$$ we have $$$2$$$ options — either assign it to $$$u$$$ or $$$v$$$.
Now for each $$$k$$$ from $$$1$$$ to $$$n$$$, we have to find the number of sequences which has gcd equals to $$$k$$$. Instead, let's find the number of sequences such that each of its values is divisible by $$$k$$$. Let it be $$$f_k$$$.
For $$$k = 1$$$, all sequences are valid. So $$$f_1 = 2^{n - 1}$$$.
Assume $$$k > 1$$$. Let's construct a sequence $$$a$$$ such that each $$$a_i$$$ is divisible by $$$k$$$. First, root the tree at node $$$1$$$. We will build the array in a bottom-up manner. Let $$$g_u$$$ be the set of childs of $$$u$$$ and $$$p_u$$$ be the parent of $$$u$$$. Assume that we have set the values for each $$$v \in g_u$$$. Now we will set the value of $$$a_u$$$. For each edge $$$(u, v)$$$ such that $$$v \in g_u$$$, if we have assigned this edge to $$$v$$$, then do nothing, otherwise we must assign it to $$$u$$$ i.e increase $$$a_u$$$ by $$$1$$$. After we are done with all the edges,
• if $$$a_u$$$ is divisible by $$$k$$$, then we can't assign the edge $$$(p_u, u)$$$ to $$$u$$$ because $$$a_u$$$ will be increased by $$$1$$$ and as $$$a_u$$$ is divisible by $$$k$$$, $$$(a_u + 1)$$$ will not be divisible by $$$k$$$ because $$$k > 1$$$.
• if $$$a_u$$$ is not divisible by $$$k$$$, then we must assign the edge $$$(p_u, u)$$$ to $$$u$$$ and thus increasing $$$a_u$$$ by $$$1$$$. If now $$$a_u$$$ is divisible by $$$k$$$, then we are done, otherwise we can't make $$$a_u$$$ divisible by $$$k$$$. So we terminate here.
If we can successfully set the values of $$$a_i$$$ for each $$$i$$$ from $$$1$$$ to $$$n$$$, then $$$f_k$$$ will be non-zero.
Observation 2: $$$f_k$$$ for $$$k > 1$$$ is either $$$0$$$ or $$$1$$$. We can say this by observing the building process of $$$a_i$$$ that has been discussed already.
So for each $$$k$$$ from $$$1$$$ to $$$n$$$, we can find the value of $$$f_k$$$ in $$$\mathcal{O}(n)$$$ by performing a simple dfs. So all $$$f_k$$$ can be found in $$$\mathcal{O}(n^2)$$$.
Observation 3: If $$$k$$$ doesn't divide $$$n - 1$$$, then $$$f_k = 0$$$.
Proof: Notice that $$$\sum\limits_{i = 1}^{n}{a_i} = n - 1$$$. So for any integer $$$k$$$, if each $$$a_i$$$ is divisible $$$k$$$, then $$$k$$$ must divide $$$n - 1$$$. Similarly, if $$$k$$$ doesn't divide $$$n - 1$$$, then each $$$a_i$$$ will not be divisible by $$$k$$$ and $$$f_k$$$ will be $$$0$$$.
So we only have to perform a dfs when $$$k$$$ divides $$$n - 1$$$. So all $$$f_k$$$ can be found in $$$\mathcal{O}(n \cdot \sigma_0 (n - 1))$$$ where $$$\sigma_0(x)$$$ is the number of divisors of $$$x$$$.
Let $$$h_k$$$ be the number of sequences which has gcd equals to $$$k$$$. We can notice that $$$h_k = f_k - \sum\limits_{i = 2}^{\left \lfloor{\frac{n}{k}}\right \rfloor}{h_{i \cdot k}}$$$.
So we can find $$$h_k$$$ for each $$$k$$$ from $$$1$$$ to $$$n$$$ in $$$\mathcal{O}(n \cdot log(n))$$$.
Time Complexity: $$$\mathcal{O}(n \cdot \sigma_0 (n - 1) + n \cdot log(n))$$$