kmjp's blog

競技プログラミング参加記です

Codeforces #511 Div1 C. Region Separation

無駄に制限厳しくない…?
http://codeforces.com/contest/1034/problem/C

問題

木を成す無向グラフが与えられる。
各頂点には重みが設定されている。

木を、重みの総和が等しくなる範囲で分割する、という作業を繰り返す。
(複数の木を分割した場合、分割後のすべての木の総和が等しくなければならない)
分割の手順は全部で何通りあるか求めよ。

解法

各木の重みの総和を決めると、その分割手法は一意に決まる。
分割可能な木の重みをすべて求めよう。
そうすると、可能な木の重みから再度分割し、その重みの約数のうちやはり同様に分割可能な重みに遷移できるので、単純なDPで数え上げができる。

あとは、「分割可能な木の重みをすべて求めよう。」のパートである。
入力全体の重みの総和をSWとする。
重要な特性として、重みW毎の分割が可能である場合、グラフを根付き木とみなした場合にSubTreeの重みの総和がWの倍数であるような場所がSW/W個あればよい。
よって重みWに対し、その倍数である個数を数え上げよう。

頂点vのSubTreeの重みの総和をW(v)とする。
g=GCD(W(v),SW)とすると、gがこの頂点を根とする分割のうちで可能な重みの最大値となる。

あとはSWの約数のうち、gの約数においても同様に可能な重みの候補となるので、エラトステネスの篩の容量で数え上げよう。
なお、重みWのうちSW/W>Nとなるものは考えなくてもよい。

int N;
int A[1010101],ma=0;
ll S[1010101];
int P[1010101];
ll mo=1000000007;

ll F[1010101];
ll R[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&N);
	FOR(i,N) {
		scanf("%d",&A[i]);
		ma=max(ma,A[i]);
	}
	FOR(i,N-1) {
		scanf("%d",&P[i+1]);
		P[i+1]--;
	}
	
	for(i=N-1;i>=0;i--) {
		S[i]+=A[i];
		if(i) S[P[i]]+=S[i];
	}
	
	FOR(i,N) {
		ll a=S[0]/__gcd(S[i],S[0]);
		if(a<=N) F[a]++;
	}
	for(i=N;i>=1;i--) {
		for(j=i*2;j<=N;j+=i) F[j]+=F[i];
	}
	
	vector<ll> ret,hoge;
	for(i=N;i>=1;i--) if(F[i]==i) {
		ll a=1;
		FOR(j,hoge.size()) if(hoge[j]%i==0) a+=ret[j];
		hoge.push_back(i);
		ret.push_back(a%mo);
	}
	
	cout<<ret.back()<<endl;
}

まとめ

わりとTLがきつい。これN=2*10^5じゃダメだったのかな。