[题解] Tree I

考察点：完全二叉树的含义，Bfs序列遍历顺序

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

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

实际上，上述方法的结点编号即为所给出的Bfs遍历数组的下标（相当于是下标到结点编号的一个映射关系）。

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

时间复杂度，空间复杂度

参考代码：

class Solution {
public:
    int n, d[100010];
    long long ans = 0;

    inline void dfs(int x) {
        if ((x << 1) <= n) {
            dfs(x << 1);
            ans += d[x] ^ d[x << 1];
        }
        if ((x << 1 | 1) <= n) {
            dfs(x << 1 | 1);
            ans += d[x] ^ d[x << 1 | 1];
        }
    }

    long long tree1(vector<int>& a) {
        n = a.size();
        for (int i = 0; i < n; ++i) {
            d[i + 1] = a[i];
        }
        dfs(1);
        return ans;
    }
};