PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
This problem is solved with such a data structure as a suffix automaton. Almost all AC solutions used the suffix automaton/tree data structure and had the following idea or someting very similar:
We have to build a suffix automaton on the given tree. If we have already built the suffix automaton on a tree, then the problem becomes quite standard:
- Count the number of paths in a directed acyclic graph
- Find the K-th path in a directed acyclic graph
It can be solved, for example, with a topological sort and a DP F[i] - the number of paths that begin in the vertex i. Obviously, F[i] is the sum of all F[x] such that there is an edge from i to x, plus one (to count the empty string too). Then, the answer to the first question is F[root] where root is the state that corresponds to the empty string. To answer the queries we can use a quite standard method: start from the empty string and then iterate through the letters of the alphabetical order in order that they are given to find the first letter. Then we can change our state and iterate again to find the second letter, etc.
Now, how to build the suffix automaton on a tree:
Let’s see how some standard building algorithm works. We have some states, each state corresponds to some set of strings and all the strings in one state are actually suffixes of some string. In the building algo we try to add the letters one-by-one to the previous state e.g. when we add the i-th letter, we try to add it to the state that corresponds to the (i-1) first letters of the string. But as we can see, transitions from any state by some letter (when we append it to some state) don’t depend on the transitions by other letters. So we can add not the only one (as in the standard algo), but several transitions from one state. Thus, to build the suffix automaton on a tree we only have to store the state that corresponds to the path from the root to the vertex. Then we can simply add a transition from the parent of some vertex to its son. The only (and obvious) requirement is that for every vertex before adding it we have to add its parent first. So, we have to “extend” our tree in a BFS or DFS order.
The writer’s implementation of such a solution worked for ~2 sec. on a single test case. There were a few solutions with another idea that produced correct answers but almost all of them got TLE during the contest. Generally, the TL was equal to 2*authors solution runtime.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.