10分求助

#include <iostream>
#include <vector>
using namespace std;

typedef long long LL;
const int N = 18, M = 1 << N;

int n, m, dep[M];
long long s[M][N];

void dfs(int x) {
	dep[x] = dep[x / 2] + 1;
	if (dep[x] == n) {
		for (int i = 1; i <= n; i++) s[x][i] = s[x][0];
		return;
	}
	dfs(x * 2), dfs(x * 2 + 1);
	for (int i = 1; i <= n; i++)
		s[x][i] = s[x][0] + s[x*2][i-1] + s[x*2+1][i-1];
}

long long query(int x, int y, int k) {
	if (x > y) swap(x, y);
	vector<int> gx, gy;
	while (dep[y] > dep[x]) gy.push_back(y), y /= 2;
	while (x != y) {
		gx.push_back(x), x /= 2;
		gy.push_back(y), y /= 2;
	}
	gx.push_back(x);
	for (int i = gy.size() - 1; i >= 0; i--)
		gx.push_back(gy[i]);
	int u, t;
	long long res = 0;
	if (gx.size() & 1) {
		t = gx.size() / 2, u = gx[t], t = k - t;
		if (t >= 0) res = s[u][min(t, n)];
	} else {
		t = gx.size() / 2, u = gx[t], t = k - t;
		if (t >= 0) res = s[u][min(t, n)];
		if (t > 0) res += s[u ^ 1][min(t - 1, n)];
		u /= 2, res += s[u][0];
	}
	for (int i = t; i && u / 2; i--, u /= 2) {
		res += s[u / 2][0];
		if (i > 1) res += s[u ^ 1][min(n, i - 2)];
	} 
	return res;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i < 1 << n; i++) scanf("%lld", &s[i][0]);
	dfs(1);
	while (m--) {
		int x, y, k;
		scanf("%d%d%d", &x, &y, &k);
		printf("%lld\n", query(x, y, k));
	}
	return 0;
}