C题

一遍dfs赋值 一遍计算异或和
class Solution {
public:
    /**
     * 
     * @param k int整型 表示完全k叉树的叉数k
     * @param a int整型vector 表示这棵完全k叉树的Dfs遍历序列的结点编号
     * @return long长整型
     */
    #define ll long long
ll as[100010],b[100010];
ll kf,cnt=0,n;
void dfs(ll s) //先序遍历
{
    b[s]=as[cnt];  cnt 控制先序遍历下标
    cnt++;
    for(int i=-1*(kf-2);i<2;i++) 
    {
        ll pos=i+s*kf;
        if(pos<=n) dfs(pos);
        else break;
    }
}
ll dfs2(int s)
{
    ll ans=0;
    for(int i=-1*(kf-2);i<2;i++)
    {
        ll pos=i+s*kf;
        if(pos<=n) ans+=(b[s]^b[pos])+dfs2(pos);
        else break;
    }
    return ans;
}
    long long tree6(int k, vector<int>& a) {
        // write code here
    kf=k;
    n=a.size();
    ll res=0;
    for(int i=0;i<n;i++)
    as[i]=a[i];
    if(k==1)
    {
        for(int i=1;i<n;i++)
            res+=as[i-1]^as[i];
        return res;
    }
    else 
    {
        dfs(1);
        ll ans=dfs2(1);
        return ans;
    }
    }

};