SRM 413 DIV1 Hard TreeCount

問題 Editorial

問題

あるグラフに対して頂点集合Sがk-stableであるとは、S中のそれぞれの頂点に対して、隣接する頂点の中でSに含まれる頂点の数がk個以下であるものをいう。
木graphが与えられる。i∈[0..|graph|-1]のそれぞれでi-stable setの数をmod 112901989で求め、それをvectorで返せ。

• 1 ≦ |graph| ≦ 50
• graphは木を表している

解答

木DP。(頂点,辺,残りのk,この頂点が含まれるかどうか)を持ってやる。

コメント

877.01ptで提出でき、これは仮に本番に参加していたら最速であった。
やっぱり、自明なDPは速く実装できる、その長所を伸ばそう。

コード

#include <string>
#include <vector>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define pb(x) push_back(x)
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef vector<int> vi; typedef long long ll; typedef vector<string> vs;
ll memo[51][51][55][2];
struct TreeCount {
	vs gg; int n;
	vector<vi> g;
	int K;
	void dfs(int i,int parent){
		rep(j,n)if(gg[i][j]=='Y') {
			if(j!=parent) {
				g[i].pb(j);
				dfs(j,i);
			}
		}
	}
	ll rec(int i, int j, int k, bool b) {
		if(k < 0) return 0;
		ll &r = memo[i][j][k][b];
		if(r != -1) return r;
		r = 0;
		if(j == g[i].size())
			r = 1;
		else {
			r += rec(g[i][j], 0, 51, false) * rec(i, j+1, k, b);
			r += rec(g[i][j], 0, K - b, true) * rec(i, j+1, k-1, b);
		}
		return r;
	}
	vector <int> count(vector <string> graph) {
		gg = graph; n = gg.size(); g.resize(n);
		dfs(0,-1);
		vi r;
		rep(i, n) {
			K = i;
			mset(memo, -1);
			ll x = rec(0, 0, K, true) + rec(0, 0, 51, false);
			r.pb(x % 112901989);
		}
		return r;
	}
};