备注：解题过程实录不是题解。它是做题过程中的思维草稿，可能比较语无伦次。
并且由于中途有中断（比如去上学），可能会有一些内容看上去“奇迹般地突然出现”。

原题链接

这是个什么玩意儿。即没有任何奶牛是另一个奶牛的前缀。

首先前缀具备偏序性质。是不是该考虑拓扑排序？

不过挂上 01 Trie 更好。这样获得一个简洁的模型：每个点走到它子树中的一个位置去，最终没有任何点的子树中有别的东西。

最小化走动的距离的和。

对于一个节点对应的子树，记“边缘节点集合”为：

  1. 如果这个节点上有奶牛（即有奶牛的 01 串是这个节点对应的 01 串），且子树中没有奶牛：包含它自己的集合。
  2. 如果这个节点的子树中是空的（即没有任何奶牛的 01 串在这个节点的子树中）：包含它自己的集合，但是有标记表明它是另一类节点。
  3. 其他情况：两个子树的边缘节点集合的并集。

（将 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;
}