Given a rooted tree with node weights, process queries that request the XOR sum of node weights within the first h layers of a specified subtree rooted at node x.

Algorithm Overview

An offline approach using depth-based tracking efficiently solves this problem. The key insight involves traversing the tree while maintaining a data structure that tracks XOR sums up to specific depths.

Key Components

• Depth Calculation: Each node x has a depth d(x) representing its distance from the root.
• Query Processing: For each query (x, h), we need the XOR sum of all nodes in x's subtree with depth ≤ d(x) + h.
• Offline Strategy: Pre-organize queries by their root node x and process them during a depth-first traversal.

Implementation Strategy

During DFS traversal:

1. Before processing node x's children, record the current XOR sum for depth d(x) + h for each query associated with x
2. Update the depth-indexed structure with x's weight at depth d(x)
3. Recursively process all children
4. After processing children, compute the answer for each query by comparing the new XOR sum with the pre-recorded value

This approach effective subtracts contributions from nodes outside x's subtree using XOR properties.

Code Implementation: Tree Array Approach

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_NODES = 1000005;
int node_count, query_count;
long long weights[MAX_NODES];
vector<int> tree[MAX_NODES];
int depth[MAX_NODES];

struct Query {
    int target_depth;
    int query_id;
};
vector<Query> queries[MAX_NODES];

long long depth_xor[MAX_NODES * 2];
long long subtree_xor[MAX_NODES];
long long results[MAX_NODES];

void process_tree(int current, int current_depth) {
    depth[current] = current_depth;
    
    // Store pre-traversal XOR values for all queries
    vector<long long> pre_values;
    for (auto &q : queries[current]) {
        pre_values.push_back(depth_xor[current_depth + q.target_depth + 1]);
    }
    
    // Update depth-based XOR structure
    depth_xor[current_depth] ^= weights[current];
    subtree_xor[current] = weights[current];
    
    // Process children
    for (int child : tree[current]) {
        process_tree(child, current_depth + 1);
        subtree_xor[current] ^= subtree_xor[child];
    }
    
    // Calculate results using XOR difference
    for (int i = 0; i < queries[current].size(); i++) {
        auto &q = queries[current][i];
        results[q.query_id] = depth_xor[current_depth + q.target_depth + 1] ^ pre_values[i];
    }
    
    // Final depth update
    depth_xor[current_depth] ^= subtree_xor[current];
}

int main() {
    cin >> node_count >> query_count;
    
    for (int i = 1; i <= node_count; i++) {
        cin >> weights[i];
    }
    
    for (int i = 2; i <= node_count; i++) {
        int parent;
        cin >> parent;
        tree[parent].push_back(i);
    }
    
    for (int i = 1; i <= query_count; i++) {
        int root_node, layers;
        cin >> root_node >> layers;
        queries[root_node].push_back({layers, i});
    }
    
    process_tree(1, 1);
    
    for (int i = 1; i <= query_count; i++) {
        printf("%.3f", results[i] / 1000.0);
        if (i < query_count) putchar('\n');
    }
    
    return 0;
}

Alternative Implementation: Depth-First with Array

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

const int MAXN = 1000005;
int n, m;
int node_weights[MAXN];
vector<int> children[MAXN];
vector<pair<int, int>> queries[MAXN];
long long answers[MAXN];
long long depth_sum[MAXN * 2];

void dfs(int u, int d) {
    for (auto &q : queries[u]) {
        answers[q.second] ^= depth_sum[d + q.first + 1];
    }
    
    long long subtree_total = node_weights[u];
    for (int v : children[u]) {
        dfs(v, d + 1);
        subtree_total ^= answers[v];
    }
    
    depth_sum[d] ^= subtree_total;
    
    for (auto &q : queries[u]) {
        answers[q.second] ^= subtree_total ^ depth_sum[d + q.first + 1];
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &node_weights[i]);
    
    for (int i = 2; i <= n; i++) {
        int p;
        scanf("%d", &p);
        children[p].push_back(i);
    }
    
    for (int i = 1; i <= m; i++) {
        int u, k;
        scanf("%d%d", &u, &k);
        queries[u].emplace_back(k, i);
    }
    
    dfs(1, 1);
    
    for (int i = 1; i <= m; i++) {
        printf("%.3f", answers[i] / 1000.0);
        if (i < m) putchar('\n');
    }
    
    return 0;
}

Both impelmentations achieve O(n) time complexity by leveraging depth-first traversal and XOR properties to efficiently compute subtree layer sums.