比赛 hs的新题赛 评测结果 AAAAAAAAAA
题目名称 HS的颓废生活 最终得分 100
用户昵称 梦那边的美好ET 运行时间 8.244 s
代码语言 C++ 内存使用 19.70 MiB
提交时间 2019-04-04 11:36:25
显示代码纯文本
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<vector>
#define maxn 100010
#define LL long long 
using namespace std;
int read(){
	int x=0,ju=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')ju=-1;c=getchar();}
	while(c<='9'&&c>='0'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*ju;
}
const LL mod=998244353,g=(LL)3;
LL ksm(LL x,LL y){
	LL ans=1;
	while(y){
		if(y&1)ans=(ans*x)%mod;
		x=(x*x)%mod;y>>=1;
	}
	return ans;
}
LL f[maxn*4];
void NTT(LL *d,LL DFT,LL n){
	for(int i=0;i<n;i++)if(i<f[i])swap(d[i],d[f[i]]);
	for(int s=1;s<n;s<<=1){
		LL wn=ksm(g,(mod-1)/(s<<1));
		if(DFT==-1)wn=ksm(wn,mod-2);
		for(int i=0;i<n;i+=(s<<1)){
			LL w1=(LL)1;
			for(int j=i;j<i+s;j++){
				LL x=d[j],y=(d[j+s]*w1)%mod;
				d[j]=(x+y)%mod;d[j+s]=(x-y+mod)%mod;
				w1=(w1*wn)%mod;
			}
		}
	}
	if(DFT==-1){LL fz=ksm(n,mod-2);for(int i=0;i<n;i++)d[i]=(d[i]*fz)%mod;}
	return;
}
vector<LL>b[maxn];
LL n,k,a1,a2,ans[maxn],bk[maxn];
LL si[maxn],maxson[maxn],all,ansd;
void dfs1(int p,int fa){
	maxson[p]=0;si[p]=1;all++;
	for(int i=0;i<b[p].size();i++){
		LL x=b[p][i];if(x==fa||bk[x])continue;
		dfs1(x,p);si[p]+=si[x];
		if(si[x]>si[maxson[p]])maxson[p]=x;
	}
	return;
}
void dfs2(int p,int fa){
	for(int i=0;i<b[p].size();i++){
		LL x=b[p][i];if(x==fa||bk[x])continue;
		dfs2(x,p);
		if(si[maxson[p]]<=(all>>1)&&si[p]>=(all>>1))ansd=p;
	}
	return;
}
LL find(LL p){
	all=0;dfs1(p,0);dfs2(p,0);
	return ansd;
}
LL A[4*maxn],B[4*maxn],ma1,ma2;
LL C[4*maxn],N;
void dfs3(int p,int fa,LL le){
	B[le]++;ma2=max(le,ma2);
	for(int i=0;i<b[p].size();i++){
		LL x=b[p][i];if(x==fa||bk[x])continue;
		dfs3(x,p,le+1);
	}
	return;
}
void dfs4(int p,int fa,LL le){
	A[le]--;
	for(int i=0;i<b[p].size();i++){
		LL x=b[p][i];if(x==fa||bk[x])continue;
		dfs4(x,p,le+1);
	}
	return;
}
void solve2(LL l1,LL l2){
	N=(LL)1;while(l1+l2>=N)N*=(LL)2;
	for(int i=1;i<N;i++)f[i]=(f[i>>1]>>1)|((i&1==1)?(N>>1):0);
	NTT(A,1,N);NTT(B,1,N);
	for(int i=0;i<N;i++)C[i]=(A[i]*B[i])%mod;
	NTT(A,-1,N);NTT(B,-1,N);NTT(C,-1,N);
	return;
}
void solve(LL p){
	ma1=0;
	for(int i=0;i<b[p].size();i++){
		if(bk[b[p][i]])continue;ma2=1;
	    dfs3(b[p][i],p,(LL)1);
		solve2(ma1,ma2);
		for(int j=0;j<=min(N-1,k);j++)ans[j]=(ans[j]+C[j])%mod;
		for(int j=0;j<=min(k,N-1);j++)A[j]+=B[j];ma1=max(ma1,ma2);
		for(int j=0;j<N;j++)C[j]=B[j]=0;
	}
	bk[p]=1;
	for(int i=0;i<b[p].size();i++){
		if(bk[b[p][i]])continue;
	    dfs4(b[p][i],p,(LL)1);
	}	
	for(int i=0;i<b[p].size();i++){
		if(bk[b[p][i]])continue;
		LL q=find(b[p][i]);
		if(all==1)continue;solve(q);
	}
	return;
}
int MAIN(){
	freopen("solve.in","r",stdin);
	freopen("solve.out","w",stdout);
	n=read();k=read();
	for(int i=1;i<=n-1;i++){
		a1=read();a2=read();
		b[a1].push_back(a2);
		b[a2].push_back(a1);
	}
	A[0]=1;LL p=find(1);solve(p);
	ans[0]=n;for(int i=0;i<=k;i++)printf("%d ",ans[i]);
	return 0;
}
int hs=MAIN();
int main(){;}