[题解] Tree IV

60~70%

可以直接对整棵树进行Dfs，即从根结点1号点开始，若当前结点为，则递归搜索两个子结点、，然后暴力计算答案，时间复杂度为，根据语言选择的不同可能会有不同的得分。

100%

本题利用了两个性质，同时这也是完全二叉树最常用的两个性质：

• 若父结点为，则其两个子结点分别为、
• 每一层均有个结点

可以枚举深度，同时维护每一层结点的范围，分别记作和，此时，这一层答案为，然后求和即可。

注意到此题需要对进行取模，所以我们需要预处理出对的逆元，按照上述方法进行计算即可。

时间复杂度

参考代码：

class Solution {
public:
    typedef long long ll;
    const ll mod = 998244353;

    inline ll qpow(ll a, ll b) {
        ll ret = 1;
        while (b) {
            if (b & 1) ret = ret * a % mod;
            a = a * a % mod, b >>= 1;
        }
        return ret % mod;
    }

    long long tree4(long long n) {
        ll ans = 0, inv2 = qpow(2, mod - 2), l, r, dep;
        for (l = 1, r = 1, dep = 1; r <= n; ++dep) {
            ans = (ans + dep * ((l + r) % mod * (r - l + 1) % mod * inv2 % mod) % mod) % mod;
            l = r + 1, r = (r + 1) * 2 - 1;
        }
        ans = (ans + dep * ((l + n) % mod * (n - l + 1) % mod * inv2 % mod) % mod) % mod;
        return ans;
    }
};

有关逆元的使用方法，可以自行搜索学习，这里仅提供一个简单的解释：
在除法运算下，除以一个数字后进行取模，等价于乘以这个数字对模数的逆元然后再取模。