题目概述

有一棵树，现在要把树分成若干个级别，每个级别是若干个权值加和相等的连通块。第一个级别是所有节点，之后的级别需要满足第 $i$ 个级别中的连通块均在 $i-1$ 中连通且 $i$ 的块数必须小于 $i-1$ 。问总方案数。

解题报告

好题。假设所有点的权值和是 $S$ ，首先先分析分成 $k$ 个连通块需要满足的条件，可以发现肯定是从包含叶子且子树权值和为 $S\over k$ 的节点开始删除，重复这个过程 $k$ 次就可以判断 $k$ 是否满足。

实际上就是找 ${S\over k}|sum_x$ 的 $x$ 的个数是不是刚好为 $k$ ，如果是的，那么肯定可以从最下面的开始删除，然后逐步删除上面的。通过 $S\over(sum_x,S)$ 可以得出对于 $x$ 的最小满足的 $k$ ，通过调和级数就可以算出所有 $k$ 的出现个数。

把满足的 $k$ 都拿出来排序，那么问题变成了这样：有多少个子序列满足后一项是前一项的倍数，直接DP。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=1000000,MOD=1e9+7;

int n,w[maxn+5],fa[maxn+5],f[maxn+5],ans[maxn+5];LL sum[maxn+5];

LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
inline void AMOD (int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&w[i]),sum[i]=w[i];
    for (int i=2;i<=n;i++) scanf("%d",&fa[i]);for (int i=n;i>1;i--) sum[fa[i]]+=sum[i];
    f[1]++;for (int i=2;i<=n;i++) if ((sum[i]=sum[1]/gcd(sum[1],sum[i]))<=n) f[sum[i]]++;
    for (int i=n;i;i--) for (int j=i<<1;j<=n;j+=i) f[j]+=f[i];
    for (int i=n;i;i--) if (f[i]==i) {ans[i]=1;for (int j=i<<1;j<=n;j+=i) AMOD(ans[i],ans[j]);}
    return printf("%d\n",ans[1]),0;
}