题目描述
难度分:$2400$
输入$n(1 \leq n \leq 2 \times 10^5)$和一棵树的$n-1$条边。节点编号从$1$开始。
定义斐波那契数列:
$f[0]=f[1]=1$
对于任意$n \geq 0$,$f[n+2]=f[n+1]+f[n]$。
定义斐波那契树:
- 树的顶点个数必须等于某个$f[k]$,
- 并且必须满足:要么只有一个点,要么可以通过删除一条边,分成两棵斐波那契树。
判断输入的树是否为斐波那契树。输出YES
或NO
。
输入样例$1$
3
1 2
2 3
输出样例$1$
YES
输入样例$2$
5
1 2
1 3
1 4
1 5
输出样例$2$
NO
输入样例$3$
5
1 3
1 2
4 5
3 4
输出样例$3$
YES
算法
递归
这个题的思路不是很难想到,但是实现方式确实没有见过,学习一下。
比较容易发现的是,一棵节点数为$f_k$的子树,一定要被分裂成节点数分别为$f_{k-1}$和$f_{k-2}$的子树,然后再检查这两棵子树是不是$Fib$树。因此可以枚举当前树的所有边,找到能够删除的边,然后递归被分裂的两棵子树,看是不是都满足$Fib$树的条件。
由于斐波那契数列每次元素至少都能增加两倍(实际上比两倍大),所以这个分裂过程最多持续$O(logn)$轮,这样做的时间复杂度为$O(nlogn)$。
对于递归函数$DFS(u,k)$,表示以$u$为根的子树是否能构成斐波那契数列的第$k$项($k$从$0$开始取值)。每次进入递归函数,先继续递归,暴力检查子树中是否存在一条边,使得把这条边断开后能够让两个子树的大小为$f_{k-1}$和$f_{k-2}$(详见代码中的$dfs2$函数)。能就记录这条边的两个端点$a$和$b$,然后继续递归$DFS(a,k-1)$和$DFS(b,k-2)$,只要这两个递归都返回true
,那以$u$为根的子树就是棵$Fib$树。
复杂度分析
时间复杂度
根据算法流程中的分析,整个算法的时间复杂度为$O(nlogn)$。
空间复杂度
树的邻接表空间复杂度为$O(n)$,递归深度在最差情况下也是$O(n)$。因此,算法整体的额外空间复杂度为$O(n)$。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 200010;
vector<PII> graph[N];
int n, del_edge, rk, node1, node2, sz[N];
bool vis[N];
const int fk[27] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418};
void dfs2(int u, int fa, int k) {
sz[u] = 1;
for(auto& pir: graph[u]) {
int v = pir.first, edge_id = pir.second;
if(v == fa || vis[edge_id]) continue;
dfs2(v, u, k);
if(~node1) break;
if(sz[v] == fk[k - 1] || sz[v] == fk[k - 2]) {
del_edge = edge_id;
node1 = u, node2 = v;
rk = (sz[v] == fk[k - 1]?k - 1: k - 2);
break;
}
sz[u] += sz[v];
}
}
// 检查以u为根的树是不是Fib树
bool dfs(int u, int k) {
// u是斐波那切数列的第k项
if(k <= 1) return true;
node1 = node2 = rk = -1;
dfs2(u, -1, k);
if(node1 == -1) {
// 没有找到能删的边,此时以u为根的子树不是Fib树
return false;
}else {
// 删除边del_edge,检查分裂出来的两棵子树是不是Fib树
vis[del_edge] = true;
int a = node1, b = node2, index = rk;
return dfs(b, index) && dfs(a, index == k - 1? k - 2: k - 1);
}
}
int main() {
scanf("%d", &n);
if(n == 1) {
puts("YES");
exit(0);
}
memset(vis, 0, sizeof(vis));
for(int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
graph[u].push_back({v, i});
graph[v].push_back({u, i});
}
int i = 0;
while(i + 1 < 27 && fk[i + 1] <= n) i++;
if(n != fk[i]) {
puts("NO"); // n就不是斐波那契数
exit(0);
}
puts(dfs(1, i)? "YES": "NO");
return 0;
}