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!
I don't think it is very plausible to solve Grass Planting with a Segment Tree representing the nodes of the tree. In order to a segment tree to actually be useful, you usually want to update a small number of contiguous segments, or else the time complexity will be huge. For the problem in the January contest, the preorder traversal was done to be able to update all the children of a node at once (in one contiguous segment). However in this problem, you need to update paths from one node from another, and I believe it is impossible(at least according to my current knowledge) to maintain an ordering so that you can update all the nodes on the path at once or at least efficiently. Why not Heavy-Light Decomposition? Researching it would be useful in the future.
P.S. Though I think it is unlikely that another solution exists, I would also be very interested if there is a solution other than using Heavy-Light Decomposition.
Addition for a path a — b can be reduced to addition for path root — a. So the value added to edge par(x) — x : sum of all addition for path root — (some node in x's subtree). So the problem can be solved by dfs preorder + bit.
O.O (red coder!!)
Sorry, I don't really understand some parts of your solution. What is path root? How do we process the addition and queries by using BIT? Could I ask for some more details about your solution? Thanks :D
Say you have a path from A to B. Let L be the LCA of A and B. Notice we add one to the path from the root to A, and one to the path from the root to B. Then, we subtract two from the path from the root to L (it got added twice). Call this "increment A, increment B, decrement L (edit: twice — thanks pacu).
Now to query an edge, we simply want to know how many values in the subtree of this edge were "incremented" or "decremented". Then we can calculate its value.
Minor typo — I think you mean "decrement L twice."
Thanks — now corrected.
But how exactly should you increment the edges on the path by using the dfs preorder? The main solution does it by using Heavy-Light but I am not sure how to do the same thing with DFS and Segment Tree/BIT?
You can update node and query subtree in log(n) with BIT/preorder. This is standard (you can find on google). Basically you keep id[i] which is preorder id of i, and mx[i] which is biggest preorder id in i's subtree. All the descendants of i have preoder id 'x' such that id[i] <= x <= mx[i]. This means you can query it with a segment tree.
Then you just update +1 A, +1 B, -2 L. (So update id[A], id[B] and id[L] in your segment tree). You only update the node, not the edges. When you get a query, you just sum query [id[i], mx[i]] to find the value of nodes below the edge.
Oh I see! Thank you for pointing this out to me! Learn something new every day :D Thank you for helping out!
@gongy I understand the method for the most part, but there are two things that I would like to clear up:
1) Would we find mx[i] while doing the recursive preorder assignment?
2) How does the sum query [id[i], mx[i]] produce the patches of grass between two nodes? I am kind of confused about what "i" stands for in the query...
1) yeah, you do it at the same time as finding id[i]
2) the query is for number of patches on one edge, not a path.
@gongy
1) :)
2) I got that part, but what does "i" stand for in the query?
If the edge you query is a-b, i stands for the deeper node out of a and b.
@gongy
In the picture above, let's say I were to update the path from 4 to 5. That would mean that Node 2 would have a value of -2, and Nodes 4 and 5 would have a value of 1. Querying the number of patches on the Edge from Node 2 to Node 5 would give an answer of -2 + 1 + 1 = 0. Did I misunderstand the method, or did I make a miscalculation?
P.S. Thanks for sticking with me throughout my process of understanding the sol!
You query the edge from node 2 to node 5. Therefore we query with i = 5. So you add up all the values in the subtree of 5 (which is only 5). So you have answer of 1.
Oops, I forgot that. :(
Is there a way to prove that this works for edge queries? I proved why node queries work as a basis.
I don't understand what you mean. We only do node queries here. The problem gives you an edge but you only care about the deeper node in the edge.
OK, why do we care only about the deeper node every time?
You're counting the number of times an update path crosses the edge. This is the sum of values below the lower node...
Ah, I completely get it now. :)
Thanks for your help everyone (especially @gongy)! I ended up solving the problem with a BIT (as range updates were not actually necessary) and modified DFS.
If anyone would like to see my C++11 solution, PM me. :)