CF1034 C. Region Separation 题解

CF1034 C. Region Separation

题意

给出一棵树，每个点有点权。

每一层是一些集合的集合。

令第一层的集合包含一个包含所有点的集合。

每次操作可以把一层的每一个集合分为两部分或两部分以上，作为下一层的集合。

要求每一层的每个集合都是一个连通块且每层的集合的权值和相等。

题解

考虑全部分成两层的方案数，考虑一个暴力的做法，令(S_i)表示以(i)为子树中的点权和，设当前要分为(k)个集合，每个集合的权值和为(frac{S_1}{k})。从下到上遍历每个点(i)，如果(large frac{S_1}{k}|S_i)就选出(i)这棵子树，将它删去，不难发现当这样的子树恰好有(k)个时，存在合法的分割方案。

考虑对每个子树(i)计算贡献，(large x cdot frac{S_1}{k} = S_i)即(large frac{S_ik}{S_1})为整数，这样的(k)满足(k)是(large frac{S_1}{gcd(S_i,S_1)})的倍数，可以在(O(n ln n))的时间内求出。

考虑分为(k_i)个(i)层集合，存在这样的合法方案当且仅当(k_{i-1} | k_i)且分成(k_i)个(2)层集合合法，(dp)计算即可

Code

#include<bits/stdc++.h>
#define int long long
#define N 1000015
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define inf 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define lowbit(i) ((i)&(-i))
#define VI vector<int>
#define all(x) x.begin(),x.end()
#define SZ(x) ((int)x.size())
using namespace std;
const int mod = 1e9+7;
int n,a[N],p[N],s[N],f[N],ans[N];
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%lld",&n);
	rep(i,1,n) scanf("%lld",&a[i]);
	rep(i,2,n) scanf("%lld",&p[i]);
	per(i,1,n) a[p[i]] += a[i];
	rep(i,1,n) {
		int k = a[1]/__gcd(a[1],a[i]);
		if(k <= n) f[k]++;
	}
	// rep(i,1,n) assert(f[i] <= i);
	per(i,1,n) for(int j = i+i;j <= n;j += i) (f[j] += f[i]) %= mod;
	ans[1] = 1;
	rep(i,1,n){
		if(f[i] != i) continue; 
		for(int j = i+i;j <= n;j += i) if(f[j] == j) (ans[j] += ans[i]) %= mod;
	}
	int res = 0;
	rep(i,1,n) (res += ans[i]) %= mod;
	printf("%lld
",res);
	return 0;
}