题解：Atcoder Weekday Contest awc0110 E - Abbreviation Assignment
题目描述
高桥正在开发一个供公司内部使用的联系人列表系统。每个员工都有一个唯一的用户名，但由于用户名较长，他决定为每个员工分配一个缩写。
公司有 $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_{i=1}^{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）累加所有缩写的长度
完整代码
#include<bits/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 tot=0; 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; vector<string> 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; }