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

Правка en2, от vamaddur, 2017-07-02 18:30:11

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!

Теги bit/fenwick tree, usaco, hld

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский vamaddur 2017-07-02 18:30:11 1 Tiny change: 'e solution\n\nPlease' -> 'e solution.\n\nPlease'
en1 Английский vamaddur 2017-07-02 18:29:43 884 Initial revision (published)