题解

题意整理：

基本题意

​ 给出一棵大小为 $nn$n 的完全二叉树的前序遍历序列 $\left\{a_i\right\}\backslash \{a\_i\backslash \}${ai​} 。

​ 定义树上任意一条边，若其连接 $(u,v)(u,v)$(u,v) 两个点，则其边权为 $u\text{ xor }vu\backslash \; \backslash text\{xor\}\backslash \; v$u xor v （$\text{xor}\backslash text\{xor\}$xor 表示按位异或运算）。

​ 求所有边的边权和。

数据范围与性质

​ $1\le n\le 10^5,1\le a_i,k\le 10^{9}1\backslash le\; n\; \backslash le\; 10^5,\; 1\backslash le\; a\_i,k\; \backslash le\; 10^9$1≤n≤105,1≤ai​,k≤109 。

​ 完全二叉树的定义：若设二叉树的深度为 $kk$k ，除第 $kk$k 层外，其它各层 ($1～k-11～k-1$1～k−1) 的结点数都达到最大个数，第 $kk$k 层所有的结点都连续集中在最左边。

​ 注意，完全二叉树的形态只和结点个数有关。

​ 暂时只想到一个较为自然/简洁的做法。

解法一：二叉树堆式编号+遍历

【知识点】二叉树堆式编号

【算法】树的前序遍历

分析与算法描述

​ 当 $nn$n 确定了，整棵树的形态其实已经确定了。

​ 那么我们只需要在这棵树上进行一次前序遍历，对照着输入给出的序列，就可以知道哪些点之间有连边了。

​ 所以一个直观的做法是，先把这棵树造出来。

​ 但其实我们不需要用任何数据结构来存储这棵树，因为完全二叉树有一种性质非常优秀的编号方式：根结点为 $11$1 ，然后按照层次，从左到右编号。这样的编号规则下，编号为 $ii$i 的点，其父亲结点的编号是 $\lfloor \frac{i}{2}\rfloor \backslash lfloor\backslash frac\{i\}\{2\}\backslash rfloor$⌊2i​⌋ ，其左儿子的编号是 $2i2i$2i ，右儿子的编号是 $2i+12i+1$2i+1 。

​ 举个例子，对一个 $n=10n=10$n=10 的满二叉树编号（图1）。

​ 因此，我们不需要存储这些结点之间的父子关系就可以直接对这棵树做前序遍历了。

​ 对于这道题，我们采用如下算法：

• 根据上文的结点父子关系，前序遍历这棵树，即 $\text{dfs}\backslash text\{dfs\}$dfs 时处理当前结点后，先访问左儿子，再访问右儿子。如果左右儿子的编号大于 $nn$n 了，说明越界了不再递归。
• 在前序遍历的过程中，访问到第 $ii$i 个结点（注意不是结点 $ii$i ，是前序遍历的第 $ii$i 个结点），我们把输入数据的第 $ii$i 个数字 $a_{i}a\_i$ai​ 标记为结点 $ii$i 的点权，称为 $va{l}_{i}val\_i$vali​ 。
• 然后对于每个不为 $11$1 的结点，我们将它和父亲的点权 $valval$val 异或起来，累加入答案中。

​

​ 因为只需要遍历整棵树一次，时间复杂度 $O\left(n\right)O(n)$O(n) 。考虑完全二叉树的层数只有 $\lceil 2_{}n\rceil \backslash lceil\backslash log\_2\; n\backslash rceil$⌈log2​n⌉ 层，因此栈空间深度最大为 $O\left(2_{}n\right)O(\backslash log\_2\; n)$O(log2​n) ，因此空间复杂度 $O(n+\log n)O(n+\backslash log\; n)$O(n+logn) 。

​

参考代码

class Solution {
public:

    int n;//总结点个数
    int num;//计数器，用来表示遍历到第几个数了
    long long ans;//累加的答案
    int val[100001];//树上点权
    
    void dfs(int x,vector<int>& a)
    {
        if(x>n)
            return;//对于编号大于 n 的结点，在题目中的树上是不存在的，直接退掉。
        
        val[x]=a[num++];//遍历到了第 num 个结点，它的点权 val 就是输入数据中第 num 个数值。
        
        if(x>1)
            ans=ans+(val[x]^val[x/2]);//对于不为根的结点，统计它与父亲之间的边的贡献
        
        dfs(x*2,a);//递归，先左后右
        dfs(x*2+1,a);
    }
    
    long long tree5(vector<int>& a) {
        num=0;
        ans=0;
        n=a.size();
        dfs(1,a);//遍历一次即可得到答案。
        return ans;
    }
};

解法二：对二叉树堆结点的dfs序进行推导

【知识点】二叉树堆式编号，二进制

​ 基于方法一的分析，我们知道，只要找到每个结点自己的权值和其父亲的权值，就可以求解出答案了。

​ 方法一通过遍历树的办法确定了每个结点的 $dfsdfs$dfs 序，从而确定了每个结点的权值。而在这个方法中，我们将用数学计算求出每个结点的 $dfsdfs$dfs 序。

​ 我们还是考虑方法一中树的编号方式，根是 $11$1 号。编号为 $ii$i 的点，其父亲结点的编号是 $\lfloor \frac{i}{2}\rfloor \backslash lfloor\backslash frac\{i\}\{2\}\backslash rfloor$⌊2i​⌋ ，其左儿子的编号是 $2i2i$2i ，右儿子的编号是 $2i+12i+1$2i+1 。

​ 我们用 $dfn\left(i\right)dfn(i)$dfn(i) 表示结点 $ii$i 的 $dfsdfs$dfs 序。

