http://mirror.codeforces.com/contest/827/submission/28492511 It runs faster even than some fft solutions.

n = 500000;
s[0] = 'V';
for (int i = 1; i < n; ++i) s[i] = i % 10 ? '?' : 'K';

And result is TL with more than 10s execution time.

Sorting 10⁶ ints (or chars) is usually fast enough in C++.

тоже самое для питона :( правда чуть пораньше — 53 и 58 тест

Maybe modulo operation"%" is very slow...

use vector<pair<int,int>> instead of vector<pair<int,string>> In pair<in,int> first is the start index of string and second is the string and store strings in vector

Also, don't do string tobe=v[i].second; it may give TLE

See discussion above.

Can you explain your idea a bit more?

It is guaranteed that... the sum of all k_i doesn't exceed 10⁶.

There can be at most 10⁶ values to scanf.

consider the case when |s|=10^6 and k=10^6 ...

And i don't think we need the whole thing with depths as it's pretty intuitive that when rehanging that path to root the diameter is not increasing.

Solution using centroid decomposition 28779873

Idea being: Find the centroid of current tree and lets call it C. Root the current tree on centroid C and lets call it T. Find all those bad-edges E such that C is the largest centroid lying on MST-path from E.u to E.v. This can be done by checking if E is connecting two different subtrees of T.

Consider the paths (C, E.u) and (C, E.v). Minimize the answer of all the MST edges lying on both the paths by E.w-1. (This will be like taking the minimum of prefix of some array with given value!).

Delete C from the tree and repeat the same process for all the new trees created.

actually it's possible to use S = 2520. it takes more time but still under a second.

can you please explain your approach a little more !

• assume that the original string is s and the query string is e , l is the start and r is the end of the segment that we have to compare.
• we can calculate the answer for every character i in e by simple iterate
• sumi = (s[l+i] == e[i]) + (s[l+i+|e|] == e[i]) + (s[l+i+2|e|] == e[i]) + (s[l+i+3|e|] == e[i]) + ... + (s[l+i+j |e|] == e[i]) .. and so on where l + i + j * |e| <= r , and finally the answer is the sum of these values..
• knowing that we have only four letters and 1 <= |e| <= 10 .. we can make things faster by calculating the partial sum in array d[n][4] .. for every i in s we store how many 'A' from i to n but instead of step one by one we need to step S by S .. like this: i, i + S, i + 2 * S, i + 3 * S... i + j * S and the same way we calculate how many 'T','G','C'.. where S is the segment size
• then to calculate the answer for every query we have to iterate only S where (r -l+1) > S.. and (r-l+1) where (r-l+1) <= S
• when (r-l+1) <= S we simply iterate and calculate the answer using naive approach
• when (r-l+1) > S we iterate only S step .. we know that for every i in s we have the number of occurrences of every character in ( i , i + S, i +2 S , i +3 S, i + j * S) from i to n , so we simply iterate over every character in e and sum these values for i , i + |e| , i + 2 * |e| , i + 3 * |e| , i + j * |e| , where j * |e| < S.
• we can notice that S must be a multiply of |e| .. and since 1 <= |e| <= 10, S could be 2520 it's a valid value because lcm(1,2,3,4,5,6,7,8,9,10) = 2520.
• for update we need to update d values at indices i,i+ S, i + 2 S,..., i + j S, where i + j S <= n, in the worst case it takes only n/S iterate which is almost 40 iterate.
• sorry for broken English it's not my native, and I hope that I explained my approach in a better way.