[题解] Tree VI_牛客博客

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

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

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

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

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

设当前节点为 $x$ ，它的所有儿子从左到右依次标号为 $(x-1)k+2,(x-1)k+3,...,(x-1)k+k+1$

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

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$

参考代码：

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 &lt;= 1; ++i) {
            if (x * k + i &lt;= n) {
                ++cnt;
                ans += (d[p] ^ d[cnt]);
                dfs(x * k + i, cnt);
            } else return;
        }
    }
    long long tree6(int K, vector&lt;int&gt; &amp;a)
    {
        n = a.size();
        k = K;
        for (int i = 0; i &lt; n; ++i)
        {
            d[i + 1] = a[i];
        }
        dfs(1, 1);
        return ans;
    }
};