Official Analysis (C++)

Solution 1: Euler Tour + Binary Lifting

Explanation

This problem requires supporting point updates and XOR path queries on a tree. We can perform an Euler Tour combined with a Fenwick tree to compute root-to-node XORs efficiently and binary lifting to find the Lowest Common Ancestor (LCA) of any two nodes.

Let $\texttt{in}[x]$ and $\texttt{out}[x]$ denote the entry and exit times of node $x$ during an Euler Tour. By storing each node's value $e_x$ at both positions $\texttt{in}[x]$ and $\texttt{out}[x]$ in the Fenwick tree, the prefix XOR up to $\texttt{in}[v]$ gives the XOR of all values on the path from the root to node $v$.

This works because nodes in the subtree of $x$ have entry times in the range $[\texttt{in}[x], \texttt{out}[x])$, so their root paths all contain $e_x$. We XOR $e_x$ at $\texttt{in}[x]$ to include it for the subtree, and XOR it again at $\texttt{out}[x]$ to cancel it out for nodes outside the subtree. This is possible due to XOR's self-inverse property.

Define $X(x)$ as the XOR of values from the root to node $x$. Then the XOR along the path between nodes $u$ and $v$ is:

$X(u)$ and $X(v)$ each include the path from the root to their LCA, which cancels out when XORed together. We must XOR in $e_{\text{lca}(u,v)}$ once to include the LCA node in the final result.

To update a node $x$ to a new value $e'_x$, we XOR the difference $e_x\oplus e'_x$ into both $\texttt{in}[x]$ and $\texttt{out}[x]$.

Implementation

Time Complexity: $\mathcal{O}((N+Q)\log N)$

Copy
#include <bits/stdc++.h>

#define MAXN 100005
#define bitinc(x) (x & -x)

using namespace std;

int n, arr[MAXN], bit[2 * MAXN + 5], in[MAXN], ot[MAXN], par[MAXN][22];
vector<int> adj[MAXN];
int timer = 1;

Copy
import java.io.*;
import java.util.*;

public class CowLand {
	static final int LOG = 18;

 	Code Snippet: Binary Indexed Tree (Click to expand)

	static ArrayList<Integer>[] adj;
	static int[] in, outTime, a;

Solution 2: Heavy-Light Decomposition

Explanation

We can also solve this using HLD. After decomposing the tree into heavy paths, we assign each node a position $\texttt{pos[node]}$ in a linearized array and store values at $\texttt{val[pos[node]]}$. Each heavy path is contiguous in this array, with $\texttt{tp[node]}$ storing the top of the heavy chain containing $\texttt{node}$.

For a path query between nodes $u$ and $v$, we repeatedly jump from the deeper node to the parent of its chain top until both nodes are on the same chain. At each step, we need to query the XOR of a contiguous segment of the linearized array. To achieve $\mathcal{O}(\log^2 N)$ complexity, we must use a data structure such as a segment tree (or Fenwick tree) to answer these segment queries in $\mathcal{O}(\log N)$.

Implementation

Time Complexity: $\mathcal{O}((N+Q)\log^2 N)$

Copy
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100005;

int n, q;