备注：解题过程实录不是题解。它是做题过程中的思维草稿，可能比较语无伦次。
并且由于中途有中断（比如去上学），可能会有一些内容看上去“奇迹般地突然出现”。
原题链接
这是个什么玩意儿。即没有任何奶牛是另一个奶牛的前缀。
首先前缀具备偏序性质。是不是该考虑拓扑排序？
不过挂上 01 Trie 更好。这样获得一个简洁的模型：每个点走到它子树中的一个位置去，最终没有任何点的子树中有别的东西。
最小化走动的距离的和。
对于一个节点对应的子树，记“边缘节点集合”为：
如果这个节点上有奶牛（即有奶牛的 01 串是这个节点对应的 01 串），且子树中没有奶牛：包含它自己的集合。 如果这个节点的子树中是空的（即没有任何奶牛的 01 串在这个节点的子树中）：包含它自己的集合，但是有标记表明它是另一类节点。 其他情况：两个子树的边缘节点集合的并集。 （将 1、2 两个 case 合称原子子树）
将两类节点分开维护并按深度排序，从两类中的最浅点中抉择。这里可以考虑优先队列启发式合并。
之后，整个过程就转化为递归的类似树形 dp 的不断合并。
对于一个非原子子树（即除根节点外的其他点中有奶牛），考虑将根节点插入到子树中的某个边缘节点上。
注意被新节点插入之后空节点会转化为满节点。而满节点会转化为它的两个子节点。
满节点的代价是深度 +2，空节点的代价是深度。
一个重要的问题是，一个点上可能有多个奶牛。这也比较好解决：多次插入同样的节点即可。
而对于原子子树上的多个奶牛，可以先构造一个只有一个奶牛的原子子树，然后将剩余的节点变成插入过程。
一般来说，ad-hoc 题想到核心 idea 就过了。然而这个题考验精细实现和卡常。
如果你不使用指针，可能会多出许多不必要的拷贝，这样就会 TLE。换用 pbds 配对堆会 T 的更惨，也许是因为指针结构 copy 和 insert 的常数更大。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 #include <bits/stdc++.h> using namespace std; struct node { int cnt; node *left, *right; node() = default; } *rt = nullptr; void trie_insert(node *&p, const basic_string<char> &s, const int depth) { if (!p) { p = new node(); } if (depth == s.size()) { p->cnt++; } else { if (s[depth] == '0') { trie_insert(p->left, s, depth + 1); } else { trie_insert(p->right, s, depth + 1); } } } using set_t = priority_queue<int, vector<int>, greater<>>; int64_t ans = 0; void ins(set_t &f, set_t &e, int c, const int depth) { while (c) { if (f.empty()) { ans += e.top() - depth; f.push(e.top()); e.pop(); } else if (e.empty()) { const int x = f.top(); f.pop(); ans += x - depth + 2; f.push(x + 1); f.push(x + 1); } else { if (e.top() < f.top() + 2) { ans += e.top() - depth; f.push(e.top()); e.pop(); } else { const int x = f.top(); f.pop(); ans += x - depth + 2; f.push(x + 1); f.push(x + 1); } } c--; } } pair<set_t *, set_t *> query(const node *const p, const int depth) { // 前满后空 if (!p) { auto *q = new set_t(); q->push(depth); return {new set_t(), q}; } else { if (!p->left && !p->right) { auto *q = new set_t(), *tmp = new set_t(); q->push(depth); ins(*q, *tmp, p->cnt - 1, depth); return {q, tmp}; } else { auto [x,y] = query(p->left, depth + 1); auto [u,v] = query(p->right, depth + 1); if (x->size() < u->size()) { swap(x, u); } while (!u->empty()) { x->push(u->top()); u->pop(); } if (y->size() < v->size()) { swap(y, v); } while (!v->empty()) { y->push(v->top()); v->pop(); } ins(*x, *y, p->cnt, depth); return {x, y}; } } } int n; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 0; i < n; ++i) { basic_string<char> s; cin >> s; trie_insert(rt, s, 0); } query(rt, 0); cout << ans; return 0; }