AOJ1196 - Bridge Removal

簡単な問題ではありますが、久しぶりに書いてみます。

問題：
橋の撤去 | Aizu Online Judge

問題概要：
大きさnの木について、自分のいる頂点から出ている辺を取り除く操作と、辺上を頂点から頂点へ移動する操作にそれぞれその辺のコストの分の時間が掛かる。好きな頂点から操作を開始するとき、すべて
の辺を取り除くのに掛かる最短時間を求めよ。

解法：
はじめの木をG、Gから葉を除いた木をG'と書くと、一度しか通らない経路はG'の直径となります。
よって求める時間は
Gの全コスト+G'の全コスト*2-G'の直径
です。
木の直径の求め方は
木の直径を求めるアルゴリズムの証明 - あんまり見ないでください
を参照しました。

コード：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#define mp make_pair
#define pb push_back
#define INF 100000005
#define rep(i,n) for(int i = 0;i < n;i++)
using namespace std;
typedef pair<int,int> PI;
int n;
bool erased[805];
vector<PI> G[805];
int dist[805];
void dfs(int s){
    rep(i,G[s].size()){
        int to=G[s][i].first;
        if(!erased[to]&&dist[to]>=INF){
            dist[to]=G[s][i].second+dist[s];
            dfs(to);
        }
    }
}


int main(){
    while(1){
        int temp;
        int t[805],ans=0;
        cin>>n;
        if(!n){
            break;
        }
        rep(i,n){
            erased[i]=false;
            G[i].clear();
        }
        rep(i,n-1){
            cin>>t[i];
            t[i]--;
        }
        rep(i,n-1){
            cin>>temp;
            ans+=temp*3;
            G[i+1].pb(mp(t[i],temp));
            G[t[i]].pb(mp(i+1,temp));
        }
        int start = 0;
        rep(i,n){
            if(G[i].size()==1){
                ans-=G[i][0].second*2;
                erased[i]=1;
                if(i==start){
                    start++;
                }
            }
        }
        fill(dist,dist+n,INF);
        dist[start]=0;
        dfs(start);
        rep(i,n){
            if(!erased[i]&&dist[i]>dist[start])start=i;
        }
        fill(dist,dist+n,INF);
        dist[start]=0;
        dfs(start);
        int hoge = 0;
        rep(i,n){
            if(!erased[i]){
                hoge = max(hoge,dist[i]);
            }
        }
        ans -= hoge;
        cout<<ans<<endl;
    }
    return 0;
}