基于稀疏表（Sparse Table）的节点与指定父节点求和问题

你的核心问题在于仅维护了祖先节点的稀疏表sTable，但没有构建对应的区间和稀疏表，同时query函数逻辑错误：未动态追踪当前节点位置，错误地重复累加或漏算节点值，导致求和结果不正确。

要高效计算节点及其k个父节点的数值和，需要在Binary Lifting基础上额外维护sumTable，其中sumTable[node][j]表示从node开始往上2^j个节点的数值总和（包含node自身）。通过二进制分解k+1（节点自身+k个父节点），就能快速累加对应区间的和。

class sumKnodes {
    vector<vector<int>> sTable;     // 存储2^j级祖先的稀疏表
    vector<vector<int>> sumTable;   // 存储从node往上2^j个节点的数值和
    vector<int> depth;              // 节点深度
    vector<vector<int>> adjacencyList; // 邻接表
    vector<int> values;             // 节点数值
    int LOG;                        // 最大二进制位数

public:
    sumKnodes(int N) : adjacencyList(N) {}

    void preProcess(int N) {
        LOG = 0;
        while ((1 << LOG) <= N) {
            LOG++;
        }

        // 初始化稀疏表和深度数组
        sTable = vector<vector<int>>(N, vector<int>(LOG, -1));
        sumTable = vector<vector<int>>(N, vector<int>(LOG));
        depth = vector<int>(N, 0);

        // DFS初始化一级祖先和一级和
        dfs(0, 0);

        // 动态规划构建高阶祖先和高阶和
        for (int j = 1; j < LOG; j++) {
            for (int i = 0; i < N; i++) {
                sTable[i][j] = sTable[sTable[i][j-1]][j-1];
                sumTable[i][j] = sumTable[i][j-1] + sumTable[sTable[i][j-1]][j-1];
            }
        }
    }

    // 按节点顺序添加数值（节点0对应第一个value，节点1对应第二个，以此类推）
    void addValue(int value) {
        values.push_back(value);
    }

    void addEdge(int u, int v) {
        adjacencyList[v].push_back(u);
        adjacencyList[u].push_back(v);
    }

    void dfs(int node, int parent) {
        sTable[node][0] = parent;
        sumTable[node][0] = values[node]; // 2^0=1，仅包含节点自身

        if (node != 0) {
            depth[node] = depth[parent] + 1;
        }

        for (int child : adjacencyList[node]) {
            if (child != parent) {
                dfs(child, node);
            }
        }
    }

    // 计算node及其parents个父节点的数值总和
    int query(int node, int parents) {
        // 总节点数：自身 + parents个父节点，最多不能超过从根到该节点的所有节点数
        int totalNodes = parents + 1;
        int maxPossible = depth[node] + 1; // 根节点depth为0，总节点数1
        if (totalNodes > maxPossible) {
            totalNodes = maxPossible;
        }

        int sum = 0;
        int currentNode = node;
        int remaining = totalNodes;

        // 二进制分解remaining，累加对应区间的和
        for (int j = LOG - 1; j >= 0; j--) {
            if (remaining >= (1 << j)) {
                sum += sumTable[currentNode][j];
                currentNode = sTable[currentNode][j]; // 跳到当前区间的下一个起点
                remaining -= (1 << j);
            }
        }

        return sum;
    }
};

1. 新增sumTable：

   • sumTable[node][0]初始化为节点自身的数值（对应2^0=1个节点）
   • 递推公式：sumTable[node][j] = sumTable[node][j-1] + sumTable[sTable[node][j-1]][j-1]，将2^j个节点拆分为两个2^(j-1)的区间求和

2. 重构query逻辑：

   • 计算需要求和的总节点数（自身+父节点数），并限制在合法范围内
   • 通过二进制分解总节点数，依次累加对应sumTable的区间和，同时动态更新当前节点位置，避免重复或漏算

3. 优化DFS初始化：

   • 在DFS中直接初始化sumTable[node][0]，简化后续操作

内容的提问来源于stack exchange，提问作者José Luis de Leòn