mayoko’s diary

プロコンとかいろいろ。

AOJ 1196: Bridge Removal

解法

スタートする頂点を全部試すとして, 各頂点について O(N) で橋の撤去にかかる最小費用を求めれば良いです。まぁ木DP ですよね。

サンプル見ればわかりますが, この問題でポイントなのは p -> v と訪れた後, 必ずしも p に戻ってくる必要はなく, p -> v1, p -> v2, ... といった p の子のうち v 以外のものを処理して p に戻ってきた後, v で処理する, というようなことができることです。

dp[v][flag] = (頂点 v 以下の部分木の橋を全部撤去するのにかかる費用の最小値。ただし, flag = 1 の場合は必ず最後に v に帰ってくる)
というような dp を考えて, 適当に処理すれば良いです。

flag = 1 の時は, v の子が葉の場合は子に行かず橋を撤去するだけでよく, そうでないときは子頂点に行って全部の橋を撤去してから v に戻って v - ch の橋を撤去します。
flag = 0 の時は, どこか一つの頂点からは戻ってこなくて良いので, どの頂点から戻ってこないかを全部調べます。

const int MAXN = 888;
int p[MAXN], d[MAXN];

struct Edge {
	int to;
	int cost;
	Edge() {}
	Edge(int to, int cost) : to(to), cost(cost) {}
};

vector<Edge> G[MAXN];

ll dp[MAXN][2];

// flag = 0: 帰ってこなくて良い
// flag = 1: 必ず v に戻ってこなければならない
ll dfs(int v, int p, int flag) {
	ll& ret = dp[v][flag];
	if (ret >= 0) return ret;
	ret = 0;
	ll sum = 0;
	for (Edge e : G[v]) {
		if (e.to == p) continue;
		dfs(e.to, v, 0);
		dfs(e.to, v, 1);
		if (G[e.to].size()==1) {
			sum += e.cost;
		} else {
			sum += e.cost + dp[e.to][1] + e.cost + e.cost;
		}
	}
	ret = sum;
	if (!flag) {
		for (Edge e : G[v]) {
			if (e.to == p) continue;
			if (G[e.to].size() == 1) continue;
			ll tmp = sum-dp[e.to][1]-e.cost + dp[e.to][0];
			ret = min(ret, tmp);
		}
	}
	return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    while (cin >> n) {
    	if (n==0) break;
    	for (int i = 0; i < n-1; i++) 
    		cin >> p[i];
    	for (int i = 0; i < n-1; i++) 
    		cin >> d[i];
    	for (int i = 0; i < n; i++)
    		G[i].clear();
    	for (int i = 0; i < n-1; i++) {
    		p[i]--;
    		G[i+1].emplace_back(p[i], d[i]);
    		G[p[i]].emplace_back(i+1, d[i]);
    	}
    	ll ans = 1ll<<55;
    	for (int i = 0; i < n; i++) {
    		memset(dp, -1, sizeof(dp));
    		ans = min(ans, dfs(i, -1, 0));
    	}
    	cout << ans << endl;
    }
    return 0;
}