Anxiety

lzh0613 · 2026-10-22 15:59:55 · 题解

下面令 \text{lca}(u, v) 表示 u 和 v 在树上的最近公共祖先。

容易发现题目给出的树是一棵层序遍历为 1, 2, \ldots, 2^n - 1 的树高为 n 的满二叉树。

对于每个点 u 可以 DP 出以 u 为根节点的向下的所有子树中距离 u 为 k 的节点权值总和。具体的，dp_{i, j} 表示在以 j 为根的向下的所有子树中距离 j 为 i 的节点权值总和，根据这棵树的性质，j 的左儿子（如果有的话）为 2 \times j，右儿子（如果有的话）为 2 \times j + 1，那么可以轻松的得到转移 dp_{i, j} = dp_{i - 1, 2 \times j} + dp_{i - 1, 2 \times j + 1} + w_j。

对于一个 u 和 v 之间的路径，满足树上与 u, v 两个节点的距离都不超过 k 的节点 p 的位置可以分成 3 类（假设这个 p 存在）。

这 3 类情况可以分别由 3 个循环完成，核心是差不多的。对于第一种情况，可以从 u 到 \text{lca}(u, v) 累加 dp_{k - \max(du, dv),u} - dp_{k - \max(du, dv) - 1,son}，其中 p 是路径上的点，du, dv 分别是 p 到 u, v 的距离，son 是上一个累加的节点（如果 p \ne u），减掉的目的是为了容斥，防止重复累加。

第二种情况和第一种差不多。第三种情况也差不多，但是需要注意的是因为 \text{lca}(u, v) 可能有 2 个儿子节点，可以单独容斥。

#include <bits/stdc++.h>
#define y0 sto_czx35_orz//防 CE
#define int long long
using namespace std;
const int N = 3e5 + 5;
int n, q, a[50][N], m;
int deep(int u) {return (int)log2(u) + 1;}
int qpow(int x) {
    if (x == 0) return 1;
    if (x == 1) return 2;
    int t = qpow(x >> 1);
    if (x & 1) return t * t << 1;
    return t * t; 
}
void dfs(int u) {
    if ((u << 1) > m) {
        for (int i = 1; i <= (n << 1); i++) {
            a[i][u] = a[0][u];
        }
        return ;
    }
    dfs(u << 1), dfs(u << 1 | 1);
    for (int i = 1; i <= (n << 1); i++) {
        a[i][u] = a[i - 1][u << 1] + a[i - 1][u << 1 | 1] + a[0][u];
    }
    return ;
}
int lca(int u, int v) {
    if (u > v) swap(u, v);
    for (int j = n; j >= 0; j--) {
        if (deep(v >> j) >= deep(u)) v >>= j;
    } 
    if (u == v) return u;
    for (int j = n; j >= 0; j--) {
        if ((u >> j) ^ (v >> j)) {
            u >>= j, v >>= j;
        }
    }
    return u >> 1;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> q; m = qpow(n) - 1;
    for (int i = 1; i <= m; i++) {
        cin >> a[0][i];
    }
    dfs(1);
    while (q--) {
        int u, v, k; cin >> u >> v >> k;
        k = min(k, n << 1);
        int lc = lca(u, v), p = u, ans = 0, son = 0;
        int du = 0, dv = deep(u) + deep(v) - (deep(lc) << 1);
        int dd = max(deep(u), deep(v)) - deep(lc);
        while (p ^ lc) {
            int res = k - max(du, dv);
            if (res >= 0) {
                ans += a[res][p];
                if (son ^ 0 && res > 0) {
                    ans -= a[res - 1][son];
                }
            }
            son = p, du++, dv--, p >>= 1;
        }
        int cu = son;
        p = v, son = 0, du = deep(u) + deep(v) - (deep(lc) << 1), dv = 0;
        while (p ^ lc) {
            int res = k - max(du, dv);
            if (res >= 0) {
                ans += a[res][p];
                if (son != 0 && res > 0) { 
                    ans -= a[res - 1][son];
                } 
            }
            son = p, du--, dv++, p >>= 1;
        }
        int cv = son;
        int res = k - max(deep(u) - deep(lc), deep(v) - deep(lc));
        if (res >= 0) {
            ans += a[res][lc];
            if (res >= 1) {
                if (cu) ans -= a[res - 1][cu];
                if (cv) ans -= a[res - 1][cv];
            }
        }
        p = lc >> 1, son = lc; int d = 1;
        while (p ^ 0) {
            int res = k - dd - d;
            if (res < 0) break; 
            ans += a[res][p];
            if (res > 0) ans -= a[res - 1][son];
            son = p, p >>= 1, d++;
        }
        cout << ans << "\n";
    }
    return 0;
}