算法标签

树结构、子树查询、异或运算、二进制拆分、重链剖分（HLD）、动态规划

题解

问题分析

题目要求在有根树中处理多组查询，每组查询需计算某个节点的子树内，所有距离该节点不超过k的节点的(v_i XOR 距离)之和。核心挑战在于：

1. 树规模和查询量均高达1e6，需线性或近线性复杂度算法
2. 异或运算与距离相关，直接计算难以优化
3. 子树范围+距离限制的双重约束增加了处理难度

方法思路

1. 二进制拆分优化异或运算：

   • 异或的特性是每位独立计算，可按二进制位拆分处理
   • 对于每个二进制位i，计算该位对结果的贡献：count * 2^i，其中count是该位为1的次数

2. 重链剖分（HLD）思想：

   • 利用重儿子优化子树合并，减少重复计算
   • 对每个节点维护不同距离的信息，便于快速查询

3. 动态规划存储距离相关信息：

   • 对每个节点u和距离d，存储：
     • f[i][d]：距离u为d的节点中，第i位异或结果的总和
     • g[i][d]：距离u为d的节点中，第i位的贡献系数（用于快速计算范围和）

4. 二进制跳跃查询：

   • 利用二进制拆分思想，将k拆分为2的幂次之和，快速累加不同距离范围的贡献

代码解析

#include <bits/stdc++.h>
using namespace std;

#define QwQ01AwA return 0
using i64 = long long;
template <class T> void ckmax(T &x, T &&y) { x = max(x, y); }
template <class T> void ckmin(T &x, T &&y) { x = min(x, y); }

/* --------------- fast io --------------- */ // 快速IO实现，略去详细注释
namespace Fread { /* ... */ }
namespace Fwrite { /* ... */ }
#define getchar Fread :: getchar
#define putchar Fwrite :: putchar
namespace Fastio { /* ... */ }
#define cin Fastio :: cin
#define cout Fastio :: cout
/* --------------- fast io --------------- */

const int N = 1e6 + 5;
int n, q, w[N], son[N], dep[N], LG;  // son:重儿子, dep:子树深度, LG:二进制最大位数
vector<int> e[N];                    // 树的邻接表
vector<pair<int, int>> ask[N];       // 存储每个节点的查询(距离k, 查询id)

// 存储每个距离的异或贡献信息
struct Node {
    array<i64, 20> f;  // f[i]:第i位的异或结果总和
    array<int, 20> g;  // g[i]:第i位的贡献系数
} buc[2 * N], *now = buc, *dp[N];    // dp[u]:节点u的距离信息数组
i64 ans[N];                           // 存储查询结果

// 第一次DFS:确定重儿子和子树深度
void dfs(int u) {
    for (auto v : e[u]) {
        dfs(v);
        if (dep[v] > dep[son[u]])
            son[u] = v;  // 选择深度最大的子节点作为重儿子
    }
    dep[u] = dep[son[u]] + 1;  // 子树深度=重儿子深度+1
}

// 合并子树信息到父节点
void merge(int x, int y) {
    int i, p = 0;
    i64 s = 0;

    // 按二进制位合并距离信息
    for (i = 1; p + (1 << (i - 1)) - 1 < dep[y]; p += (1 << (i - 1)), i++) {
        s += dp[y][p].f[i - 1] + (1ll << (i - 1)) * (dp[y][p].g[i - 1] - dp[y][p + (1 << (i - 1))].g[i - 1]);
        dp[x][0].f[i] += s;
    }

    s += (1ll << (i - 1)) * dp[y][p].g[i - 1];

    // 处理剩余部分
    for (int j = i - 1; j >= 0; j--) {
        if (p + (1 << j) - 1 >= dep[y])
            continue;
        s += dp[y][p].f[j], p += (1 << j);
        s += (1ll << j) * dp[y][p].g[j];
    }

    // 补全更高位
    while (i < LG)
        dp[x][0].f[i] += s, i++;
}

// 第二次DFS:计算各节点的距离信息并处理查询
void rdfs(int u) {
    // 初始化当前节点的信息(距离为0)
    for (int i = 0; i < LG; i++)
        dp[u][0].f[i] = w[u], dp[u][0].g[i] = (w[u] >> i & 1) ? -1 : 1;

    // 处理重儿子
    if (son[u]) {
        dp[son[u]] = dp[u] + 1;  // 重儿子复用父节点的内存空间
        rdfs(son[u]);
        merge(u, son[u]);  // 合并重儿子信息

        // 更新贡献系数
        for (int i = 0; i < LG; i++)
            dp[u][0].g[i] += dp[son[u]][0].g[i];
    }

    // 处理轻儿子
    for (auto v : e[u]) {
        if (v == son[u]) continue;

        dp[v] = now, now += dep[v] + 1;  // 轻儿子分配独立内存
        rdfs(v);
        merge(u, v);  // 合并轻儿子信息

        // 更新不同距离的贡献
        for (int i = 0; i < dep[v]; i++) {
            for (int j = 0; j < LG; j++) {
                dp[u][i + 1].f[j] += dp[v][i].f[j];
                dp[u][i + 1].g[j] += dp[v][i].g[j];
            }
        }

        // 更新贡献系数
        for (int i = 0; i < LG; i++)
            dp[u][0].g[i] += dp[v][0].g[i];
    }

    // 处理当前节点的所有查询
    for (auto [k, id] : ask[u]) {
        ckmin(k, dep[u] - 1);  // 距离不能超过子树深度
        int p = 0;
        ans[id] = 0;

        // 二进制跳跃累加结果
        for (int i = LG - 1; i >= 0; i--) {
            if (p + (1 << i) - 1 > k) continue;
            ans[id] += dp[u][p].f[i];
            ans[id] += (1ll << i) * (dp[u][p].g[i] - dp[u][k + 1].g[i]);
            p += (1 << i);
        }
    }
}

signed main() {
    cin >> n;
    LG = min(20, __lg(n) + 1);  // 二进制最大位数(不超过20)

    // 读取节点权值
    for (int i = 1; i <= n; i++)
        cin >> w[i];

    // 读取树结构(2~n号节点的父节点)
    for (int i = 2, fa; i <= n; i++)
        cin >> fa, e[fa].push_back(i);

    // 读取查询
    cin >> q;
    for (int i = 1, x, k; i <= q; i++)
        cin >> x >> k, ask[x].push_back({k, i});

    // 第一次DFS确定重儿子和深度
    dfs(1);
    // 分配内存并第二次DFS计算结果
    dp[1] = now, now += dep[1] + 1;
    rdfs(1);

    // 输出所有查询结果
    for (int i = 1; i <= q; i++)
        cout << ans[i] << '\n';

    QwQ01AwA;
}

复杂度分析

• 时间复杂度：O(n log n + q log k)，其中log n来自二进制拆分，重链剖分使每个节点的合并操作摊还为O(log n)
• 空间复杂度：O(n log n)，主要用于存储各节点不同距离的异或贡献信息

该算法通过二进制拆分优化异或运算，结合重链剖分减少子树信息合并的开销，高效处理了大规模的树查询问题。