### PROBLEM LINK:

**Author:** Vivek Bansal

**Tester:** Kush Khandelwal

**Editorialist:** Vivek Bansal

### DIFFICULTY:

EASY-MEDIUM

### PREREQUISITES:

Bitmasking , Dynamic Programming

### PROBLEM:

Given a complete binary tree where each node a color associate with it .

For each query U & K, determine what is the minimum level at which number of distinct color nodes is greater than or equal to K under

the subtree rooted at U . If number of distinct color nodes under the subtree (of node U) < K , output -1.

### EXPLANATION:

Since it’s a complete binary tree , then the number of levels in tree can be maximum LOG(N) = 17(approx)

where N = 10^5 in worst case.

Consider Node X and Level Y :

For a given node X and Level Y , we should know in O(1) that what is the number of distinct color nodes under the subtree

rooted at node X and upto Level Y .

This can be done simply with the help of dynamic programming and bitmasking.

Let’s say if you have the answer for the childs of a node X and you wish to contruct the DP[][] table for this node X .

Then , this could be computed for a given node while making dfs .

Now for answering an query U & K, Just iterate all the levels sequentially and break when number

of bit set in DP[U][level] becomes >= K . And if number of bit set is level < K till last level , answer -1.

### TIME COMPLEXITY:

O((N*LOG(N)) + (Q*LOG(N)))