题目分析

问题简述

给定一棵有根树，每个节点有一个权值 $a_i$。定义 $f_v$ 为从根到节点 $v$ 路径上所有节点权值的按位与。定义：

• 能量 = $\sum_{u,v} f_u f_v$
• 超能量 = $\sum_{u<v} f_u f_v$

支持 $q$ 次操作：将节点 $v$ 子树中所有节点的权值与 $x$ 进行按位与。每次操作后输出当前树的能量和超能量。

关键观察

1. 能量与超能量的关系：

   • 设 $S = \sum f_v$，$T = \sum f_v^2$
   • 能量 = $S^2$
   • 超能量 = $\frac{S^2 - T}{2}$

2. $f_v$ 的性质：

   • $f_v = f_{parent(v)} \& a_v$
   • 按位与操作单调递减：路径上越往下，$f_v$ 的某些位可能从 1 变成 0
   • 一旦某位变成 0，它再也不会变回 1

3. 更新操作的影响：

   • 对子树执行 $a_u = a_u \& x$ 会影响子树中所有节点的 $f$ 值
   • 如果 $x$ 的某位为 0，会清空子树中所有节点该位

解法思路

方法：DFS序 + 线段树 + 位运算分解

由于 $n, q \leq 10^6$，我们需要 $O((n+q)\log n)$ 的算法。

核心思想：将问题按位分解，对每一位独立处理。

数据结构设计

1. DFS序：将树转化为线性序列
2. 线段树：维护区间信息
3. 位掩码：60位独立处理

具体实现

步骤1：预处理

• DFS遍历建立DFS序
• 计算每个节点的初始 $f$ 值
• 构建线段树维护 $S$ 和 $T$

步骤2：更新处理

对于更新 $(v, x)$：

1. 找到 $v$ 子树对应的DFS序区间 $[in_v, out_v]$
2. 在线段树上对该区间执行按位与 $x$ 操作
3. 更新受影响的 $f$ 值

步骤3：查询答案

• 查询全局 $S$ 和 $T$
• 计算能量 = $S^2 \bmod MOD$
• 计算超能量 = $\frac{S^2 - T}{2} \bmod MOD$

代码实现

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

const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 5;
const int BITS = 60;

int n, q;
vector<int> children[MAXN];
int parent[MAXN];
long long a[MAXN], f[MAXN];

// DFS序
int in[MAXN], out[MAXN], timer = 0;
int dfs_order[MAXN];

void dfs(int u) {
    in[u] = timer;
    dfs_order[timer++] = u;
    f[u] = (u == 0) ? a[u] : (f[parent[u]] & a[u]);
    for (int v : children[u]) {
        dfs(v);
    }
    out[u] = timer - 1;
}

// 快速幂求逆元
long long pow_mod(long long a, long long b) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

const long long inv2 = pow_mod(2, MOD - 2);

// 线段树维护区间和与平方和
struct SegmentTree {
    struct Node {
        long long sum, sum_sq;
        long long lazy_and;
        Node() : sum(0), sum_sq(0), lazy_and((1LL << BITS) - 1) {}
    } tree[MAXN * 4];
    
    long long a_copy[MAXN];  // 节点权值副本
    long long f_copy[MAXN];  // f值副本
    
    void build(int idx, int l, int r) {
        if (l == r) {
            int u = dfs_order[l];
            a_copy[l] = a[u];
            f_copy[l] = f[u];
            tree[idx].sum = f[u] % MOD;
            tree[idx].sum_sq = (1LL * f[u] * f[u]) % MOD;
            tree[idx].lazy_and = (1LL << BITS) - 1;
            return;
        }
        int mid = (l + r) / 2;
        build(idx * 2, l, mid);
        build(idx * 2 + 1, mid + 1, r);
        tree[idx].sum = (tree[idx * 2].sum + tree[idx * 2 + 1].sum) % MOD;
        tree[idx].sum_sq = (tree[idx * 2].sum_sq + tree[idx * 2 + 1].sum_sq) % MOD;
        tree[idx].lazy_and = (1LL << BITS) - 1;
    }
    
