Hey guys!
I was having trouble solving milkvisits on the USACO gold contest. I solved it using heavy light decomposition, and I messed up on the implementation. I realize that you can solve this problem in a different, faster, and easier way, but I want to know what went wrong in my implementation. I looked at the test cases, but the smallest test case that I got a wrong answer on is of size 100, 000, so I had trouble visualizing the graph.
Here is my code, the input is in this google drive folder. I am supposed to output 1, but instead I am outputting 0. It would be of great help to me if you could tell me why my code is failing, and generally speaking, how you manage to debug problems with large inputs, if you use the inputs at all.
Thanks in advance.
in the editorial it was written that the queries can be done online also in O((N+M)log(N).probably they were referring to this HLD solution.Can you explain your solution once
Thanks
High Level Idea:
Any path between two nodes in a tree can be broken up into U->LCA(U,V) & V->LCA(U, V). Tree is a non linear data structure, we can convert them into smaller number of linear data structures (break them up) and we can use Segment Trees for those linear data structures to speed up queries. This is standard technique.
You use segment trees to maintain whether an id exists in this range. So, the path from U->LCA(U,V) will be a chain of segments. See if You can find the id exists in any of the range if so, output 1. If not, check V->LCA(U,V) as well. If id not found anywhere, then output 0.
Hope that helps.
In my implementation, i missed some corner case, hence failing for one query. It seems that corner case is in most of the test cases and failing the testcases. I'm just curious to find what i missed.
Cheers
Time complexity will be (M)*log^2N. Not sure if they refer to this solution in the editorial.