気が付けば簡単なんだけどね…。
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; }
まとめ
貪欲でいいってのに気付きにくい。