you can easily deduce that the solution is Dynamic Programming where dp[u] equals str[u]  +  the lexicographically minimum dp[v] where there is an edge going from u to v however doing that with strings will easily cause you a very shiny time limit exceeded.

so he is representing the string saved in dp[v] as a segment tree that carries the string hash of a range however finding the minimum between two strings is not that easy hence the hash comes into play he binary search the maximum prefix where hash1[x][0 -  > i] = hash[y][0 -  > i] now the next character should be the one you decide for which is less x or y.

but that is also going to give a very shiny memory limit exceeded before it gives you a time limit exceeded hence the use of persistent segment tree where you can say that tree[u] = update(tree[v]) this assigns the value of tree[v] to tree[u] with the modification that is add str[u] to segment tree of v