hackercupai/hackercup huggingface dataset:
Each trie node represents a distinct string \(s\), so the number of times that \(s\) will be present in a triplet of tries is independent of all other strings. This leads to the observation that the answer can be calculated independently over each string, as long as we know the number of occurrences of \(s\) across all tries.

Supposing a string \(s\) is in \(k\) tries, we like to know it's contribution to the answer: for how many out of all \(\binom{N}{3}\) possible triples of tries is it in at least one of the tries? The answer is \(\binom{N}{3}\) minus the number the number of triples that doesn't have this node in any of the three tries, equal to \(\binom{N - k}{3}\).

All that remains is computing each pair of \((s, k_s\)). We can use DFS across all \(N\) tries to build a "mega" trie consisting of all \(N\) tries overlayed on top of each other, with the count at each node of how many times the corresponding string appears. This running time of the DFS will be proportional to the total number of nodes. Finally, we can DFS again to walk the entire megatrie, adding the contribution of \(\binom{N}{3} - \binom{N - k}{3}\) to the answer for each \(k\).

Alternatively, we can hash all strings as we walk through all the tries, maintaining a table of the counts for each hash, calculating the answer at the end just the same.