2017/04/27 My regret in NOI2015


See Huffman coding
Let’s consider the K-ary condition.
First we choose K nodes with the smallest K values and then merge them into one. So the number of the nodes decreases by (K – 1).
But this may cause that there are less than K nodes at last, when (N – 1) % (K – 1) != 0. So we cleverly add some virtual nodes with value 0 to ensure the nodes can be merged into one.


There exist an R-similar pair of wines only when two suffixes’s LCP has length R, that is, in a suffix tree, two nodes’s LCA has depth R. So we just need to build the suffix tree and use dfs to solve the problem.
As for the suffix tree of a string, it is just the SAM of its reverse string.