題目鏈接：點擊查看

題目大意：給出一棵樹，問是否為斐波那契樹。斐波那契樹的定義是，樹的大小為斐波那契數列的其中一項，且可以通過刪除掉一條邊使其拆分的兩個子樹也為斐波那契樹

題目分析：需要觀察到，大小為 $fi{b}_i$ 的樹，分解成兩個子樹后，如果合法，那么需要分解成兩個大小分別為 $fi{b}_{i?1}$ 和 $fi{b}_{i?2}$ 的子樹

但上述分解方法存在著兩種分法，不過可以證明任意一種都是可行的

所以直接模擬就好了，初始時記得判斷一下 $n$ 是否為斐波那契項，然后每次用樹形 $dp$ 求一下子樹的大小，然后枚舉每條邊嘗試刪除，如果其中的任意一步都非法，那么直接輸出 $NO$ 即可

代碼：

// Problem: E. Fib-tree // Contest: Codeforces - Codeforces Global Round 13 // URL: https://codeforces.com/contest/1491/problem/E // Memory Limit: 256 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; vector<int>fib; vector<pair<int,bool>>node[N];//{to,ban} int sz[N]; void get_size(int u,int fa) {sz[u]=1;for(auto it:node[u]) {int v=it.first,ban=it.second;if(ban||v==fa) {continue;}get_size(v,u);sz[u]+=sz[v];} } void cut_edge(int u,int fa,int k,int& pu,int& pv,int& pk) {for(auto it:node[u]) {if(pu>0) {return;}int v=it.first,ban=it.second;if(ban||v==fa) {continue;}if(sz[v]==fib[k-1]||sz[v]==fib[k-2]) {pu=u,pv=v,pk=(sz[v]==fib[k-1]?k-1:k-2);return;}cut_edge(v,u,k,pu,pv,pk);} } void dfs(int u,int k) {if(k<=1) {return;}get_size(u,-1);int pu=0,pv=0,pk=0;cut_edge(u,-1,k,pu,pv,pk);if(!pu) {puts("NO");exit(0);}for(auto& it:node[pu]) {if(it.first==pv) {it.second=true;}}for(auto& it:node[pv]) {if(it.first==pu) {it.second=true;}}dfs(pv,pk);dfs(pu,pk==k-1?k-2:k-1); } void init() {fib.push_back(1);fib.push_back(1);for(int i=2;i<30;i++) {fib.push_back(fib[i-1]+fib[i-2]);} } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);init();int n;read(n);for(int i=1;i<n;i++) {int u,v;read(u),read(v);node[u].push_back({v,false});node[v].push_back({u,false});}int p=lower_bound(fib.begin(),fib.end(),n)-fib.begin();if(fib[p]!=n) {return 0*puts("NO");}dfs(1,p);puts("YES");return 0; }

總結

以上是生活随笔為你收集整理的CodeForces - 1491E Fib-tree(模拟)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。