M-SOLUTIONS プロコンオープン D - Maximum Sum of Minimum

atcoder.jp

問題

木の各頂点に与えられた数列の要素を書き込みます。
辺には両端の頂点の数字のうち小さい方を書き込みます。
辺に書き込んだ数字の合計（スコア）が最大になるようにしたときの最大値と各頂点への数字の書き込み方を出力します。

考察

スコアの最大値が数列のもっとも小さな要素から最大値の次に大きな要素までの合計になることはわかりました。
あとはそのような木の構築ですが、とりあえず､スコアの最大値をだすところまでやってみました。

コード　前半

#include<bits/stdc++.h>
using namespace std;

int main(){  
  int N;
  cin>>N;
  vector<vector<int>> G(N);
  vector<pair<int,int>> vp;
  for(int i=1;i<N;i++){
    int a,b;
    cin>>a>>b;
    a--;b--;
    G[a].emplace_back(b);
    G[b].emplace_back(a);
    vp.emplace_back(a,b);
  }
  int C[10010];
  int sum=0;
  for(int i=0;i<N;i++){
    cin>>C[i];
  }
  sort(C,C+N);
  for(int i=0;i<N-1;i++){
    sum+=C[i];
  }
  cout<<sum<<endl;
  return 0;
}

構築に苦しむ

後半の構築部分はbfsを使ってやってみましたがうまくいきません。
cout デバッグで変数の値を確認したところ入力は大丈夫そうなのですがもう少し検討してみます。

  //構築
  queue<int>que;
  que.push(0);  
  vector<int>ans;
  int k=N-1;
  cout<<"#k"<<k<<" "<<C[k]<<endl;
  int l;
  int qq;
  
  cout<<"G[0].size()"<<G[0].size()<<endl;
  cout<<"que.size()"<<que.size()<<endl;
  while(que.size()!=0){
    cout<<"#"<<qq<<endl;
    qq=que.front();
    que.pop();
    ans[qq]=C[k];
    k--;
    l=G[qq].size();
    for(int i=0;i<l;i++){
      if(ans[G[qq][i]]==0){
        que.push(G[qq][i]);
      }
    }
  }

デバッグ続き

いろいろ確認していると
ans[qq]=C[k];
のところでエラーになることがわかりました。

ansの宣言のところを

 vector<int>ans(N-1,0);

に変えてみましたが2ケースWA。

間違いに気づき

 vector<int>ans(N,0);

に直してACしました。

ACしたコード

#include<bits/stdc++.h>
using namespace std;

int main(){  
  int N;
  cin>>N;
  vector<vector<int>> G(N);
  vector<pair<int,int>> vp;

  for(int i=1;i<N;i++){
    int a,b;
    cin>>a>>b;
    a--;b--;
    G[a].emplace_back(b);
    G[b].emplace_back(a);
    vp.emplace_back(a,b);
  }
  int C[10010];
  int sum=0;
  for(int i=0;i<N;i++){
    cin>>C[i];
  }
  
  //最大スコア計算
  sort(C,C+N);
  for(int i=0;i<N-1;i++){
    sum+=C[i];
  }
  cout<<sum<<endl;
  
  //構築
  queue<int>que;
  que.push(0);  
  vector<int>ans(N,0);
  int k=N-1;
  int l;
  int qq;
  while(que.size()!=0){
    
    qq=que.front();
    que.pop();
    ans[qq]=C[k];
    k--; 
    l=G[qq].size();
    for(int i=0;i<l;i++){
      if(ans[G[qq][i]]==0){
        que.push(G[qq][i]);
      }
    }
  }
  for(int i=0;i<N;i++){
    cout<<ans[i]<<endl;
  }
  return 0;
}