kmjp's blog

競技プログラミング参加記です

Codeforces Global Round 13 : E. Fib-tree

気が付けば簡単なんだけどね…。
https://codeforces.com/contest/1491/problem/E

問題

木を成すグラフが与えられる。
このグラフがFib木か判定せよ。

Fib木の定義は以下のとおりである。

  • 頂点数が1である
  • 頂点数が2以上である場合、以下を満たす。
    • F(n)をn番目のフィボナッチ数とする。Fib木の頂点数がF(n)である場合、ある辺を切断して2つの連結成分に分けたとき、頂点数F(n-1)とF(n-2)のFib木に再帰的に分けられる。

解法

後者の条件について、辺の切断候補が複数ある場合、実はどこで切断してもよい。
それがわかると、木をDFSしてSubTreeがF(n-1)またはF(n-2)頂点になる辺でどん欲に分割し、再帰的に処理していこう。

int N;
set<int> E[202020];
int level[202020];
int F[50];
int U,V;

int dfs2(int cur,int pre,int L) {
	int C=1;
	FORR(e,E[cur]) if(e!=pre) C+=dfs2(e,cur,L);
	
	if(C==F[L-1]) U=cur,V=pre;
	if(C==F[L-2]) V=cur,U=pre;
	return C;
}


int dfs(int cur,int L) {
	if(L<=3) return 1;
	U=V=-1;
	dfs2(cur,cur,L);
	
	if(U==-1) {
		return 0;
	}
	E[U].erase(V);
	E[V].erase(U);
	int x=U,y=V;
	return dfs(x,L-1)&&dfs(y,L-2);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].insert(y-1);
		E[y-1].insert(x-1);
	}
	
	F[0]=F[1]=1;
	level[1]=1;
	for(i=2;i<=40;i++) {
		F[i]=F[i-1]+F[i-2];
		if(F[i]>N) break;
		level[F[i]]=i;
	}
	
	
	if(level[N]&&dfs(0,level[N])) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	
}

まとめ

貪欲でいいってのに気付きにくい。