md今天一直在调bug，不想调了
（1）根号分治
方法一：观察转移方程，对于不同规模选择不同转移方式
#include<bits/stdc++.h>
using namespace std;
long long n,p,m,dp[100005],g[405][100005],ans;
int main()
{
scanf("%lld%lld",&n,&p);
m=sqrt(n);
dp[0]=1;
for(int i=1;i<m;i++)
{
for(int j=0;j<=n;j++)
{
if(j-i>=0) dp[j]+=dp[j-i];
dp[j]%=p;
}
}
// cout<<dp[2]<<endl;
g[0][0]=1;
for(int i=1;i<=n/m;i++)
{
for(int j=1;j<=n;j++)
{
if(j>=m) g[i][j]+=g[i-1][j-m];
if(j>=i) g[i][j]+=g[i][j-i];
g[i][j]%=p;
}
}
for(int i=1;i<=n/m;i++)
{
for(int j=0;j<=n;j++)
{
// cout<<i<<" "<<j<<": "<<g[i][j]<<endl;
g[i][j]+=g[i-1][j];
g[i][j]%=p;
}
}
for(int i=0;i<=n;i++)
{
ans+=dp[i]*g[n/m][n-i];
ans%=p;
}
cout<<ans;
return 0;
}
方法二：观察答案和大小变化
观察到当k>=sqrt(n)时答案只有sqrt(n)个，对应的k却有很多，当k<sqrt(n)同理，k少ans多
所以k小就直接算，k大就二分算每一个答案对应多少个k
#include<bits/stdc++.h>
using namespace std;
int n,uu,vv,T,ans[100005],li[100005],mson[100005][2],l,ll,rr,mid,dfn[100005],cnt,fa[100005];
vector<int> G[100005];
void dfs(int x,int f)
{
cnt++;
dfn[x]=cnt;
fa[dfn[x]]=dfn[f];
// li[x]=1;
// mson[x][0]=mson[x][1]=0;
for(int i=0;i<G[x].size();i++)
{
if(G[x][i]!=f)
{
dfs(G[x][i],x);
// if(li[G[x][i]]!=sum)
// {
// if(li[G[x][i]]>mson[x][1]) mson[x][1]=li[G[x][i]];
// if(mson[x][1]>mson[x][0]) swap(mson[x][1],mson[x][0]);
// }
}
}
// if(li[x]+mson[x][0]+mson[x][1]>=sum)
// {
// li[x]=0;
// ans[sum]++;
// }
// else
// {
// li[x]+=mson[x][0];
// }
return ;
}
void work(int sum)
{
for(int j=1;j<=cnt;j++) mson[j][0]=mson[j][1]=li[j]=0;
for(int j=cnt;j>=1;j--)
{
li[j]=1;
if(li[j]+mson[j][0]+mson[j][1]>=sum)
{
li[j]=0;
ans[sum]++;
}
else
{
li[j]+=mson[j][0];
}
if(li[j]!=sum)
{
if(li[j]>mson[fa[j]][1]) mson[fa[j]][1]=li[j];
if(mson[fa[j]][1]>mson[fa[j]][0]) swap(mson[fa[j]][1],mson[fa[j]][0]);
}
}
return ;
}
int main()
{
cin>>n;
T=sqrt(n*log(n));
T=min(T,n);
// T=0;
for(int i=1;i<=n-1;i++)
{
scanf("%d%d",&uu,&vv);
G[uu].push_back(vv);
G[vv].push_back(uu);
}
dfs(1,0);
for(int i=1;i<=T;i++)
{
work(i);
}
// dfs(1,0,2);
// cout<<ans[2]<<endl;
l=T+1;
while(l<=n)
{
if(ans[l]==0)
{
work(l);
}
// cout<<l<<": "<<ans[l]<<endl;
ll=l,rr=n;
while(ll<rr)
{
mid=(ll+rr)/2+1;
// cout<<mid<<endl;
if(ans[mid]==0)
{
work(mid);
}
if(ans[mid]==ans[l]) ll=mid;
else rr=mid-1;
}
for(int i=l;i<=ll;i++) ans[i]=ans[l];
l=ll+1;
}
for(int i=1;i<=n;i++)
{
printf("%d\n",ans[i]);
}
return 0;
}