CodeForces - 1491E Fib-tree(模拟)

题目链接：点击查看

题目大意：给出一棵树，问是否为斐波那契树。斐波那契树的定义是，树的大小为斐波那契数列的其中一项，且可以通过删除掉一条边使其拆分的两个子树也为斐波那契树

题目分析：需要观察到，大小为 $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(模拟)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。