在一棵有根树中，边有两种：虚边和实边。一个点最多和一个儿子之间有实边。
当我们执行 Access(x) 时，首先会把 x 到根这条路径上的所有点的实边全变成虚边，然后把这条路径上的所有边全变成实边。
有一棵 $n$ 个点、以 $1$ 为根的有根树，一开始所有边都是虚边。你可以进行最多 $k$ 次任意的 access 操作，求树有可能的形态数目。
Sol
什么？？树形dp的效率是O(nk)的？？！！
考虑dp.
f[i][j]表示以i为根的子树进行了j次有效的access。
那么有树形dp的时候g[i][j][0/1]表示前i棵子树，进行了j次有效的access，否/是 选出了一条v->k的实边。
g[i][j+x][0]=f[v][x]*g[i-1][j][0]
g[i][j+x][1]=f[v][x]*g[i-1][j][1]
这两种相当于v不连上去
g[i][j+x][1]=g[i-1][j][0]*(f[v][x]+(x==1))
相当于我选择v连上去。但是如果x==1，那么f[v][1]少包括了只 access v 的情况所以要加1。
#include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> #define maxn 10005 #define ll long long #define mod 998244353 using namespace std; int n,m,head[maxn],tot,t[maxn],cnt,sz[maxn]; ll f[maxn][505],g[maxn][505][2]; struct node{ int v,nex; }e[maxn*2]; void add(int t1,int t2){ e[++tot].v=t2;e[tot].nex=head[t1];head[t1]=tot; } void dp(int k,int fa){ sz[k]=1; for(int i=head[k];i;i=e[i].nex){ if(e[i].v^fa)dp(e[i].v,k),sz[k]+=sz[e[i].v]; } cnt=0; for(int i=head[k];i;i=e[i].nex){ if(e[i].v^fa)t[++cnt]=e[i].v; } g[0][0][0]=1;int Sum=0; for(int i=1;i<=cnt;i++){ for(int j=0;j<=Sum&&j<=m;j++){ for(int x=0;x<=sz[t[i]]&&x+j<=m;x++){ (g[i][j+x][0]+=g[i-1][j][0]*f[t[i]][x]%mod)%=mod; (g[i][j+x][1]+=g[i-1][j][1]*f[t[i]][x]%mod)%=mod; if(x)(g[i][j+x][1]+=g[i-1][j][0]*(f[t[i]][x]+(x==1))%mod)%=mod; } } Sum+=sz[t[i]]; } f[k][0]=1; for(int i=1;i<=sz[k]&&i<=m;i++){ f[k][i]=g[cnt][i][1]; if(i>1)(f[k][i]+=g[cnt][i-1][0])%=mod; } Sum=0; for(int i=1;i<=cnt;i++){ Sum+=sz[t[i]];for(int j=0;j<=Sum&&j<=m;j++)g[i][j][0]=g[i][j][1]=0; } } int main(){ cin>>n>>m; for(int i=1,t1,t2;i<n;i++){ scanf("%d%d",&t1,&t2); add(t1,t2);add(t2,t1); } dp(1,0); ll ans=0; for(int i=1;i<=m;i++)ans=(ans+f[1][i])%mod; cout<<ans+1<<endl; return 0; }
原文：https://www.cnblogs.com/liankewei/p/12388281.html
如果您也喜欢它,动动您的小指点个赞吧
602392714
清零编程群