ICPC2014 国内予選 E 橋の撤去

問題

無向木で表されるような島と橋が与えられる。
辺の重みが、橋を渡る時間であり、その橋を壊す時間である。（両者は等しい）

好きな島から出発し、橋を渡るか、今いる島につながっている橋を壊すかすることができる。
終了時には好きな島にいてよい。
全ての橋を壊すのにかかる時間の最小値を求めよ。

制約条件

n≦800

方針

木DPをすればよい。
終了時の島をrとして、これ全通りに対してそれぞれDPを試す。

DPは、「グラフのうち、自分以下の部分を全て破壊するコスト」を求めるDP.
グラフのうち、自分以下の部分というのは、木の根を決めたとき、
自分および、自分の子孫からなる部分木のことを言う。
この場合はrから再帰をスタートするのでrが木の根。

dp[0][v]を、v以下の部分木を破壊するコストでスタートは自由
dp[1][v]を、v以下の部分木を破壊するコストで、スタートもv
にする。

dp[1][v]は簡単に求められて、
それぞれの子の島に行ってdp[1][child]のコストで島を破壊して、
またvに戻って、今戻った橋を破壊するということをやればよい。

dp[0][v]は、どこか一つの子uにいかなかったことにする。
で、その子の部分木を全部壊すのに、「スタート自由で、最後はuで終わって壊す」ことをして、vに戻ればよい。

「スタート自由で、最後はuで終わって壊す」は、dp[1][u]に等しい。なので、再帰で前に求めた結果が使える。
これを全部の子uで計算してみて、一番小さかったコストを採用すればよい。

計算量

一つのrにつき、再帰にかかる時間計算量はO(n)
（全ての頂点と辺を1回ずつ見るだけだから）

rをn個試すので、全体の時間計算量はO(n^2)

ソースコード

import java.util.*;

public class Main {

	int n;
	int ans;
	int[][] dp;
	boolean[] isLeaf;
	ArrayList<int[]>[] e;
	
	//dp[0][r] : 好きなとこからスタートして、r以下の部分木を全て破壊し、rで終了するときのコスト
	//dp[1][r] : rからスタートして、r以下の部分木を全て破壊し、rで終了するときのコスト
	
	void rec(int c, int p){
		
		dp[1][c] = 0;
		isLeaf[c] = true;
		for(int[] a : e[c]){
			int to = a[0], cost = a[1];
			if(to == p) continue;
			rec(to, c);
			dp[1][c] += dp[1][to];
			if(!isLeaf[to]) dp[1][c] += 3 * cost; //橋を行って、戻って、壊す
			else dp[1][c] += cost; //葉だったら行かないで壊す
			
			isLeaf[c] = false;
		}
		dp[0][c] = dp[1][c];
		
		//開始地点を自由に選べる場合、どこの子のところからスタートするか
		for(int[] a : e[c]){
			int to = a[0], cost = a[1];
			if(to == p || isLeaf[to]) continue; //葉からスタートする場合を除く
			
			int tmp = dp[1][c]; //自分からはじまって自分で終わる場合を少しいじって計算したい
			
			tmp -= dp[1][to]; //toのところをなかったことにする
			tmp += dp[0][to]; //toの子孫のどこかからスタートしたことにする
			
			tmp -= cost; //一回分戻らなくてよい
			
			dp[0][c] = Math.min(dp[0][c], tmp);
		}
	}
	
	@SuppressWarnings("unchecked")
	void run(){
		Scanner sc = new Scanner(System.in);
		while(true){
			n = sc.nextInt();
			if(n == 0) break;
			
			dp = new int[2][n];
			e = new ArrayList[n];
			isLeaf = new boolean[n];
			for(int i = 0; i < n; i++) e[i] = new ArrayList<int[]>();
			
			int[] ps = new int[n - 1];
			int[] ds = new int[n - 1];
			
			for(int i = 0; i < n - 1; i++) ps[i] = sc.nextInt() - 1;
			for(int i = 0; i < n - 1; i++) ds[i] = sc.nextInt();
			for(int i = 0; i < n - 1; i++){
				e[i + 1].add(new int[]{ps[i], ds[i]});
				e[ps[i]].add(new int[]{i + 1, ds[i]});
			}
			
			ans = Integer.MAX_VALUE;
			for(int r = 0; r < n; r++){
				rec(r, r);
				ans = Math.min(ans, dp[0][r]);
			}
			System.out.println(ans);
		}
	}
	public static void main(String[] args) {
		new Main().run();
	}
}