A Perfect Binary Tree

This problem can be solved using Heavy-Light Trick. Let's consider H = 17. We will call the nodes having depth less than 10, heavy nodes. And the rest are light nodes.

Question 1: How can we efficiently calculate the count of a color in a subtree?

Answer: We can build an array from the pre-order traversal time. In this new array, all the nodes under each subtree will be continuous. Now if we store the traversal time of these nodes for each color separately in a vector, we can efficiently count the number of colors in a subtree. Per checking complexity is O(log (number of nodes) = O(H)).

There are 29 = 512 nodes on level 9. We can precalculate answer for these 5122 pairs of nodes. Then we can build answer for other pair of heavy nodes. It will take around (5123 × H) iterations.

For light-heavy or light-light pairs, we can iterate over the light subtree and make O(H) query to count the number of such colors on the heavy subtree.

Question 2: Can we improve the color checking complexity even more?

Answer: We can use another heavy-light trick on it. We will mark the colors heavy and light depending on their frequency. The colors having frequency more than Sqrt(N) will be heavy colors. We can precalculate the answers for heavy colors in Sqrt(N) × 2H complexity. And so now if we apply our previous vector method to count colors, none of the vectors will contain more than Sqrt(N) colors. Thus, our complexity per query will come down to O(log (sqrt(N))).

Overall Time Complexity: $O((N + Q) \times \sqrt{N} \times log(\sqrt N))$.