Statement's second paragraph shows that Voldemort has to go from room having lowest energy(to which he arrived) to room having highest energy in a sorted manner. Hence first sort the energies in increasing order and take the sum of pairwise adjacent energies to get the answer.

Let f(i,x) be the maximum number of wands using which we can make a stick of length x using the types of sticks from type 1 to type i.Our answer is f(K,N). The recurrence can be written, f(i,x) = max(f(i-1,x), f(i-1,x-len[i])). Similarly for minimum g(i,x)=min(g(i-1,x),g(i-1,x-len[i])).

The intended solution was using Small to Large trick. We can maintain 2 maps for each vertex, one for storing the frequency of colors in its subtree, and second for storing the counts of colors that appear specific times. While merging the maps, we can use the Small to Large trick to reduce the complexity to O(n*log n).

Forgetting about the constraints, we can use binary search to find answer to 1st type of query. Applying binary search to each query won't pass the time limit. We can use Parallel Binary Search for this. Solution of second query can be found out by traversing the operations backwards and using disjoint set union.

We can solve this problem using Centroid Decomposition and BIT.

1. Find the centroid of tree.

2. Right now we are finding the value of min_in_path * max_in_path for all the paths passing through given centroid.(this can be done using BIT). Add this value to your final answer.

3. Remove the current centroid and recursively calculate the value of P for all the decomposed trees and add them to your answer.

[As simple as divide and conquer]

Now how to calculate the value of min_in_path * max_in_path for all the the paths passing through given centroid. Run a dfs from the centroid and store the minimum and maximum value from root node(centroid) to current node in a vector of pair.

Now the problem is reduced to :

Given a vector of pair find the summation of min(A[i].first, A[j].first) * max(A[i].second, A[j].second) for all pair i,j in the index of array. Think about it.

Hint : This is the right place to use BIT.

This was a game theory problem with range queries and use of trie to build a tree on which game will be played. The game is known as Hackenbush which is pretty famous.

Basically we have to build a forest of trees using given strings on which the game will be played. Each move is nothing but removing an edge from a tree which leads to removing its subtree which is not connected to the root anymore.

Each game is played on a range of trees where number of string used to construct it is less than k.

Step to proceed:

1. Build trie for all the strings with a particular id.

2. Build tree from each trie on which game is played.(Redundant)

3. Find grundy number for each each tree.

4. For each query construct a set S of grundy values of all trees where number of strings used to construct it is less than k in range l to r.

5. Let the xor of all the values in set S be g. Find the frequency of g in S.

Step 4 and 5 can be done using merge sort tree.(How ?)

Intended solution is to use Hashing. For Hash you can either use two primes or it can even be done using one prime(How ?).

Find the Hash for each K * K submatrix of matrix A save the count of each hash in map A.

Find the Hash for each K * K submatrix of matrix B save the count of each hash in map B.

Now to count total number of equal submatrix pairs iterate on each hash value and add the product of count of this hash in map A and map B to your final answer.

Solutions with a complexity of O(n * n * log(n*n)) , appropriate optimization and strong hash can pass all the test cases.

Break the summation into 2 parts.

1st part :- consider 2 cases :-

       when N is odd ==> 2^(N - 1)
       when N is even ==> 2^(N - 1) + C(N, N/2)/2
         C(N,N/2) can be easily calculated using Lucas Theorem

2nd part :- Fibonacci(n) using matrix expo

Sort the queries in reverse order. Store pairs of (A[i], i) in vector and sort the vector. Maintain a segment tree to answer queries of L to R (Refer to the problem http://www.spoj.com/problems/GSS1/). Initially Update all points of segment tree with K. For each query update only those points for which A[i] > Q[i].P. In this way only N updates will occur.

Sort the values on the basis of age . For each index a range is needed which can be calculated using binary search. For finding answer for a range construct a segment tree where each node contains 2 matrix M^S[i] and M^(S[i] — 2) where M represents the matrix constructed from recurrence for F(N). Merge operation can be find easily using these 2 matrix. The intended solution was to use diagonalization of matrix to find M^S[i] and M^(S[i] — 2).