yukicoder : No.1719 Tree and Permutation

考察中心の問題。
https://yukicoder.me/problems/no/1719

問題

1～N番の頂点からなる木が与えられる。
1～NのPermutation Pのうち、以下を満たすものがあるか判定せよ。

• 1～Nのうち3要素(i,j,k)を選ぶと、以下の条件のうち少なくとも片方が成り立つ
  • 頂点i→頂点jのパス上に頂点kがない
  • 頂点P[i]→頂点P[j]のパス上に頂点P[k]がない

解法

葉が半分以上を占めていれば条件を満たす。
そうでない場合、鳩ノ巣原理の要領で考えると、頂点iも頂点P[i]も次数が2以上であるようなiが存在する。

その点iを削除したグラフを考えると、異なる連結成分中の点(x,y)に対し、P[i]がP[x]→P[y]のパス内にあってはならない。
とするとP[i]は葉でなければいけないが、そもそもこれは最初iを選んだ時の条件に反する。
よって、葉が半分以上の時条件を満たす。

int T,N;
int A[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) A[i]=0;
		FOR(i,N-1) {
			cin>>x>>y;
			A[x-1]++;
			A[y-1]++;
		}
		int leaf=0;
		FOR(i,N) if(A[i]==1) leaf++;
		if(leaf*2>=N) {
			cout<<"Yes"<<endl;
		}
		else {
			cout<<"No"<<endl;
		}
	}
	
		
}

まとめ

こういうのサクっと考察するの苦手。