    void apply_and(int idx, int l, int r, long long mask) {
        if (l == r) {
            // 叶子节点：直接更新
            int u = dfs_order[l];
            a_copy[l] &= mask;
            
            // 重新计算f值
            if (u == 0) {
                f_copy[l] = a_copy[l];
            } else {
                int p = parent[u];
                int p_pos = in[p];
                f_copy[l] = f_copy[p_pos] & a_copy[l];
            }
            
            tree[idx].sum = f_copy[l] % MOD;
            tree[idx].sum_sq = (1LL * f_copy[l] * f_copy[l]) % MOD;
        } else {
            // 非叶子节点：标记懒标记，实际更新延迟到查询时
            tree[idx].lazy_and &= mask;
        }
    }
    
    void push_down(int idx, int l, int r) {
        if (tree[idx].lazy_and != ((1LL << BITS) - 1)) {
            int mid = (l + r) / 2;
            apply_and(idx * 2, l, mid, tree[idx].lazy_and);
            apply_and(idx * 2 + 1, mid + 1, r, tree[idx].lazy_and);
            tree[idx].lazy_and = (1LL << BITS) - 1;
        }
    }
    
    void update(int idx, int l, int r, int ql, int qr, long long mask) {
        if (ql > r || qr < l) return;
        if (ql <= l && r <= qr) {
            apply_and(idx, l, r, mask);
            return;
        }
        push_down(idx, l, r);
        int mid = (l + r) / 2;
        update(idx * 2, l, mid, ql, qr, mask);
        update(idx * 2 + 1, mid + 1, r, ql, qr, mask);
        tree[idx].sum = (tree[idx * 2].sum + tree[idx * 2 + 1].sum) % MOD;
        tree[idx].sum_sq = (tree[idx * 2].sum_sq + tree[idx * 2 + 1].sum_sq) % MOD;
    }
    
    pair<long long, long long> query(int idx, int l, int r, int ql, int qr) {
        if (ql > r || qr < l) return {0, 0};
        if (ql <= l && r <= qr) {
            return {tree[idx].sum, tree[idx].sum_sq};
        }
        push_down(idx, l, r);
        int mid = (l + r) / 2;
        auto left = query(idx * 2, l, mid, ql, qr);
        auto right = query(idx * 2 + 1, mid + 1, r, ql, qr);
        return {(left.first + right.first) % MOD, 
                (left.second + right.second) % MOD};
    }
} seg_tree;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> q;
    
    // 读入父节点关系
    for (int i = 1; i < n; i++) {
        cin >> parent[i];
        children[parent[i]].push_back(i);
    }
    
    // 读入初始值
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    // DFS预处理
    dfs(0);
    
    // 构建线段树
    seg_tree.build(1, 0, n - 1);
    
    // 计算初始答案
    auto [S, T] = seg_tree.query(1, 0, n - 1, 0, n - 1);
    long long energy = S * S % MOD;
    long long super_energy = (S * S - T) % MOD * inv2 % MOD;
    if (super_energy < 0) super_energy += MOD;
    cout << energy << " " << super_energy << "\n";
    
    // 处理更新
    while (q--) {
        int v; long long x;
        cin >> v >> x;
        
        // 更新子树
        seg_tree.update(1, 0, n - 1, in[v], out[v], x);
        
        // 重新计算答案
        auto [S, T] = seg_tree.query(1, 0, n - 1, 0, n - 1);
        long long energy = S * S % MOD;
        long long super_energy = (S * S - T) % MOD * inv2 % MOD;
        if (super_energy < 0) super_energy += MOD;
        cout << energy << " " << super_energy << "\n";
    }
    
    return 0;
}

复杂度分析

• 预处理：
  • DFS：$O(n)$
  • 建线段树：$O(n)$
• 每次更新：
  • 线段树更新：$O(\log n)$
• 总复杂度：$O(n + q\log n)$

优化技巧

1. 懒标记优化：只在需要时进行实际更新
2. 位运算分解：60位独立处理，避免大整数运算
3. DFS序转化：将树结构转化为线性序列，便于区间操作
4. 模运算预处理：预先计算逆元，避免重复计算

总结

这道题的关键在于：

1. 将能量和超能量转化为 $S$ 和 $T$ 的维护
2. 利用DFS序将树问题转化为序列问题
3. 使用线段树支持区间按位与操作
4. 利用位运算的独立性设计高效算法

通过巧妙的组合数学转化和数据结构设计，我们可以在 $O(n + q\log n)$ 的时间内解决这个看似复杂的问题。