Submission #72942957

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
ll ksm(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b/=2;
	}
	return res;
}
int n;
set<int> S;
int deg[200005];
vector<int> V[200005];
struct edge{
	int u,v,c;
}e[200005];int tot;
void dfs(int u,int fa,int rt,int c){
	if(deg[u]!=2){
		if(rt) e[++tot]={rt,u,c};
		rt=u,c=1;
	}
	for(int v:V[u]){
		if(v==fa) continue;
		dfs(v,u,rt,c+1);
	}
}
int f[200005],sz[200005],out[200005];
int fd(int x){
	if(x==f[x]) return x;
	return f[x]=fd(f[x]);
}
void merge(int x,int y,int c){
	x=fd(x),y=fd(y);
	f[x]=y;
	sz[y]+=sz[x]+c-2;
	out[y]=out[y]+out[x]-2;
	S.erase(x);
}
ll fac[200005],Ifac[200005];
ll C(int x,int y){
	if(x<y) return 0;
	return fac[x]*Ifac[y]%mod*Ifac[x-y]%mod;
}
ll T(int x,int h){
	return (out[x]-1)*(h-1)+sz[x]-1; 
}
ll ans[200005];
void solve(){
	cin>>n;
	if(n==1){
		cout<<1<<"\n";
		return;
	}
	fac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
	Ifac[n]=ksm(fac[n],mod-2);
	for(int i=n-1;i>=0;i--) Ifac[i]=Ifac[i+1]*(i+1)%mod;
	for(int i=1;i<=n;i++) V[i].clear(),deg[i]=0;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		V[u].push_back(v);
		V[v].push_back(u);
		deg[u]++,deg[v]++;
	}
	S.clear();
	for(int i=1;i<=n;i++){
		if(deg[i]!=2){
			f[i]=i;
			sz[i]=1;
			out[i]=deg[i];
			S.insert(i);
		}
	}
	tot=0;
	dfs(*S.begin(),0,0,1);
	int pos=1;
	sort(e+1,e+1+tot,[&](edge x,edge y){
		return x.c<y.c;
	});
	for(int k=n-1;k>=1;k--){
		while(pos<=tot&&e[pos].c<n-k){
			merge(e[pos].u,e[pos].v,e[pos].c);
			pos++; 
		}
		ans[k]=C(n,k);
		for(auto x:S){
			ans[k]=ans[k]*fac[T(fd(x),n-k)]%mod;
		}
	}
	ans[n-1]=n,ans[n]=1;
	for(int k=1;k<=n;k++) cout<<ans[k]<<" ";
	cout<<"\n"; 
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin>>T;
	while(T--) solve();
} 

Submission Info

Judge Result