Water Tree

Source: Codeforces 343D

1. Read the problem and summarise the task requirements.
   • Try to keep your response to a couple of sentences.
   • Note that “children” is a poor translation; they mean “descendants” instead.

Let’s attempt some simplified versions of the problem.

2. Suppose there are no operations of type 2, so the only operations are filling a subtree and querying a vertex. How would you solve this problem?
   • Make use of a particular application of range trees that was exhibited in lectures.
3. Suppose there are no operations of type 1, so the only operations are emptying a node (and its ancestors) and querying a vertex. How would you solve this problem? Assume that the tree starts filled.

Let’s return to the original problem.

4. Now that we can track when a node has been filled or emptied, we still need a way to determine which one happened most recently. What additional information can we store to help us with this?

5. Design an algorithm to solve the problem.

6. Analyse the time complexity of your algorithm and estimate its running time.

7. Implement this algorithm in code.
   • Reflector:
     • What potential pitfalls can you think of?
     • Write some tests to check for these pitfalls.
   • Other group members:
     • Write a program which solves the problem.
   • Run your tests and debug if necessary.
8. Submit your program for judging!
   • Debug as required.