题目

题目描述

紫雅拥有七彩的头发，身穿樱花色的七彩裙子，这种梦幻般的外貌自然能够吸引所有男人的目光
紫雅为了展示自己的才华，开始在这个国家跳起了芭蕾
已知这个国家的城市和道路刚好形成一颗完全二叉树，从位于根节点的城市开始广度优先依次将城市编号为$1\sim N$
紫雅在这个国家一共表演$M$天，每天会从某个城市开始，经过若干条道路（不会回头），从而到达某个城市进行芭蕾表演
每个城市都有人口数量$A_i$，紫雅希望知道，对于她这一天的行动，她所有可能表演的城市的人口之和为多少

输入格式

第一行$2$个正整数$N,M$
接下来$N$行每行$1$个整数$A_i$，为第$i$个城市的人口数量
接下来$M$行每行$2$个正整数$B_j, P_j$，表示第j天紫雅的起点城市的编号以及经过的道路的数量

输出格式

$M$行，每行$1$个非负整数$C_i$,为第$j$天所有可能表演的城市的人口数量之和
如果不存在这种城市，则答案为$0$

样例

样例输入

样例输出

0
18
27

数据范围与提示

样例解释

第一天：$1$号城市位于该树的根节点。不存在经过$3$条不重复的道路所能到达的城市
第二天：$4$号城市位于该树的叶节点，经过$2$条道路可到达$1$号城市和$5$号城市，故答案为$13+5=18$
第三天：$3$号城市位于$1$号城市的子节点处，经过$1$条道路可到达$1$号城市，$6$号城市和$7$号城市。故答案为$13+6+8=27$

数据范围

对于$50%$的数据：$1\leqslant N\leqslant 1023,1\leqslant M\leqslant 1000$
对于$100%$的数据：$1\leqslant N\leqslant 131071,1\leqslant M\leqslant 100000$，且$N=2t-1,t\in \N^+,1\leqslant Ai\leqslant 30000$

题解

设$f_{i,j}$为从$i$出发，往下走$j$步能到达的点的权值和，$g_{i,j}$为从$i$出发，往上走$j$步能到达的点的权值和
所以我们可以直接用DFS求$f$和$g$
最后的答案就是$f$、$g$的和了！

//班上某同学的代码，自己的代码太难解释了！
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>

using namespace std;

typedef long long ll;
const int maxn = 131072 + 10;
const int maxt = 32;

int n, m, t, dep[maxn + 5], len, maxlen;
ll f[maxn + 5][maxt + 5], g[maxn + 5][maxt + 5], a[maxn + 5], ans[maxn + 5][maxt + 5];

void dfs(int p) {
    if (p << 1 <= n) f[p][len] = f[p << 1][len - 1] + f[p << 1 | 1][len - 1];
    g[p][len] = g[p / 2][len - 1];
    if (len >= 2) g[p][len] += f[p ^ 1][len - 2];
    if ((p << 1) <= n) {
        dfs(p << 1);
        dfs(p << 1 | 1);
    }
}

int main() {
    int x, k;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]); f[i][0] = g[i][0] = a[i];
        dep[i] = log2(i) + 1;
    }
    t = log2(n + 1); maxlen = t * 2 - 2;
    for (len = 1; len <= maxlen; len++) {
        dfs(1);
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &x, &k);
        if (k > maxlen) printf("0\n");
        else printf("%lld\n", f[x][k] + g[x][k]);
    }
    return 0;
}