题目描述高桥正在开发一个供公司内部使用的联系人列表系统。每个员工都有一个唯一的用户名但由于用户名较长他决定为每个员工分配一个缩写。公司有 $N$ 名员工其中 $i$ 名员工的用户名是一个由小写英文字母组成的字符串 $S_i$ 。对于每个员工 $i$ 我们会从他们的用户名 $S_i$ 中选择一个非空前缀并将其指定为缩写 $T_i$ 。也就是说 $T_i$ 必须是由 $S_i$ 的前 $1$ 至 $|S_i|$ 个字符组成的字符串。也允许使用整个用户名作为缩写。缩写赋值 $(T_1, T_2, \ldots, T_N)$ 必须满足以下无前缀条件- 无前缀条件对于任意两个不同的员工 $i, j$ ( $i \neq j$ )( $i \neq j$ ) 中 $T_i$ 不是 $T_j$ 的前缀且 $T_j$ 不是 $T_i$ 的前缀。这里如果 $|A| \leq |B|$ 和 $B$ 的第一个 $|A|$ 字符与 $A$ 匹配那么字符串 $A$ 就是字符串 $B$ 的前缀。其中当 $A B$ 时 $A$ 也是 $B$ 的前缀。因此根据无前缀条件也不允许有 $T_i T_j$ 为不同的雇员 $i, j$ $i \neq j$ 。如果存在有效的缩写分配高桥希望最小化缩写的总长度 $\sum_{i1}^{N} |T_i|$ 。如果存在有效的赋值则输出最小总长度否则输出 $-1$ 。解题思路问题转化每个员工需要选择一个自己用户名的非空前缀作为缩写且所有缩写之间不能存在前缀关系。核心观察如果员工A的用户名是员工B的用户名的真前缀那么必然无解。因为A可以选择的最短缩写是它自己的完整用户名长度为|A|而B的任何前缀都必须以A为前缀B的前缀至少包含到A的末尾这样就一定存在前缀关系。Trie树的构建将所有用户名插入到Trie树中其中每个节点代表一个字符串从根到该节点的路径is_end[u] true表示该节点对应的字符串是一个完整的用户名可行性判断对于每个用户名S检查其所有真前缀中是否存在另一个用户名如果存在则无解输出-1否则所有用户名之间没有一个是另一个的真前缀最小化总长度当可行性满足后我们需要为每个用户名选择一个满足条件的节点Trie中的某个节点且该节点是用户名路径上的节点使得总深度最小。贪心策略对于每个用户名选择尽可能浅的节点但该节点的子树中只能包含这一个用户名。推导如果某个节点v假设对应字符串P的子树中只包含一个用户名即cnt[v] 1那么该用户名可以选择P作为缩写且不会与其他用户名产生前缀冲突为了让每个用户名的缩写尽量短我们找最浅的满足cnt[v] 1的节点实现细节计算每个节点的cnt该节点子树中包含的用户名数量对于每个用户名对应的终端节点u沿着父节点向上找直到遇到cnt[v] ! 1的节点假设停在节点v那么该用户名的最佳缩写是v的一个子节点深度为depth[v] 1累加所有缩写的长度完整代码#includebits/stdc.h using namespace std; const int MAX 500010; int trie[MAX][26]; bool is_end[MAX]; int parentArr[MAX], depthArr[MAX], cnt[MAX]; int tot0; void insert(const string s) { int u 0; for (char ch : s) { int c ch - a; if (!trie[u][c]) { trie[u][c] tot; parentArr[tot] u; depthArr[tot] depthArr[u] 1; } u trie[u][c]; } is_end[u] true; } bool check(const string s) { int u 0; for (int i 0; i (int)s.size() - 1; i) { int c s[i] - a; u trie[u][c]; if (is_end[u]) return false; } return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin N; vectorstring str(N); for (int i 0; i N; i) { cin str[i]; insert(str[i]); } for (const string s : str) { if (!check(s)) { cout -1 \n; return 0; } } for (int i 0; i tot; i) { cnt[i] is_end[i] ? 1 : 0; } for (int i tot; i 1; --i) { cnt[parentArr[i]] cnt[i]; } long long ans 0; for (int u 0; u tot; u) { if (!is_end[u]) continue; int v u; while (v ! 0 cnt[v] 1) { v parentArr[v]; } ans depthArr[v] 1; } cout ans \n; return 0; }