Simple And

Subtask 1: 1 ≤ N, Q ≤ 104

For this subtask, we only need the simple idea of DFS. At first from the root, we need to perform a DFS that determines the parent of every node. Then for each query (u, k) we need to perform another DFS from node u that goes to k’th depth in it’s subtree and calculate bitwise AND value.

Subtask 2: k ≤ 1

As previous subtask, at first from the root, we need to perform a DFS that determine the parent of every node. If k = 0 then answer will be number present in that node. If k = 1 then we just need to look at the adjacency list of node u and calculate bitwise AND value of every node in it except it’s parent node. We may need to save the previously calculated answers to avoid recalculating it. Otherwise, it may give TLE.

Subtask 3:

For the original subtask, we can use an idea called DSU on tree.

Firstly for every vertex v save all queries with this vertex. Then for every vertex, which is the root of it’s subtree make DFS, the parameters of DFS are vertex v and map<int,int>mp. This map contains for every depth i of the subtree of v, mp[i]= all the bitwise AND value on depth i.

This map could be calculated simply. Consider all sons of v and calculate such map for them. Obviously, the size of our map mp will be maximum of sizes of descendant’s maps. Then consider every descendant’s map and merge them. Of course, we will merge a smaller map to a larger map. After that, you should add the present node information of node v as mp[depth[v]] = value of that node.

After this, you can at once answer all queries of vertex v. Answer is -1 if v has no descendants on the depth k. The complexity of above algorithm is O(n log2n).