很妙的性质题！全是意识流证明见过吗？
problem
每次选一个非空边集删掉，谓之曰砍树。砍树后需要满足每个连通块的点权和相同。
在一个方案中可以砍很多次树，都要满足砍树后的要求。一共有多少种合法方案呢？
\(n\leq 10^6,1\leq a_i\leq 10^9\)。
solution
假如我们将树砍成 \(k\) 个连通块，我们发掘一些性质：
- 砍树方案唯一。证明：
- 这是棵树。
- 点权非负。
- 记所有点权和为 \(S\)，则有 \(k\) 个连通块的和为 \(S/k\)。（这变相要求了 \(k|S\)）。
- 如果再砍一刀，砍完后的 \(k'|k\)，可以看作每个连通块独立。
考虑求出 \(f(k)\) 表示砍成 \(k\) 个连通块是不是可能的。
考虑一种贪心：从底向上，维护子树大小，如果碰到 \(siz_u=S/k\) 马上砍了，然后 \(u\) 到根的路径集体减 \(siz_u\)。
猜测结论：只有恰好 \(k\) 个 \(\frac{S}{k}|siz_u\) 才说 \(f(k)=true\)。
证明
- 每个点唯一的包含在一个连通块中。
- 若一个点 \(u\) 满足 \(\frac{S}{k}|siz_u\)，且 \(f(k)=true\)，则子树 \(u\) 必然分成了 \(siz_u/\frac{S}{k}\) 份连通块才是正确的。请记住，点权非负。
- 考虑点 \(u\) 在一个连通块中是吧，我们令 \(\Sigma=\frac{S}{k}\)，则一个 \(siz_u\) 可以看作是包含点 \(u\) 一个 \(\Sigma\) 和其它所有儿子满足 \(\Sigma|siz_v\) 的和。
- 它的本质是，每一个连通块只会算一次，刚好算了 \(k\) 次。
啊这个结论很强，但我们还是不会快速求 \(f(k)\) 呢，考虑把它变成 \(\frac{S}{\gcd(S,siz_u)}|k\)。
过程
方法一
令 \(a=\frac{S}{k}\)。
显然有 \(a|siz_u,a|S\Rightarrow a|\gcd(siz_u,S)\)。
\(\therefore \frac{S}{k}|\gcd(siz_u,S)\Rightarrow \frac{S}{\gcd(S,siz_u)}|k\)。
方法二
\(\frac{S}{k}|siz_u\Rightarrow \frac{S}{siz_u}|k\)。
令 \(d=\gcd(S,siz_u)\)，则分数化简 \(\frac{S/d}{siz_u/d}|k\)。
现在左边这东西不是整数，考虑整除本质 \(x\frac{S/d}{siz_u/d}=k\)。
\(\because k\in N^+,\therefore siz_u/d|x\)，这样才能约分成整数。
考虑去掉 \(x\) 的这一部分，即 \(\frac{S\cdot siz_u/d}{siz_u}|k\Rightarrow \frac{S}{\gcd(S,siz_u)}|k\)。
喵喵喵，这样我们求出 \(\frac{S}{\gcd(S,siz_u)}\) 然后枚举倍数就行了。
考虑砍了很多次之后砍成 \(k\) 个连通块的方案数：\(g_k=f(k)+\sum_{j|k,j\neq k}g_j\)。
做完了。
code
点击查看代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
const int P=1e9+7;
void red(LL&x){x=(x%P+P)%P;}
LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
int n,fa[1000010];
LL f[1000010],siz[1000010],g[1000010],ans=0;
int main(){
freopen("xiongaktenioi.out","w",stdout);
// #ifdef LOCAL
freopen("xiongaktenioi.in","r",stdin);
// #endif
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&siz[i]);
for(int i=2;i<=n;i++) scanf("%d",&fa[i]);
for(int i=n;i>=2;i--) siz[fa[i]]+=siz[i];
for(int i=1;i<=n;i++){
LL w=siz[1]/gcd(siz[i],siz[1]);
debug("siz[%d]=%lld,w=%lld\n",i,siz[i],w);
for(LL j=w;j<=n;j+=w) f[j]++;
}
for(int i=n;i>=2;i--){
if(f[i]==i){
g[i]=1;
for(int j=i+i;j<=n;j+=i) red(g[i]+=g[j]);
red(ans+=g[i]);
debug("g[%d]=%lld\n",i,g[i]);
}
}
printf("%lld\n",ans+1);
return 0;
}