牛客编程巅峰赛S2第3场 - 青铜&白银&黄金 C Tree VI

根据题面，可以发现前面层都是完全二叉树，所以可以先预处理出，每一层的节点个数，然后一直往左生儿子，在加上当前节点后如果超过了总结点就返回，先序遍历是一直先往左走，所以需要预处理出当前节点之前的完全二叉树的节点个数，可以根据代码具体理解.

const long long N=1e5+10;
class Solution {
public:
    typedef long long ll;
    ll n=0;
    ll lim=0;
    ll cnt=0;
    ll tot=0;
    ll res=0;
    ll num[N];
    ll head[N];
    ll base[N],pre[N];
    struct Edge{
        int u,v;
    }edge[N<<1];
    void add(ll x, ll y) {
        edge[++tot].u=head[x];
        edge[tot].v=y;
        head[x]=tot;
    }
    void dfs(ll now, ll loc, ll fa, ll dep) {
        if(now!=1) {
            add(now, fa);
            add(fa, now);
        }
        for(ll i=1; i<=lim; ++i) {
            if(pre[dep]>=n || pre[dep]+lim*(loc-1)+i>n) return;
            dfs(++cnt,lim*(loc-1)+i,now,dep+1);
        }
    }
    void dfs_two(ll now, ll fa) {
        if(now!=1) res+=(num[now]^num[fa]);
        for(ll i=head[now]; i; i=edge[i].u) {
            int to=edge[i].v;
            if(to==fa) continue;
            dfs_two(to,now);
        }
    }
    ll tree6(int k, vector<int>& a) {
        n=a.size();
        lim=k*1ll;
        for(int i=0; i<n; ++i) num[i+1]=a[i]*1ll;
        pre[0]=base[0]=1;
        for(int i=1; i<=n; ++i) base[i]=base[i-1]*lim;
        for(int i=1; i<=n; ++i) pre[i]=pre[i-1]+base[i];
        dfs(++cnt,1,0,0);
        dfs_two(1,0);
        return res;
   }
};