​ 用 $Lr\left(i\right)Lr(i)$Lr(i) 表示结点 $ii$i 在其所在层的排名，比如 $Lr\left(3\right)=2,Lr\left(6\right)=3Lr(3)=2,Lr(6)=3$Lr(3)=2,Lr(6)=3 （见图2）

​ 可以发现 $Lr\left(i\right)=i+1-2^{\lfloor 2_{}i\rfloor }Lr(i)=i+1\; -\; 2^\{\backslash lfloor\backslash log\_2\{i\}\backslash rfloor\}$Lr(i)=i+1−2⌊log2​i⌋ ，这是因为每一层最左边的数字一定是 $22$2 的整数次幂。

​ 我们用 $Slr\left(i\right)Slr(i)$Slr(i) 表示结点 $ii$i 与其祖先的 $LrLr$Lr 值之和，于是有递推式 $Slr\left(i\right)=Slr(\lfloor \frac{i}{2}\rfloor )+Lr\left(i\right)Slr(i)\; =\; Slr(\backslash lfloor\; \backslash frac\{i\}\{2\}\backslash rfloor)\; +\; Lr(i)$Slr(i)=Slr(⌊2i​⌋)+Lr(i) 。

​ 我们要确定 $dfn\left(i\right)dfn(i)$dfn(i) ，就需要知道在遍历的的时候，有多少个点在 $ii$i 之前被遍历。

​ 我们统计这些点的数量，分为三个部分，如图3，以结点 $33$3 为例。

• 第一个部分，就是 $Slr(\lfloor \frac{i}{2}\rfloor )Slr(\backslash lfloor\; \backslash frac\{i\}\{2\}\backslash rfloor)$Slr(⌊2i​⌋) 。
• 第二个部分，从 $ii$i 所在层前面的 $Lr\left(i\right)-1Lr(i)-1$Lr(i)−1 个结点开始延伸，有若干层，其中每一层的结点是上一层的两倍。具体有多少层，可以直接根据树的高度和结点 $ii$i 所在的高度算出。
• 第三个部分，树最下面不满的一层，需要特殊判断一下。

​ 第一个部分直接递推求解。

​ 第二个部分可以这么算出：假设树满的层数是 $DD$D ，$ii$i 所在层数是 $d\left(i\right)d(i)$d(i) 那么这部分的值就是 $\left(Lr\right(i)-1)\times (2^{D-d\left(i\right)+1}-1)(Lr(i)-1)\backslash times\; (2^\{D-d(i)+1\}-1)$(Lr(i)−1)×(2D−d(i)+1−1) 。其中 $22$2 的幂次用位运算计算，是 $O\left(1\right)O(1)$O(1) 的。

​ 第三个部分可以这么算出：假设树满的层数是 $DD$D 那么，$ii$i 所在层数是 $d\left(i\right)d(i)$d(i) ，那么随着 $Lr\left(i\right)-1Lr(i)-1$Lr(i)−1 个点的延伸，最后一层本应该有 $2^{D-d\left(i\right)+1}2^\{D-d(i)+1\}$2D−d(i)+1 个结点，但是可能并不能取满，假设树最后一层（不满）有 $kk$k 个结点，第三部分的值就是 $\min (2^{D-d\left(i\right)+1},k)\backslash min(2^\{D-d(i)+1\},k)$min(2D−d(i)+1,k) 。

​ 三个部分之和，就得到了在 $ii$i 之前被遍历的结点数目，据此从输入数组中我们可以取出 $ii$i 的权值，这样，遍历一遍 $2～n2～n$2～n 计算 ${\sum }_{i=2}^{n}val\left(i\right)\text{ xor }val(\lfloor \frac{i}{2}\rfloor )\backslash sum\_\{i=2\}^n\; val(i)\; \backslash text\{\; xor\; \}\; val(\backslash lfloor\; \backslash frac\{i\}\{2\}\backslash rfloor)$∑i=2n​val(i) xor val(⌊2i​⌋) 。

参考代码

class Solution {
public:

    int n;//总结点个数
    int D;//树满的层数
    long long ans;//累加的答案
    int val[100001];//树上点权
    int Slr[100001];//辅助数组，记录结点i所在层以及其上层中比i先遍历的点个数(包括i自己)
    
    long long tree5(vector<int>& a) {
        ans=0;
        n=a.size();
        D=floor(log2(n))-1;
        if(n==1)return 0;// 特判边界情况
        
        for(int layer=0;layer<=D+1;layer++)//枚举树的层
        {
            int first = 1 << layer ;//这一层的第一个结点的编号
            for(int j=0;j+first<=n && j<first;j++)//遍历这一层的结点
            {
                int node = first + j;//当前处理的结点编号
                int dfn = Slr[node/2] 
                          + (j * ((1 << (D - layer + 1)) - 1)) 
                          + min(n + 1 - (1 << (D+1)) , j * (1 << (D - layer + 1)));
                //求出当前结点的dfn,三个部分求和
                Slr[node] = Slr[node/2] + j + 1;
                val[node] = a[dfn];//知道dfn了，就可以获取这个结点的权值了
                if(node > 1) ans += val[node] ^ val[node/2];//父结点的val已经计算出来了，直接计算答案。
            }
        }
        return ans;
    }
};

​ 该算法求解每个部分都是通过遍历所有结点做的，单个结点的计算是 $O\left(1\right)O(1)$O(1) 的，总时间复杂 $O\left(n\right)O(n)$O(n) 。由于对每个结点用到了常数个辅助数组，总空间复杂度 $O\left(n\right)O(n)$O(n) 。注意，此算法不需要用到超过常数级的栈空间。