## Editorial for Wesley's Anger Contest 1 Problem 4 (Hard Version) - A Red-Black Tree Problem

Remember to use this editorial

**only**when stuck, and**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.**Submitting an official solution before solving the problem yourself is a bannable offence.**Author:

Please refer to the original problem's editorial for the dynamic programming solution.

To speed up the solution, we can observe that when computing , we only need to consider and when and where is the size of the subtree of vertex .

It can be shown that the resulting time complexity is . Proof is left as an exercise to the reader. Hint: .

**Time Complexity:**

## Comments