Can somebody explain how DSU on tree approach works . I couldn’t find much material on this topic . There is blog on codeforces by ARPA , but that blog talks much more on implementation rather than the idea .
1 Like
yeah same,i dont know how to transform a tree using dsu 
1 Like
thx :))
could you please tell me what is the “cache” array storing in the problem setter’s solution?
Can anyone tell me the test cases/situation for which my code is failing 2 TC’s (for partial). Tried brute force approach with hashing.
I used a slightly different (more complicated?) approach. Instead of building a new tree, I simulate the removal of nodes in the original tree.
Arbitrarily rooting the tree, for some operation on day i, I add the pair {a_i, i} to the highest ancestor of p_i that can be reached without crossing a previously blocked node. (This can be computed with binary lifting). The pair {a_i, i} means that this operation should be performed on the whole subtree, except for subtrees which were blocked previously, on some day before i.
Then we can get the answers with a DFS like in the editorial, maintaining a list of ancestors and their operations. However, before processing each node, we should have some way of ignoring all operations after the time where this node was blocked. We can do this by maintaining a segment tree that represents the ancestors, and for each node, we can build a new segment tree where some suffix is all zeros using persistence, so only log(n) new nodes are created.
Hopefully my solution is a little more clear:
https://www.codechef.com/viewsolution/36581652
Also, I thought of the editorial’s idea, but I didn’t think it would work because I didn’t realize the new tree doesn’t necessarily need to have the exact same edges as the original, since what’s really important is that the notion of connectedness is the preserved. Another good example of how starting from the end and adding edges can be more helpful than thinking about starting from the beginning and removing edges.
https://www.codechef.com/viewsolution/36684437
What is the error with my solution for the above problem , if I only aim for passing the subtask 1 ?
I Found somthing on youtube which is great.
3 Likes
Nice Editorial!!
@harshil21 can you tell the formation of second tree from first is a special technique Or it’s by observation only??
For me, Obervation / Intuition worked, as I worked on some cases and was able to see it.
Actually, the subtask should help you to find out the observation / intution much quicker.
Really loved your editorial!!!. Would be great if you guys could solve a test case by hand.
how can the subtask help to find the observation/intuition quicker?
https://www.codechef.com/viewsolution/37171143
I have implemented setters solution, but i can’t understand why i am getting wa
Just tell me the error , if instead of running the bfs and then clearing the source node vector and removing the source node from all other vectors in which it is present , I prefer to simply mark the source node as visited in my main after the bfs function so the next time the next source node goes through the bfs function it traverses only the nodes which are not visited ?
where’s the error ?
Just tell me the error , if instead of running the bfs and then clearing the source node vector and removing the source node from all other vectors in which it is present , I prefer to simply mark the source node as visited in my main after the bfs function so the next time the next source node goes through the bfs function it traverses only the nodes which are not visited ?
where’s the error ?
I using BFS and brute force approach for the first 30 points,but only two test cases are passing.
is my code wrong or only DFS can be applies here?