代码求调

#include<bits/stdc++.h>
using namespace std;
#define MAXN (1<<20)
long long a[MAXN],sum;
long long f[MAXN][40];
int dep[MAXN],n,m;
bool is_L[MAXN];
#define ls(x)(x<<1)
#define rs(x)(x<<1|1)
void Init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=(1<<n)-1;++i)scanf("%lld",&a[i]),f[i][0]=a[i],sum+=a[i];
    for(int i=(1<<n)-1;i>=1;--i)for(int j=1;j<=n+1;++j)f[i][j]=f[i*2][j-1]+f[i*2+1][j-1];
}

void dfs1(int u,int fa){
    if(u>(1<<n)-1)return;
    is_L[ls(u)]=true;
    dep[u]=dep[fa]+1;
    dfs1(ls(u),u),dfs1(rs(u),u);
}

int GLCA(int x,int y){
    while(x!=y){
        if(dep[x]<=dep[y])swap(x,y);
        x/=2;
    }
    return x;
}


int dis(int x,int y){return dep[x]+dep[y]-dep[GLCA(x,y)]*2;}

long long sumk(int x,int k){
    long long re=0;
    for(int i=0;i<=min(18,k);++i)re+=f[x][i];
    return re;
}

long long Climb_up(int x,int k,bool s){
    if(k<0||x<=0)return 0;
    return a[x]+(s==1?sumk(rs(x),k-1):sumk(ls(x),k-1))+Climb_up(x/2,k-1,is_L[x]);
}

long long To_LCA(int p,int LCA,int x,int y,int k,bool s){
    if(p<=LCA)return 0;
    int d=max(dis(p,x),dis(p,y));
    if(d<=k)return a[p]+To_LCA(p/2,LCA,x,y,k,is_L[p])+(s==1?sumk(rs(p),k-1-d):sumk(ls(p),k-1-d));
    return To_LCA(p/2,LCA,x,y,k,is_L[p]);
}
bool Judge_L(int x,int to){
    if(x<to)return 0;
    if(x==to)return 1;
    return Judge_L(x/2,to);
}
long long ask(int x,int y,int k){
    if(k>=n*2)return sum;
    int LCA=GLCA(x,y),d=dep[x]+dep[y]-dep[LCA]*2;
    long long ans=0;
    if(max(dis(LCA,x),dis(LCA,y))<=k){
        ans+=Climb_up(LCA/2,k-max(dis(LCA,x),dis(LCA,y))-1,is_L[LCA]);
    }
    if(x==LCA)swap(x,y);
    ans+=To_LCA(x/2,LCA,x,y,k,is_L[x])+To_LCA(y/2,LCA,x,y,k,is_L[x]);
    ans+=sumk(x,k-d);
    if(x==y)return ans;
    if(LCA!=y)ans+=sumk(y,k-d);
    else {
        if(Judge_L(x,ls(y)))ans+=sumk(rs(y),k-d-1)+a[y];
        else ans+=sumk(ls(y),k-d-1)+a[y];
    }
    if(max(dis(x,LCA),dis(y,LCA))<=k&&LCA!=y)ans+=a[LCA];
    return ans;
}

int main(){
    Init();dfs1(1,0);
    while(m--){
        int x,y,k;scanf("%d%d%d",&x,&y,&k);
        printf("%lld\n",ask(x,y,k));
    }
    return 0;
}