[题解] Tree VI

考察点：完全二叉树的含义及其推广，Dfs序列遍历顺序

需要理解完全二叉树的含义：即每个结点的子结点之多有两个子结点。

不妨我们先考虑最简单的一种情况，即结点编号按照一棵“标准”完全二叉树给出，即结点的两个子结点分别为与，根据这棵树，我们可以非常容易的用一次Dfs来“发掘”整棵树的构造。

由此，我们可以推广出完全叉树的含义：若设叉树的深度为，除第 层外，其它各层 (～) 的结点数都达到最大个数，第层所有的结点都连续集中在最左边。

因此，我们可以根据和当前层结点与其父结点的关系推导出结点下标的编号:

设当前节点为，它的所有儿子从左到右依次标号为

然后依次计算出每个下标在Dfs序中的位置，然后计算加密后的答案即可。

时间复杂度，空间复杂度

参考代码：

class Solution
{
public:
    typedef long long ll;
    ll n, k, d[100010];
    ll ans = 0, cnt = 1;

    inline void dfs(ll x, ll p)
    {
        for (ll i = -k + 2; i <= 1; ++i) {
            if (x * k + i <= n) {
                ++cnt;
                ans += (d[p] ^ d[cnt]);
                dfs(x * k + i, cnt);
            } else return;
        }
    }
    long long tree6(int K, vector<int> &a)
    {
        n = a.size();
        k = K;
        for (int i = 0; i < n; ++i)
        {
            d[i + 1] = a[i];
        }
        dfs(1, 1);
        return ans;
    }
};