TopCoder SRM 559 Div1 Medium HatRack

問題

木が与えられる。
この木と同じ頂点数で、葉以外の頂点の子は必ず一つまたは二つで、
なるべく平衡しているような木で、余った葉はなるべく左側から埋められている木を考える。

この木に、与えられた木を対応させる方法は何通りあるか、求めよ。

制約条件

枝の本数≦50

方針

根にする頂点を一つ決める。
そこから、頂点を当てはめて探索する。
子の数が違ったりしたらその時点で枝刈り。

適当にメモ化すると最悪が5msくらいで通る。

ソースコード

vector<vi> e;
ll dp[51][51][52], cld[51];

void dfs(int c, int p){
	cld[c]++;
	rep(i, e[c].size()) if(e[c][i] != p){
		dfs(e[c][i], c);
		cld[c] += cld[e[c][i]];
	}
}
ll rec(int c, int p, int num){
	if(num < 0) return 0;
	if(num != cld[c]) return 0;
	
	if(dp[c][p][num] >= 0) return dp[c][p][num];
	ll &res = dp[c][p][num];
	res = 0;
	
	int cc = 0, cs[51];
	rep(i, e[c].size()) if(e[c][i] != p) cs[cc++] = e[c][i];
	
	if(num == 1) return res = 1;
	if(cc == 1){
		if(num == 2) return res = 1;
		return res = 0;
	}
	if(cc > 2) return res = 0;
	
	int a = 1;
	while(1){
		int b = a * 2 + 1;
		if(b > num) break;
		a = b;
	}
	int l = min(num - a, a / 2 + 1) + a / 2;
	
	rep(i, cc){
		res += rec(cs[i], c, l) * rec(cs[1 - i], c, num - l - 1);
	}
	return res;
}

class HatRack {
	public:
	long long countWays(vector <int> knob1, vector <int> knob2) 
	{
		int n = knob1.size() + 1;
		e.clear(); e.resize(n);
		
		rep(i, n - 1){
			int a = knob1[i] - 1;
			int b = knob2[i] - 1;
			e[a].pb(b); e[b].pb(a);
		}
		ll ans = 0;
		rep(i, n){
			memset(cld, 0, sizeof(cld));
			memset(dp, -1, sizeof(dp));
			dfs(i, i);
			ans += rec(i, i, n);
		}
		return ans;
	}
};