Alternative editorial to 2019 USACO Gold February, Problem 1

Revision en2, by nsqrtlog, 2022-09-07 01:20:16

The official editorial is not asymptotically optimal and involves an advanced concept that usually does not appear in USACO Gold. I derived a relatively "low-tech" and faster solution, which I will describe below.


Problem link

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$$$.

Subtask 1

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)$$$ using a simple DFS, so the overall complexity of this subtask is $$$O(n+b(n)+q\cdot (1+c(n))$$$, where $$$b(n)$$$ is the pre-computation time of the LCA method we use, and $$$c(n)$$$ is the query

Tags usaco, segment tree, euler tour, lca

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en12 English nsqrtlog 2022-09-14 02:47:08 177
en11 English nsqrtlog 2022-09-07 05:33:35 397
en10 English nsqrtlog 2022-09-07 02:00:34 0 (published)
en9 English nsqrtlog 2022-09-07 01:59:58 50 Tiny change: 'oiler>\n\n\nThank ' -> 'oiler>\n\nThank '
en8 English nsqrtlog 2022-09-07 01:57:22 64
en7 English nsqrtlog 2022-09-07 01:53:46 25
en6 English nsqrtlog 2022-09-07 01:52:48 16 Tiny change: 'b19.html) is not as' -> 'b19.html) to this problem is not as'
en5 English nsqrtlog 2022-09-07 01:52:24 4 Tiny change: '------\n\n[Problem l' -> '------\n\n### [Problem l'
en4 English nsqrtlog 2022-09-07 01:49:32 168
en3 English nsqrtlog 2022-09-07 01:46:30 4736 Tiny change: 'e std;\n\n\n#defin' -> 'e std;\n\n#defin'
en2 English nsqrtlog 2022-09-07 01:20:16 1353 Tiny change: 'ion:**\n\n' -> 'ion:**\n\nfor the sake of convenience, let $\sum\limits_u^v$ denote '
en1 English nsqrtlog 2022-09-06 16:22:47 407 Initial revision (saved to drafts)