TopCoder SRM 674 Div2 Hard VampireTreeDiv2

久々にちょっと難しめのDiv2Hard？
https://community.topcoder.com/stat?c=problem_statement&pm=14001

問題

Div1 Easy同様吸血鬼の関係を考える。
Div1 Easyは常に各吸血鬼は主人1人から生成されたが、こちらはi番の吸血鬼の生成方法は以下の2通りがある。
ただし、親子として生成される吸血鬼数は15体以下である。

• 自分より番号の小さな吸血鬼A[i]1体から生成される。A[i]番とi番は主従関係にある。
• 自分より番号の小さな吸血鬼A[i]、B[i]2体から生成される。A[i]番とi番及びB[i]番とi番は親子関係にある。

すなわち、Div1 Easyと異なりこちらは完全に吸血鬼の主従関係・親子関係が確定している。

この状態で、吸血鬼を何体か選びたい。
その際以下の条件を満たさなければならない。

• 主従関係にある吸血鬼同士は、最低1体は選ばれること。
• 親子関係にある吸血鬼同士は、最低1体は選ばれること。

条件を満たす選び方のうち、選ぶ吸血鬼数が最小のものを求め、その選び方の組み合わせ数を求めよ。

解法

まず親子関係がなく主従関係だけの場合を考える。
これは良くある定番のDPで、親から順に

• 親を選択するので、子は選択してもしなくてもよい
• 親を選択しないので、子は選択しなければならない

の2通りでDFSしながら各subtreeの最小選択数とその組み合わせ数を求めて重ねる(選択数は足し算、組み合わせは掛算)ようにしていけば良い。

問題は親子関係の処理。
親子で生成される吸血鬼の数(以下P)は少ないので、総当たりしよう。
親子合わせて3体の吸血鬼組について、選ばれる・選ばれないを考えると、(2^3)^P通り考える必要があってややこしい。
以下のように考えると、2^P通りだけ考えればよくなる。

• 子供が選択される場合。この場合、DFS過程で必ず子を選択しなければならない。親2体はどちらでも良い。
• 子供が選択されない場合。この場合、DFS過程で必ず親2体を選択しなければならない。子は選択してはならない。

なお、DFS過程で親A[i]からiと親B[i]からi両方探索してしまうと、i番以下のsubtreeの組み合わせを二重にカウントしてしまうので片方だけ探索しよう。

ll mo=1000000007;
vector<int> E[1010];
pair<int,ll> memo[1010][2];
int must0[1010];
int must1[1010];

class VampireTreeDiv2 {
	public:
	
	pair<int,ll> dfs(int cur,int need) {
		if(memo[cur][need].first>=-1000) return memo[cur][need];
		
		int mi=10010;
		ll pat=0;
		
		if(must0[cur]==0) {
			int mi2=1;
			ll pat2=1;
			FORR(r,E[cur]) {
				auto a=dfs(r,0);
				mi2+=a.first;
				pat2=pat2*a.second%mo;
			}
			mi=mi2, pat=pat2;
		}
		
		if(need==0 && must1[cur]==0) {
			int mi2=0;
			ll pat2=1;
			FORR(r,E[cur]) {
				auto a=dfs(r,1);
				mi2+=a.first;
				pat2=pat2*a.second%mo;
			}
			if(mi2<mi) mi=mi2, pat=pat2;
			else if(mi2==mi) pat=(pat+pat2)%mo;
		}
		return memo[cur][need] = {mi,pat};
	}
	
	int countMinSamples(vector <int> A, vector <int> B) {
		int mi=1010;
		ll ret=0;
		int N=A.size(),i;
		vector<int> ind;
		
		FOR(i,N+1) E[i].clear();
		FOR(i,N) {
			E[A[i]].push_back(i+1);
			if(B[i]!=-1) ind.push_back(i);
		}
		
		for(int mask=0;mask<1<<(ind.size());mask++) {
			ZERO(must0);
			ZERO(must1);
			FOR(i,ind.size()) {
				if(mask&(1<<i)) {
					must1[A[ind[i]]]=must1[B[ind[i]]]=1;
					must0[ind[i]+1]=1;
				}
				else {
					must1[ind[i]+1]=1;
				}
			}
			
			FOR(i,N+1) memo[i][0].first=memo[i][1].first=-1010;
			auto v = dfs(0,0);
			if(v.first<mi) mi=v.first, ret=0;
			if(v.first==mi) ret += v.second;
		}
		
		return ret % mo;
	}
}

まとめ

親子における(2^3)^Pの組み合わせを2^Pに落とし込むのに結構頭使った。