比赛时第一时间想到是dfs爆搜+统计,不出意外只拿了30。

代码如下

#include<bits/stdc++.h>
using namespace std;
int n,m,a[262145],x,y,k,mak[262145],ans[262145],sum;
void dfs(int u,int d){
	if(u>pow(2,n)-1) return ;
	if(d>k) return ;
	ans[u]+=1;
	if(ans[u]==2) sum+=a[u];
//	printf("%d %d\n",u,d);
	if(mak[u/2]==0&&u/2>0){
		mak[u/2]=1;
		dfs(u/2,d+1);	
	}
	if(mak[u*2]==0&&u*2<=pow(2,n)-1){
		mak[u*2]=1;
		dfs(u*2,d+1);
	}
	if(mak[u*2+1]==0&&u*2+1<=pow(2,n)-1){
		mak[u*2+1]=1;
		dfs(u*2+1,d+1);	
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=pow(2,n)-1;i++) scanf("%d",&a[i]);
	for(int i=1;i<=pow(2,n)-1;i++)ans[i]=log2(i)+1;
//	for(int i=1;i<=pow(2,n)-1;i++) printf("%d ",ans[i]);
	while(m--){
		sum=0;
		scanf("%d%d%d",&x,&y,&k);
		memset(ans,0,sizeof(ans));
		memset(mak,0,sizeof(mak)); 	
		mak[x]=1;
		dfs(x,0);
		memset(mak,0,sizeof(mak));
		mak[y]=1;
		dfs(y,0);
		printf("%d\n",sum);
	}
	return 0;
}

后来想了半天也找不到优化思路，唯一能想到的就是可能和树的深度有关。