968. Adding Up How Much Every Pair Shares

Given n words, add up, over every unordered pair of them, the length of the prefix those two words share. Print the total.

ab abc abd -> 6 each of the three pairs shares ab abc xyz pqr -> 0 aaa aaa aaa -> 9 three pairs, three letters each a ab abc abcd -> 10 1+1+1+2+2+3 over the six pairs

Check the last one by hand. The pairs and their shared lengths are (a,ab)=1, (a,abc)=1, (a,abcd)=1, (ab,abc)=2, (ab,abcd)=2, (abc,abcd)=3, which totals 10.

## The direct sum is out of reach

There are n (n - 1) / 2 pairs, which at n = 50000 is 1249975000, and each needs up to 50 character comparisons. That is over 6 * 10^10 comparisons.

## Count the pairs at each node instead of the letters at each pair

Problem 949 established that a node at depth d with cnt words below it is a prefix of length d shared by those cnt words. Turn that around:

· a pair of words shares a prefix of length L exactly when both of them pass through the L nodes at depths 1, 2, ..., L on their common path, and through no deeper common node · so the pair contributes exactly 1 to every node it BOTH passes through, and the number of such nodes is L

Therefore

total = sum over every non-root node v of cnt[v] * (cnt[v] - 1) / 2

because cnt[v] * (cnt[v] - 1) / 2 is the number of pairs that both pass through v, and summing over nodes adds 1 for each pair at each node they share, which is the pair's shared length.

Swapping the two summations, from "for each pair, how many nodes" to "for each node, how many pairs", is the whole idea, and it is the same move that turns O(n^2) counting problems into linear ones elsewhere in this bank.

build the trie with cnt[node] += 1 at every step of every insertion total = 0 for every node v other than the root: total += cnt[v] * (cnt[v] - 1) / 2

One pass over the nodes, and no pair is ever formed.

## Overflow, computed

This one genuinely needs 64 bits. The worst case allowed here is 50000 copies of a ten letter word, since the words total at most 500000 characters. Every one of the ten nodes then holds cnt = 50000, so

50000 * 49999 / 2 = 1249975000 pairs at each of 10 nodes total = 12499750000

and 12499750000 is about 5.8 times 2147483647, the largest signed 32 bit integer. A 32 bit accumulator wraps and prints a negative number.

The individual term cnt * (cnt - 1) / 2 is 1249975000 and does fit in 32 bits, which is what makes this easy to get wrong: the term looks safe, and the running total is not. Note also that cnt * (cnt - 1) before the division is 2499950000, which already exceeds INT_MAX, so the multiplication itself must be done in 64 bits rather than only the addition.

## Boundaries

A single word gives 0, because there is no pair. Two words sharing nothing also give 0, and 0 is a real answer rather than a failure. Equal words share their whole length, which the counting handles with no special case, since they walk the same nodes.

## Cost

Time O(total characters) to build plus O(nodes) to sum, at most 500001 nodes. Space is the trie.

Constraints - `1 ≤ n ≤ 50000` - Every word is 1 to 50 lowercase English letters. - The words total at most 500000 characters. - Words may repeat, and two equal words form a pair sharing their whole length.