- Quiz
- AC
- 問題理解
- 読解に苦労したが、画像を見れば一発だろう(下記)
- 木をパスに分解する。各パスは互いに接している必要がある
- 解説
- これを考えると次数3以上の頂点が2つ以上あると「接せない異なる色のパス」ができてしまうのでNo
- それ以外の場合は次数3以上の頂点は高々1つで、そこから葉に向けてをパスにすれば条件を満たす
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
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;
}