在到校两个小时二十分钟后，我终于开始决定写题。
我们考虑实际上这个 \(a_i\) 数组，必然与我们直接定向每一条边之后每个点的出度数组一一对应。
然后就去吃饭了好耶！
在到校四个小时四十分钟后，我终于开始继续写题。
我们再来考虑如何求出这个 \(\gcd(a_1,a_2,\cdots,a_n)=k\) 。
感觉可以考虑莫反，我们令 \(g(i)\) 表示恰好 \(\gcd\) 为 \(i\) 的方案数，\(f(i)\) 表示 \(\gcd\) 为 \(i\) 的倍数的方案数。
\[f(k)=\sum_{k|d}g(d)\\
g(k)=\sum_{k|d}\mu(\frac{d}{k})f(d)\\
\]
我们考虑 \(f(d)\) 怎么算。我们发现，实际上我们只需要满足每一棵子树中的 \(siz_u\) 加上该子树连向父亲的边的对该子树根的出度贡献是 \(d\) 的倍数，就是一种方案。
我们就直接考虑算出所有的可能的 \(d\) 的 \(f(d)\) ，然后用调和级数来计算 \(g(k)\) 就行了。
我们再来考虑可能的 \(d\) 的范围，实际上就是 \(n-1\) 的因数。我们考虑暴力枚举因数然后判断就行了吧。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int MOD=998244353;
int ADD(int x,int y){return x+y>=MOD?x+y-MOD:x+y;}
int TIME(int x,int y){return (int)(1ll*x*y%MOD);}
int n,siz[N],f[N],g[N];
struct Edge{int nxt,to;}e[N<<1];int fir[N];
void add(int u,int v,int i){e[i]=(Edge){fir[u],v},fir[u]=i;}
void dfs(int u,int fa){
siz[u]=1;
for(int i=fir[u];i;i=e[i].nxt){
int v=e[i].to;if(v==fa) continue;
dfs(v,u),siz[u]+=siz[v];
}
}
int check(int k){
int res=1;
for(int i=2;i<=n;++i)
res=TIME(res,(siz[i]%k==0)+((siz[i]-1)%k==0));
return res;
}
int mu[N];bool tag[N];
vector<int> pri;
void init(){
mu[1]=1;
for(int i=2;i<N;++i){
if(!tag[i]) pri.push_back(i),mu[i]=MOD-1;
for(int j=0;j<(int)pri.size();++j){
if(i*pri[j]>=N) break;
tag[i*pri[j]]=true;
if(i%pri[j]==0){mu[i*pri[j]]=0;break;}
else mu[i*pri[j]]=TIME(mu[i],mu[pri[j]]);
}
}
}
void solve(){
cin>>n;
for(int i=1;i<=n;++i) fir[i]=0;
for(int i=1;i<n;++i){
int u,v;scanf("%d%d",&u,&v);
add(u,v,i<<1),add(v,u,i<<1|1);
}
dfs(1,0);
for(int i=1;i<=n;++i) f[i]=0,g[i]=0;
for(int i=1;i*i<=n-1;++i){
if((n-1)%i) continue;
f[(n-1)/i]=ADD(f[(n-1)/i],check((n-1)/i));
if(i*i!=n-1) f[i]=ADD(f[i],check(i));
}
for(int i=1;i<=n;++i){
for(int j=i;j<=n;j+=i)
g[i]=ADD(g[i],TIME(mu[j/i],f[j]));
}
for(int i=1;i<=n;++i) printf("%d ",g[i]);
return printf("\n"),void();
}
int main(){
init();int T;cin>>T;
while(T--) solve();
return 0;
}