CSP-J 树与二叉树公式计算 题解

思路解析

这是一道“把理论公式写成程序”的题。做法是先读入查询类型，再用 if/else 判断属于哪一种公式。

核心公式：

• 树边数 = n - 1。
• 森林边数 = n - k。
• 二叉树第 k 层最多节点数 = 2^(k-1)。
• 高度为 h 的二叉树最多节点数 = 2^h - 1。
• 1-based 完全二叉树父节点 = i / 2。
• 完美二叉树高度为 h 时，叶子数 = 2^(h-1)。

注意：C++ 中 ^ 不是乘方，不能写 2^h 来表示 2 的 h 次方。

参考代码

#include<bits/stdc++.h>
using namespace std;
long long pow2(int x){
    long long ans=1;
    for(int i=1;i<=x;i++) ans*=2;
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin>>q;
    while(q--){
        string op;
        cin>>op;
        if(op=="TREE"){
            long long n; cin>>n;
            cout<<n-1<<"\n";
        }else if(op=="FOREST"){
            long long n,k; cin>>n>>k;
            cout<<n-k<<"\n";
        }else if(op=="LAYER"){
            int k; cin>>k;
            cout<<pow2(k-1)<<"\n";
        }else if(op=="MAXNODE"){
            int h; cin>>h;
            cout<<pow2(h)-1<<"\n";
        }else if(op=="PARENT"){
            long long i; cin>>i;
            cout<<i/2<<"\n";
        }else if(op=="FULLLEAF"){
            int h; cin>>h;
            cout<<pow2(h-1)<<"\n";
        }
    }
    return 0;
}