题目描述

难度分:$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;
}