AOJ 2344 Multi Ending Story

AOJ 動的計画法

問題

二分木が与えられる。

  • 根に移動するコストが０
  • 子に移動するコストが０
  • 一つだけ、今いるノードを覚えることができて、覚えるコストが０
  • 覚えたノードに移動するコストが０
  • （何度でも新たに上書きで覚えることができる）

とき、全ての子を訪れるのにかかる最小コストを求めよ。

制約条件

n≦500000

方針

木DP.


頂点vにいるとき、vの左の子をl[v], 右の子をr[v]とする。
l[v]を頂点とする部分木のノードを全て訪問し終えた後でr[v]を頂点とする部分木のノードを初めて訪れるか、
r[v]を頂点とする部分木のノードを全て訪問し終えた後でl[v]を頂点とする部分木のノードを初めて訪れるような訪問のしかたしか最短ではない。


dp[0][v]を、vを頂点とする部分木を、セーブを使わないで全部訪問するのにかかるコスト、
dp[1][v]を、vを頂点とする部分木を、セーブを使って全部訪問するのにかかるコストとする。


dp[0][v]はすぐにもとまる。
dp[1][v]は、vでセーブして、左の部分木をセーブなしで全て訪れて、右の部分木を訪れるか、その逆の訪問の仕方がある。
もしくは、左の部分木をセーブありで訪れて、一度根まで戻って、右の部分木を訪れるという訪問の仕方がある。
dp[1][v]はこれらの最小値である。


再帰でやるとREなので適当にループで書き換える。

ソースコード

const int MX = 500001;
int n, l[MX], r[MX], lf[MX], depth[MX];
ll dp[2][MX];

inline void rec(int c, int d = 0){
	lf[c] += lf[l[c]] + lf[r[c]];
	dp[0][c] += dp[0][l[c]] + lf[l[c]];
	dp[0][c] += dp[0][r[c]] + lf[r[c]];
	
	dp[1][c] = min(lf[l[c]] + dp[0][l[c]] + dp[1][r[c]], lf[r[c]] + dp[1][l[c]] + dp[0][r[c]]) + 1;
	dp[1][c] = min(dp[1][c], 2 + d + dp[1][l[c]] + dp[1][r[c]]);
}

int main(){
	cin >> n;
	rep(i, n - 1) cin >> l[i + 1] >> r[i + 1];
	
	vi ord;
	queue<pi> q;
	q.push(mp(1, 0));
	while(!q.empty()){
		int c = q.front().first, d = q.front().second; q.pop();
		ord.pb(c);
		depth[c] = d;
		if(l[c] < n) q.push(mp(l[c], d + 1));
		if(r[c] < n) q.push(mp(r[c], d + 1));
	}
	reverse(all(ord));
	
	lf[n] = 1;
	rep(i, n - 1) rec(ord[i], depth[ord[i]]);
	cout << dp[1][1] << endl;
	return 0;
}