### synths's blog

By synths, history, 7 months ago,

The official editorial to this problem is not asymptotically optimal and involves an advanced concept that's infrequent in USACO Gold. I managed to derive a relatively "low-tech" and faster solution, which I will describe below.

## Solution

for the sake of convenience, let $\sum\limits_u^v$ denote the XOR of all labels on the path from node $u$ to node $v$.

We want a way to efficiently calculate the XOR of every label along an arbitrary path without modifications. Note that after rooting the tree at an arbitrary root $r$, if we split a path by the LCA of its endpoints, this can be computed alongside binary-jumping LCA, but that approach can't be easily transferred to subtask 2.

The key observation is that, since XOR is an involution, if we take the XOR of $\sum\limits_u^r$ and $\sum\limits_v^r$, nodes that are on both paths will not contribute. By definition, these are exactly the common ancestors of $u$ and $v$, and almost all of them are nodes that we wouldn't want to count in the query!

Since the LCA is the only common ancestor of $u,v$ on the path between them, we can simply return $(\sum\limits_u^r\oplus\sum\limits_v^r)\oplus e_{\text{LCA(u,v)}}$ for each query. The "prefix sums" of labels can be pre-computed in $O(n)$ with any graph traversal algorithm, so the overall complexity of this subtask is $O(n+b(n)+q\cdot (1+c(n))$, where $b(n),c(n)$ are the pre-computation and query times of our LCA method, respectively.

Going further along the idea to keep track of paths sourcing from the root, for some arbitrary node $x$, which prefix sums will have to be updated if it is modified? The answer is exactly every node that has $x$ as an ancestor. This is the subtree of $x$ by definition, and subtree modifications are right up the alley of the Euler Tour technique!

If we establish an Euler Tour of the tree, we can effectively modify subtrees in $O(\log(n))$ with any data structure that supports range modification, such as a lazy propagation segment tree. However, note that when retrieving the answer, we only need to query two individual nodes, so it's sufficient to use a slightly modified version of an iterative segment tree due to Al.Cash, where a node keeps track of every update ever done over its corresponding segment, instead of the value of its corresponding segment; that way, to query a specific index, we can traverse along the path from it to the root of the segment tree, and their XOR is the current value of that index. A more detailed explanation of iterative segment trees and this specific trick can be found here.

(EDIT: it's also plausible to simply use a typical point-update range-query data structure on the difference array. Not sure why I didn't include that in my initial revision.)

Every technique used here can be found in multiple past USACO Gold problems (excluding range modification/point query, but that is a fairly natural extension of vanilla segment trees IMO), hence I consider my solution canonical to the gold division.

Time complexity: $O(n+b(n)+q\log(n))$.

My C++ code, which comfortably AC's, is shown below. Credits to Al.Cash once again for the segment tree implementation.

Click

Thank you for reading, and remember to praise the cows.

• +10