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; }