Introduction

At the time I am writing this, it seems that all accepted solutions to 786D - Rap God [this problem] use optimized O(n*q) algorithms, including the only accepted solution during the contest by jqdai0815. The editorial gives some hints on an algorithm with complexity O((n+q)*lg^3(n)), but nobody seems to have successfully implemented something like it. So I thought I'd give it a try today and after a lot of hard work, I got it accepted. My code can be found here: 25820897. Since I enjoyed solving this problem, and since I used a lot of different interesting techniques, I decided to share my approach to this problem in this blog.

Centroid decomposition

(just like in the editorial.)

We will decompose the tree using centroid decomposition. When processing a centroid, we will need to count for each query (that is in this subtree) the number of paths that pass through the centroid and are lexographically smaller than the query-path. Because of the way the centroid decomposition works, we will process each query at most a logarithmic number of times. Each time we process a query-centroid-combination, we will first compare the path of the query-startnode to the centroid (all paths that we need to count now start with this path) with the query-path (capped at the length of the first path). We will later see how to do this quickly. If they differ, we know that all or none of the paths from the query-startnode though the centroid are lexographically smaller than the query-path. If they are equal, things are a little more difficult. We now need to find where the remaining part of the query-path falls in the subtree of all paths rooted in the centroid, excluding the subtree of the query-startnode.

Trie rooted in centroid with binary search

(to sort paths starting in centroid and find the position of the remaining part of the query-path)

To find the position of a path in the subtree of all paths rooted in the centroid, we will first construct a trie from the centroid. Then walking this trie in-order will result in a sorted list of all paths rooted in the centroid. If we store all these paths in an array, we can use binary search to find the position of the remaining part of the query path. For this we again need to compare two paths in the tree. We will see later how to do this quickly.

Binary Indexed Tree

(to count only active nodes)

We only need to count paths in a different subtree than the subtree of the query-startnode. For this, we will use a binary indexed tree. Initally we start with all paths enabled, just before processing queries in a subtree we disable all paths in the subtree, and after processing queries in the subtree we re-enable all paths in the subtree. Then when we know the position of the remaining part of the query-path in list of all paths in the subtree, we can query the binary indexed tree for a prefix sum to obtain the number of paths that we need to count.

Ladder decomposition

(to decompose paths in O(lg(n)) strings)

During the algorithm, we frequently needed to compare the strings for two paths in the tree, and we need to be able to calculate this quickly. The editorial suggests using hashing for this, but we will use another technique. We will build a string S of linear size, such that each path can be decomposed into a logaritmic number of substrings of S. Then two paths can be compared as follows: split each path in a logarithmic number of substrings of S, compare the first parts of both lists (with length equal to the shorter of the two parts), if they differ we know the result, otherwise we continue with the remaining parts. We continue this way until we find a part that differs or we reach the end of one of the paths; in both cases we know the answer. Assuming we can compare two substrings of S in constant time, then comparing two paths using this algorithm takes only logarithmic time.

How should S look like so it has the above property? First build a ladder composition of the tree. The total sum of the sizes of all ladders will be at most 2*n. In S, store for each ladder the upward and the downward strings. Then the length of S will be at most 4*n. And each path in the tree can be decomposed into a logarithmic number of parts of a ladder (upward or downward) which correspond to a substring of S.

Suffix array and lcp array with sparse table range minimum query

(to compare strings)

To compare two substrings in S quickly, we can create a suffix array for S. The relative position of the startpoints in the suffix array of the two suffixes corresponding to the two substrings will then tell us which of the two suffixes comes first, and the minimum over the range in the corresponding lcp array will tell us if the prefixes of the two suffixes (the substrings) are equal or not. To be able to compare substrings in constant time, we should store their position in the suffix array and build a sparse table for rmq queries in the lcp array.

Suffix tree

(to create suffix array and lcp array)

There are other ways to do this, and you can even afford to use a somewhat slower algorithm, but I used my suffix tree library implementation to create the suffix array in linear time.

Conclusion

Like I said, I really enjoyed solving this problem. Sometimes it seemed like there was so much stuff to do, but when it all came together in the end it was a wonderful feeling. I want to thank PrinceOfPersia for creating this problem.

On a more critical note, I don't think its realistic to expect someone to implement something like this in a two hour contest. And it is very difficult to set the time limit so that these kind of solutions pass, but O(n*q) solutions don't. Because of these reasons, I don't think it was a good problem for a two hour contest.