I did a DFS and marked all the leaf nodes and stored in a map of int -> vector all the leaf nodes available in the current subtree.
By using prefix sum array we can find out the number of leaf nodes in the interval [l…r] in O(1)
For each query, I did a binary search on the distance between LCA and a leaf node in the current interval and for a particular distance I find it’s ancestor using DP (like in binary lifting). For that ancestor, the map will contain all the leafs present in that subtree. In that we can find the length of sub-array which contains values in the range [l…r] using BS again. If this subarray length and the number of leaves present in [l…r] are the same, then this current ancestor node is a candidate for the final answer. So I update the answer and check further for ancestor nodes with less distance in the BS.
I didn’t solve this problem within the stipulated time as I had some connectivity issues. Will this approach work ?
I solved this problem using segment tree and LCA.
Segment tree contained the LCA of nodes or -1 for non-leaf nodes.
After this, the queries were very simple.
Hey, can you give a bit more detail of this solution? Didnt get segment tree contained the LCA part…Also LCA was for multiple leaf nodes…how did u handle that??
I would solve this using sparse-table and LCA precomputation as you mentioned the starting time and the ending time.
You can compute the LCA for each subarray of leaves of size - powers of 2.
Lca[L][i] = lca(L, L + 1, …, L + (2^i) - 1)
Computing the answer would also be easy. lca(Lca[L][i], Lca[R - 2^i + 1][i]).
Yes, Define dp[i][j] as number of ways to organize activities in [1..i] with j^{th} activity on i^{th} day. The recurrence becomes: dp[i][j] = \sum\limits_{l=1}^{B_j}\sum\limits_{k=1}^{m} dp[i-l][k] - \sum\limits_{l=1}^{B_j}dp[i-l][j]. Basically consider the length of contiguous interval of j^{th} activity and you would arrive at this recurrence.
You can simplify this by defining pre[i][j] = \sum\limits_{l=1}^{i} \sum\limits_{k=1}^{j} dp[i-l][k]