Alternative editorial to 2019 USACO Gold February, Problem 1

Revision en1, by nsqrtlog, 2022-09-06 16:22:47

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

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)