Quiz
- https://atcoder.jp/contests/m-solutions2019/tasks/m_solutions2019_d
AC
- https://atcoder.jp/contests/m-solutions2019/submissions/25535678
解説
- 公式解説では大きい値から辺に設定し、辺を伸ばしていくdfs
- 逆に、葉から小さいコストのものから設定しても通るよね？と思ったのでやってみた
- 葉に1番小さいコストを設定して葉を消す。葉の親が新たな葉となったら、次のコストを割り当てる候補とする
感想
- 辺の削除をするので隣接リストをsetで持った
- 実装は手間がかかった。根からdfsできるならそちらの方がいい

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N;cin>>N;
    
    vector<set<ll>> se(N);
    VI deg(N);

    rep(i,N-1){
      ll a,b;cin>>a>>b;
      a--;b--;
      
      deg[a]++;
      deg[b]++;
      
      se[a].insert(b);
      se[b].insert(a);
    }
    
    // 葉に小さい方から入れていくのもOKだよね？
    VI C = loadV(N);
    SORT(C);

    // 葉
    set<ll> leafs;
    rep(i,N){
      if(se[i].size()==1)leafs.insert(i);
    }

    // 答えはこれに入れる
    VI Ans(N, -1);

    ll idx=0; // 次使うC

    while(leafs.size()){
      auto it = leafs.begin();
      ll leaf = *it;
      ll parent = *se[leaf].begin();
    
      Ans[leaf]=C[idx++];
      if(idx==N-1){
        // 最後の状態に注意
        break;
      }
      leafs.erase(leaf);
      se[parent].erase(leaf);

      // 新しく葉になったものがあれば追加
      if(se[parent].size()==1){
        leafs.insert(parent);
      }
    }

    // 1つだけ未設定の頂点があるので
    rep(i,N){
      if(Ans[i]==-1){
        Ans[i]=C[idx]; break;
      }
    }

    ll sum = SUM(C)-C.back();
    p(sum);
    print_vector(Ans);

    return 0;
}

2021-09-03

visual studio code (VSC) のターミナルで使うシェルを変更する

環境設定

元環境

Windows 10
Ubuntu (WSL)をVSCのターミナルから開いてg++などを使っている

2021/09/03

VSCを更新し、VSC内のターミナルを開いたらいつものLinuxシェルの動きではなくなった
PSと書いてあるのでPowerShellがデフォルト起動している
表示＞terminal ターミナル：規定のプロファイルの設定
- と移動し、WSLを既定とすれば元に戻すことができます

f:id:peroon:20210903194211p:plain