Wannafly挑战赛27 C蓝魔法师

链接Wannafly挑战赛27 C蓝魔法师

• 给出一棵树，求有多少种删边方案，使得删后的图每个连通块大小小于等于\(k\)，\(n,k\leq 2*10^3\)
• 假设我们正在考虑\(i\)这个子树，那么不和\(i\)连边的内部节点所在联通块大小是不会再发生改变了，所以我们根本不关心内部联通情况，只关心\(i\)的联通情况，因为\(i\)有可能会和父亲连边形成更大的联通块。
• 考虑\(f_{i,j}\)表示考虑子树\(i\)，过子树\(i\)的联通块大小为\(j\)的方案数。
• 这个是考试的时候设的状态，其实这个说的不太严谨，应该是\(f_{i,j}\)表示考虑子树\(i\)，当前子树\(i\)对父亲的联通块贡献\(j\)的方案数。
• 转移就是老套路了$$f_{i,u+v}=\sum f_{i,u}*f_{son,v}$$

\[f_{i,0}=\sum_{j\leq K} f_{i,j}
\]

\[f_{i,j}=0,j>K
\]

• 答案就是\(f_{1,0}\)

#include<bits/stdc++.h>

#define R register int

#define ll long long

using namespace std;

const int N=2501;

const int M=5001;

const int mod=998244353;

int n,m,u,v,cnt,tmp[N],f[N][N],g[N][N],hd[N],to[M],nt[M],sz[N];

void link(R f,R t){nt[++cnt]=hd[f],to[cnt]=t,hd[f]=cnt;}

int gi(){

    ll x=0,k=1;char c=getchar();

    while((c<'0'||c>'9')&&c!='-')c=getchar();

    if(c=='-')k=-1,c=getchar();

    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();

    return x*k;

}

void add(R &x,R y){x=(x+y>=mod?x+y-mod:x+y);}

void Dfs(R i,R fm){

	sz[i]=1,f[i][1]=1;

	for(R k=hd[i];k;k=nt[k])

		if(to[k]!=fm){

			Dfs(to[k],i);

			for(R j=1;j<=sz[i]+sz[to[k]];++j)tmp[j]=0;//f[i][j];

			for(R u=0;u<=sz[i];++u)

				for(R v=0;v<=sz[to[k]];++v)

					add(tmp[u+v],1ll*f[to[k]][v]*f[i][u]%mod);

			sz[i]+=sz[to[k]];

			for(R j=1;j<=sz[i];++j)f[i][j]=tmp[j];

		}

	f[i][0]=0;

	for(R j=1;j<=m;++j)add(f[i][0],f[i][j]);

	for(R j=m+1;j<=sz[i];++j)f[i][j]=0;

}

int main(){

	n=gi(),m=gi();

	for(R i=1;i<n;++i)

		u=gi(),v=gi(),link(u,v),link(v,u);

	Dfs(1,0),cout<<f[1][0]<<endl;

    return 0;

}