静かで孤独な日記

のんびりたまに

AOJ 1196 Bridge Removal

#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;
    //show(ans);
    for(int i=0;i<n;i++){
      if(leaf[i])continue;
      int maxedge=bfs(i);
      ans2=min(ans2,ans-maxedge);
      //show(maxedge);
    }
    cout<<ans2<<endl;
  }
  return 0;
}
  • あまりいい方法が考えられず、解けなかった
  • どんな場所は何回通るのかをしっかり意識して考えたい。