TopCoder SRM 622 Div1 Medium Ethernet

問題

n頂点からなる無向木が与えられる。
この木の辺を何本か切断して、直径がそれぞれmaxDist以下であるような木いくつかにしたい。
最小でいくつの木に分ければよいか求めよ。

制約条件

n≦51
辺の長さ≦500
maxDist≦500

方針

木DP.
vを根とする部分木で、深さdまで子を伸ばしていいときの最小の切断回数をrec(v, d)とする。
これを再帰していけばよい。
一番深いところで切断する子idxを選び、そのときの深さmdを全通り試す。

一番深いとこで切断する子以外の子において切断する深さは、
md以下かつ、maxDist - md以下であれば条件を満たす。

子につながる辺を切断した場合は、次のd = maxDistとして再帰すればよい。

で、最悪計算量が上手く見積もれないのだけど、
実質回るところはあまりなくて、最悪150msくらいで通る。

ソースコード

class Ethernet {
	public:
	
	int n, maxDist;
	int dp[51][501];
	vector<vector<pi> > e;
	
	int rec(int c, int d){
		
		if(d < 0) return 10000;
		
		int &res = dp[c][d];
		if(res >= 0) return res;
		if(e[c].empty()) return res = 0;
		
		res = inf;
		rep(idx, e[c].size()) for(int md = 0; md <= d; md++){
			
			int tmp = 0;
			
			rep(i, e[c].size()){
				int lim = i == idx ? md : min(maxDist - md, md);
				tmp += min(rec(e[c][i].first, lim - e[c][i].second), rec(e[c][i].first, maxDist) + 1);
			}
			res = min(res, tmp);
		}
		return res;
	}
	
	int connect(vector <int> parent, vector <int> dist, int maxDist) {
		
		memset(dp, -1, sizeof(dp));
		this->maxDist = maxDist;
		n = parent.size() + 1;
		
		e.clear(); e.resize(n);
		rep(i, n - 1) e[parent[i]].pb(mp(i + 1, dist[i]));
		
		return rec(0, maxDist) + 1;
	}
};