标签：return 50005 int Rebuild Tree long n1 mod
- 考虑\(\prod s[i]\)的组合意义：就是在每个连通块内选一个点的方案数
- 应用链式前向星存图时，应当舍弃“0-1”变换，从2号边开始编号【对于其他情况，也应尽量避免从0开始编号】
- 枚举子树大小DP是O(n^2)的，但如果有m的限制，可以证明时间复杂度降至O(nm)
- 因为出点和入点未必相同，所以不能简单地把连通块大小相乘；但相信最后的结果是美的，可以大胆猜想把m+1换成n
- 加法式枚举的好处在于，保证了两边都是合法的，避免了复杂度的错误
点击查看代码
#include <bits/stdc++.h>
using namespace std;
vector<int>a[50005];
int s[50005],n,m;
const int mod=998244353;
long long f[50005][105][2],g[105][2];
int power(int n,int p)
{
if(p==0)
{
return 1;
}
long long tmp=power(n,p/2);
if(p%2==1)
{
return tmp*tmp%mod*n%mod;
}
return tmp*tmp%mod;
}
void dp(int n1)
{
s[n1]=1;
f[n1][0][0]=1;
f[n1][0][1]=1;
for(int i=0;i<a[n1].size();i++)
{
if(!s[a[n1][i]])
{
dp(a[n1][i]);
int k=a[n1][i];
memcpy(g,f[n1],sizeof(f[n1]));
memset(f[n1],0,sizeof(f[n1]));
for(int j=0;j<=min(s[n1]-1,m);j++)
{
for(int l=0;l<=min(s[k]-1,m);l++)
{
if(j+l>m)
{
break;
}
(f[n1][j+l][0]+=(g[j][0]*f[k][l][0]%mod))%=mod;
(f[n1][j+l][1]+=(g[j][1]*f[k][l][0]%mod+g[j][0]*f[k][l][1]%mod))%=mod;
if(j+l+1<=m)
{
(f[n1][j+l+1][0]+=(g[j][0]*f[k][l][1]%mod))%=mod;
(f[n1][j+l+1][1]+=(g[j][1]*f[k][l][1]%mod))%=mod;
}
}
}
s[n1]+=s[a[n1][i]];
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
a[u].push_back(v);
a[v].push_back(u);
}
dp(1);
cout<<f[1][m][1]*power(n,m-1)%mod<<endl;
return 0;
}
标签：return,
50005,
int,
Rebuild,
Tree,
long,
n1,
mod
From： https://www.cnblogs.com/watersail/p/18446565