TopCoder SRM 570 Div2 Hard CentaurCompanyDiv2

Div2 MediumはDiv1 Easyとほぼ同じなので、次はDiv2 Hardに行く。
http://community.topcoder.com/stat?c=problem_statement&pm=12426

問題

木となっているグラフ与えられる。
ここからいくつかの辺を選んで、小さな木を作れる組み合わせの数を答える。

解法

現在の点と直前の点を引数としたDFSを行う。
このDFSは２つの組み合わせ数を返す。

1. 現在の点を選ばなかった場合の木の組み合わせ数
2. 現在の点を選んで場合の木の組み合わせ数

前者は、現在の点を選ばない場合の木の作り方は、(直前の点を除く)隣接点の向こうにある木の組み合わせ数の総和になる。

後者は、現在の点を選ぶ場合、(直前の点を除く)隣接点の向こうにある現在の点と接続された木の組み合わせ数の積になる。

両者を計算して最後に足し合わせれば良い。
O(|V|)で終わるので計算量は心配なし。

class CentaurCompanyDiv2 {
	public:
	vector<int> edge[60];
	int N;
	
	pair<ll,ll> dfs(int cur, int prev) {
		int i;
		ll ns=0,s=1;
		FOR(i,edge[cur].size()) {
			int tar=edge[cur][i];
			if(tar==prev) continue;
			pair<ll,ll> tm = dfs(tar,cur);
			ns += tm.first+tm.second;
			s *= (1+tm.second);
		}
		return make_pair(ns,s);
	}
	
	long long count(vector <int> a, vector <int> b) {
		int i,x,y;
		
		N=a.size()+1;
		FOR(x,N) edge[x].clear();
		
		FOR(x,a.size()) {
			edge[a[x]-1].push_back(b[x]-1);
			edge[b[x]-1].push_back(a[x]-1);
		}
		
		pair<ll,ll> p = dfs(0,-1);
		return 1+p.first + p.second;
	}
};

まとめ

この問題、割とすぐに解法が思いついてすぐに解けた。
本番なら800pt以上取れる時間だ。

残念ながら今回はこのアイデアはDiv1には適用できないけど、今後類似問題が出そうな問題設定なので今回の解き方は覚えておこう。