比赛 |
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(){;}