TopCoder SRM 693 Div2 Hard TreeAndCycle

Nが小さめなのがありがたい。
https://community.topcoder.com/stat?c=problem_statement&pm=14330

問題

木を成すグラフがある。
各頂点及び辺にはコストがある。

このグラフに辺を増減し、全体を１つの閉路にしたい。
その際、既存の辺を消すにはその辺のコストがかかるし、辺を追加するには両端の頂点のコストがかかる。
閉路を作るのに必要なコストを最小化せよ。

解法

閉路を作ると考えると難しい。
グラフを複数のパスに分割すると考えよう。
(パス同士は点を共有せず、全部のパスで全頂点を網羅する)。
パスの両端をどうつないでも、辺を追加するコストはパスの両端の頂点のコストの総和なので、つなぎかたは考えなくて良い。

後は単純な木DPで、各頂点で親方向の辺を残す場合と消す場合でsubtreeのコストの総和を求めればよい。
各頂点の子頂点からは、親方向の辺を残せるのは２頂点までである点に留意。

int dp[101][3];
int pe[101];

class TreeAndCycle {
	public:
	int N;
	vector<int> V;
	vector<pair<int,int>> E[101];
	
	int dpdp(int cur,int isopen) {
		if(dp[cur][isopen]>=0) return dp[cur][isopen];
		int& ret = dp[cur][isopen];
		ret=1<<30;
		
		int t=0;
		FORR(e,E[cur]) t+=dpdp(e.first,0);
		ret=t+V[cur]+(isopen?0:V[cur]+pe[cur]);
		
		// both
		if(isopen==0) {
			FORR(e,E[cur]) FORR(e2,E[cur]) if(e!=e2) {
				int t=dpdp(e.first,1)+dpdp(e2.first,1)+pe[cur];
				FORR(e3,E[cur]) if(e!=e3 && e2!=e3) t+=dpdp(e3.first,0);
				ret=min(ret,t);
			}
		}
		FORR(e,E[cur]) {
			int t=dpdp(e.first,1);
			FORR(e2,E[cur]) if(e!=e2) t+=dpdp(e2.first,0);
			ret=min(ret,t+(isopen?0:V[cur]+pe[cur]));
		}
		return ret;
		
	}
	
	int minimize(vector <int> costV, vector <int> pre, vector <int> costE) {
		N=costV.size();
		V=costV;
		int i;
		
		FOR(i,N) E[i].clear();
		FOR(i,N-1) {
			E[pre[i]].push_back({i+1,costE[i]});
			pe[i+1]=costE[i];
		}
		
		MINUS(dp);
		return min(dpdp(0,0),dpdp(0,1)+V[0]);
	}
}

まとめ

妙に手こずったけど、使うテクとしてはオーソドックスか。