?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
230964655 |
Practice: racccccoon |
1499F - 12 | C++14 (GCC 6-32) | Accepted | 124 ms | 620 KB | 2023-11-02 14:50:43 | 2023-11-02 14:50:43 |
// LUOGU_RID: 132975308 #include<bits/stdc++.h> using namespace std; const int N=5010,M=5010; const int mod=998244353; int n,m; int dep[N],mxd[N],lev[N],son[N]; int *f[N],*now,dp[N],tmp[N]; struct edge{int to,nxt;}; edge e[2*N];int head[N],tot; void add(int u,int v) { e[++tot]={v,head[u]};head[u]=tot; } void dfs1(int u,int pa) { dep[u]=dep[pa]+1; // lev[u]=1; for(int i=head[u];i;i=e[i].nxt) { int v=e[i].to;if(v==pa)continue; dfs1(v,u); // lev[u]=max(lev[u],lev[v]+1); if(lev[v]>lev[son[u]])son[u]=v; } lev[u]=lev[son[u]]+1; } void dfs2(int u,int pa) { f[u][0]=1; if(son[u]) { f[son[u]] = f[u] + 1; dfs2(son[u],u); tmp[0]=0; for(int i=0;i<=min(lev[son[u]]-1,m);i++) { (tmp[0]+=f[son[u]][i])%=mod;//f[u][0] <- sum } f[u][0]=tmp[0]; } for(int i=head[u];i;i=e[i].nxt) { int v=e[i].to;if(v==pa||v==son[u])continue; f[v] = now;now += lev[v]; dfs2(v,u); for(int j=0;j<=min(lev[u]-1,m);j++) tmp[j]=0; for(int j=0;j<=min(lev[u]-1,m);j++) { for(int k=0;k<=min(lev[v]-1,m);k++) { (tmp[j]+=1ll*f[u][j]*f[v][k]%mod)%=mod; if(j+k+1<=m) (tmp[max(j,k+1)]+=1ll*f[u][j]*f[v][k]%mod)%=mod; } } for(int j=0;j<=min(lev[u]-1,m);j++) (f[u][j]=tmp[j])%=mod; //f[u][j] = tmp[j],而非 += 因为状态逻辑上应包含已合并的全部子结点 } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<n;i++) { int u,v;scanf("%d%d",&u,&v); add(u,v);add(v,u); } dfs1(1,0); now = dp;f[1]=now;now+=lev[1]; dfs2(1,0); int ans=0; for(int i=0;i<=min(lev[1]-1,m);i++) (ans+=f[1][i])%=mod; printf("%d\n",ans); return 0; }
?
?
?
?