981C - Useful Decomposition

• Quiz
  • https://codeforces.com/contest/981/problem/C
• AC
  • https://codeforces.com/contest/981/submission/98427495
• 問題理解
  • 読解に苦労したが、画像を見れば一発だろう（下記）
  • 木をパスに分解する。各パスは互いに接している必要がある

• 解説
  • これを考えると次数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;
}