How can I solve USACO 2011 Gold December Grass Planting Without Heavy-Light Decomposition (HLD)?

Revision en1, by vamaddur, 2017-07-02 18:29:43

Problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=102

Another user pointed out to me the similarity between this problem and one on the most recent January contest (http://www.usaco.org/index.php?page=viewproblem2&cpid=696). The latter problem can be solved using the combination of a preorder traversal and BIT.

I was wondering if it is possible to solve the former problem with a combination of a Segment Tree and DFS (closest possible method to a preorder traversal). The segment tree would use lazy propagation to update the range of edges, but I am not sure how to use a DFS in this situation.

Am I on a right track? If so, I would appreciate input on how to continue. If not, please point me to another possible solution

Please help, and thanks in advance!

Tags bit/fenwick tree, usaco, hld

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English vamaddur 2017-07-02 18:30:11 1 Tiny change: 'e solution\n\nPlease' -> 'e solution.\n\nPlease'
en1 English vamaddur 2017-07-02 18:29:43 884 Initial revision (published)