本文共 1587 字，大约阅读时间需要 5 分钟。

Fib-tree

首先定义Fib-tree为节点个数为斐波那契数列，并且要么只有一个点要么可以被划分成两个Fib-tree。

然后给你一颗n\((n\le10^5)\)个点的树，判断它是否是一颗Fib-tree

然后考虑先判断这个树的节点个数是否是fib-tree，由于斐波那契数列是呈指数级增长，所以我们只需要预处理前几项即可。

然后考虑划分，首先划分的大小是唯一确定的。这是由于斐波那契数列的递推式决定的。

假如有另外一组解，那么必然有\(f_i-f_a>f_{i-1}(a<i-2)\)

可以进行\(dfs\)寻找有没有这样的子树大小为\(f_{i-1}或f_{i-2}\)然后进行递归即可，但是有一个问题就是可能存在有很多满足大小条件的子树，我们不知道哪个是可行的。然后这题有非常惊人的性质，就是如果存在可行方案，那么其他划分方案也是可行的，那么我们考虑证明。

如果这棵树存在两种划分方式，那么我们可以将树分解为三部分，大小分别为\(f_{i-1},f_{i-2},f_{i-2}\)那么这样我们发现如果选择一种划分方式，其中\(f_{i-1}\)的划分就可以割刚才的边。然后我们发现这是一个归纳的过程。如果对于大小为\(f_{i-1}\)的树满足，那么对于\(f_i\)的树就必然满足，因为如果其中一种满足条件，根据归纳划分为三部分的方式就必然是合法的，那么任意分割方案都是就都是合法的。

要大胆猜想性质！！！

#include
   
    #define LL long long#define V inline void#define I inline int#define FOR(i,a,b) for(register int i=a,end##i=b;i<=end##i;++i)#define REP(i,a,b) for(register int i=a,end##i=b;i>=end##i;--i)#define go(i,x) for(int i=hed[x];i;i=e[i].pre)using namespace std;inline int read(){	char x='\0';	int fh=1,sum=0;	for(x=getchar();x<'0'||x>'9';x=getchar())if(x=='-')fh=-1;	for(;x>='0'&&x<='9';x=getchar())sum=sum*10+x-'0';	return fh*sum;}const int N=2e5+9;int n,fib[39];struct lian{	int to,pre;	bool del;}e[N<<1];int hed[N],lcnt=1;V jlian(int x,int y){	e[++lcnt]={y,hed[x]};	hed[x]=lcnt;}int siz[N],tf,tx,tid;V getsiz(int x,int fa,int tar){	siz[x]=1;	go(i,x)	{		int to=e[i].to;		if(to==fa||e[i].del)continue;		getsiz(to,x,tar);		siz[x]+=siz[to];		if(siz[to]==tar) tf=x,tx=to,tid=i;	}}inline bool check(int x,int k){//	cout<<"check "<
    
     <<' '<
     
      <
      
       =2)fib[i]=fib[i-1]+fib[i-2];		if(fib[i]==n)k=i;	}//	cout<
       
        <
       
      
     
    
   

转载地址：https://www.cnblogs.com/dinlon/p/14507942.html 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！