981C - Useful Decomposition

f:id:peroon:20201115190051p:plain

  • 解説
    • これを考えると次数3以上の頂点が2つ以上あると「接せない異なる色のパス」ができてしまうのでNo
    • それ以外の場合は次数3以上の頂点は高々1つで、そこから葉に向けてをパスにすれば条件を満たす
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;

    VI A(N-1);
    VI B(N-1);
    VI dim(N);
    rep(i,N-1){
      ll a,b;cin>>a>>b;a--;b--;
      A[i]=a;
      B[i]=b;
      dim[a]++;
      dim[b]++;
    }

    if(N==2){
      p_yes();
      p(1);
      p2(A[0]+1,B[0]+1);
      return 0;
    }
    
    ll over3_cnt=0;
    rep(i,N){
      if(dim[i]>=3)over3_cnt++;
    }
    if(over3_cnt>1)no();

    VI leafs;
    rep(i,N){
      if(dim[i]==1)leafs.push_back(i);
    }

    ll ma = MAX(dim);
    ll center = -1;
    rep(i,N){
      if(dim[i]==ma)center=i;
    }
    p_yes();
    p(leafs.size());
    for(ll leaf : leafs){
      p2(leaf+1, center+1);
    }

    return 0;
}