General
 
 
# 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
→ Source
// 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;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details