It caches every query. It seems that there could not be many distinct large queries.

for (i = p; i < q; i++) { if (f[w[z][i].second] == 0) { sum++; f[w[z][i].second] = 1; } }

In the worst case this part works (summary) in .

Sample:

K+M -> K+M-1 -> K+M-2 -> .... K

K -> 1,2,3, ..., K-1

K+1 -> some chain of length 1

K+2 -> some chain of length 2

...

K+M -> some chain of length M

Prove:

Each w[z][i] will be viewed at most times. To view it k times, we should ask about layer z from k different ancestors of w[z][i]. How to get k different pairs <p,q>? For each of these k ancestors we have to add a chain from it to layer z. Lengths of these chains will be at least 1,2, ... k. Sum is at most n. So k is at most .