#include<bits/stdc++.h>
#define fi first
#define se second
#define show(x) cerr<<#x<<"="<<x<<"\n"
typedef long long ll;
using namespace std;
const int inf=(int)1e9;
vector<vector<pair<int,int> > > v;
bool past[801];
bool leaf[801];
void dfs(int now){
bool flag=1;
for(int i=0;i<(int)v[now].size();i++){
if(past[v[now][i].fi])continue;
flag=0;
past[v[now][i].fi]=1;
dfs(v[now][i].fi);
}
if(flag)leaf[now]=1;
}
int bfs(int s){
int d[801];
for(int i=0;i<801;i++){
d[i]=0;
}
queue<pair<int,int> > q;
q.push({s,0});
bool p[801];
for(int i=0;i<801;i++)p[i]=0;
p[s]=1;
while(!q.empty()){
int now=q.front().fi;
int nowcost=q.front().se;
q.pop();
for(int i=0;i<(int)v[now].size();i++){
if(leaf[v[now][i].fi])continue;
if(p[v[now][i].fi])continue;
p[v[now][i].fi]=1;
d[v[now][i].fi]=v[now][i].se+nowcost;
q.push({v[now][i].fi,v[now][i].se+nowcost});
}
}
int res=0;
for(int i=0;i<801;i++){
res=max(res,d[i]);
}
return res;
}
int main(){
int n;
while(cin>>n,n){
v.resize(n);
for(int i=0;i<n;i++)v.resize(0);
for(int i=0;i<n;i++){
past[i]=0;
leaf[i]=0;
}
int tmp[801];
for(int i=0;i<n-1;i++){
cin>>tmp[i];tmp[i]--;
}
ll ans=0;
for(int i=0;i<n-1;i++){
int cost;cin>>cost;
ans+=cost*3;
v[i+1].push_back({tmp[i],cost});
v[tmp[i]].push_back({i+1,cost});
}
past[0]=1;
dfs(0);
for(int i=0;i<n;i++){
past[i]=0;
}
for(int i=0;i<n;i++){
if(leaf[i]){
past[i]=1;
dfs(i);
break;
}
}
for(int i=0;i<n;i++){
if(leaf[i])ans-=2*v[i][0].se;
}
ll ans2=ans;
for(int i=0;i<n;i++){
if(leaf[i])continue;
int maxedge=bfs(i);
ans2=min(ans2,ans-maxedge);
}
cout<<ans2<<endl;
}
return 0;
}
- あまりいい方法が考えられず、解けなかった
- どんな場所は何回通るのかをしっかり意識して考えたい。