You

题意翻译

### 题目描述 给你一个 $n$ 个点的树，可以通过以下方式生成一个长度为 $n$ 的序列 $a$： + 每次在树中选取一个**未被标记**的节点 $u$，令 $a_u$ 等于与节点 $u$ 相邻的**未被标记**的节点个数，然后将节点 $u$ **标记**。 对于每一个整数 $k\in[1,n]$，输出符合以下条件的序列 $a$ 的数量模 $998244353$ 的值： + 序列 $a$ 可以由给定的树通过上述方式生成； + $\gcd(a_1,a_2,\cdots,a_n)=k$。 ### 输入格式 第一行一个整数 $T$ 表示数据组数。 对于每组数据，第一行一个整数 $n$。 接下来 $n-1$ 行，每行两个整数 $u,v$，表示一条树上的边。 ### 输出格式 对于每组数据，第一行输出 $n$ 个数，第 $i$ 个数表示当 $k=i$ 时的答案。每个数之间输出一个空格，每组数据之间输出一个换行。 ### 数据范围 对于 $100\%$ 的数据，$1\leq t\leq 10^4,2\leq n\leq 10^5,\sum n \leq 3\times10^5$。

题目描述

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

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

2
3
2 1
1 3
2
1 2

输出样例 #1

3 1 0
2 0

说明

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.