CF1034C Region Separation

好题啊

我们先考虑只进行一次操作，可以发现如果这次操作希望把整个树分成 $k$ 份，那么要么不可分，要么只有一种方案。

怎么证明？首先可以钦定 1 为根。如果希望把整个树分成 $k$ 份，那么每个联通块的大小必然是 $\frac S k$，其中 $S$ 是整个树的权值的和。然后很显然的，每个断开当前点和它父亲的边的必要条件是 $s_u \equiv 0 \pmod {\frac S k}$ 。但是，假设它的子树内已经有很多点被断开了，那么对于这个点所在的联通块大小，必然满足 $\frac S k | x$ 其中 $x$ 是这个点所在的联通块大小。既然如此，我们有 $x \ge \frac S k$ 。由此可以看出满足 $s_u \equiv 0 \pmod {\frac S k}$ 的点的个数是不超过 $k$ 个的。如果超过了 $k$ 个，必然在分某个点的时候没有 $x \ge \frac S k$。（其实可以感性理解一下w）

我们设

$f[k] = \displaystyle \sum_{x=1}^n [s_x\equiv 0 \pmod {\frac{S}{k}}]$

那么如果 $f[k] = k$ 则表示第一次操作分成 $k$ 是合法的。我们只需要给所有满足条件的点到父亲的边 cut 掉就行了。

如何计算 $f$ ？考虑如果一个 $s_i$ 会对 $f[k]$ 造成贡献，那么有

$s_i \equiv 0 \pmod {\frac S k}\\s_i = a \frac{S}{k} ,a\in \N^*\\k = a\frac{S}{s_i}$

我们设 $t = \frac{S}{k}$ ，那么

$s_i = at,k = \frac{S}{t}$

也就是说如果有 $t | s_i , t|S$，即 $t|\gcd(s_i,S)$，那么 $s_i$ 就会对 $\frac S t$ 造成贡献。

即若 $\frac{S}{k}|\gcd(s_i,S)$ ，即 $\frac{S}{\gcd(s_i,S)} | k$ ，则 $s_i$ 会对 $k$ 造成贡献。于是只需要对于 $s_i$ 扫一遍 $\frac S {\gcd(s_i,S)}$ 的倍数就好辣。也就是说求出 $f$ 的复杂度是 $O(n\ln n)$。

我们设最后一次剖分时剖分为 $k$ 份的方案数量是 $F[k]$ ，显然，如果上一次剖分为 $k_{i-1}$ 份，这次是 $k_i$ 份，那么必须满足 $k_{i-1} | k_i$ 。而方案又要么是 1 要么是 0 ，所以有

$F[k] = f[k]\sum_{k|t} F[t]$

然后就一个 $\log$ 做完了。

#include "iostream"
#include "cstring"
#include "cstring"
#include "cstdio"
using namespace std;
#define MAXN 1000006
#define P 1000000007
typedef long long ll;
int n;
int A[MAXN] , fa[MAXN] , num[MAXN] , f[MAXN]; ll S[MAXN];
ll gcd( ll a , ll b ) { return !b ? a : gcd( b , a % b ); }
int main() {
    cin >> n;
    for( int i = 1 ; i <= n ; ++ i ) scanf("%d",&A[i]);
    for( int i = 2 ; i <= n ; ++ i ) scanf("%d",&fa[i]);
    for( int i = n ; i ; -- i ) S[i] += A[i] , S[fa[i]] += S[i];
    ll s = S[1];
    for( int i = 1 ; i <= n ; ++ i ) if( s / gcd( S[i] , s ) <= n ) ++ num[s / gcd( S[i] , s )];
    for( int i = 1 ; i <= n ; ++ i ) if( num[i] )
        for( int j = i ; j <= n ; j += i )
            f[j] += num[i];
    for( int i = 1 ; i <= n ; ++ i ) f[i] = ( f[i] == i );
    ll ans = 0;
    for( int i = n ; i > 1 ; -- i ) if( f[i] ) {
        for (int j = i + i; j <= n; j += i) ( f[i] += f[j] ) %= P;
        ( ans += f[i] ) %= P;
    }
    cout << ans + 1 << endl;
}