「一本通 2.3 练习 4」背单词

形式化题目

给定 $n$ 个两两不同的字符串 $w_1, w_2, \ldots, w_n$ 。选择一个排列 $p_1, p_2, \ldots, p_n$ 作为填写顺序。对位置 $x$ 上的单词 $w$ ，记 $S(w)$ 为所有是 $w$ 真后缀的单词出现位置的集合，代价为

\text{cost}(w) = \begin{cases} n \times n, & \text{存在 } u \in S(w) \text{ 出现在 } x \text{ 之后},\\[2pt] x - y, & \text{所有后缀都在 } x \text{ 之前},\ y = \max S(w) \text{（无后缀时 } y = 0\text{）}. \end{cases}

求 $\sum_{i=1}^{n} \text{cost}(p_i)$ 的最小值。

约束： $1 \leqslant n \leqslant 10^5$ ，所有单词长度之和 $1 \leqslant \sum |len| \leqslant 5.1 \times 10^5$ ，单词均为小写字母且两两不同。

样例

输入为 a、ba。a 是 ba 的后缀，因此 a 必须先填：

填写顺序	位置 1 的代价	位置 2 的代价	总代价
`a`, `ba`（合法）	`a`：无后缀，代价 $1$	`ba`：最长后缀 `a` 在位置 1，代价 $2-1=1$	2
`ba`, `a`（非法）	`ba`：后缀 `a` 尚未填，代价 $n^2=4$	`a`：代价 1	5

反着填会让 ba 触发 $n^2 = 4$ 的惩罚，总代价反而更大。可见最优解一定让"所有后缀先于单词本身"。

正解

思路

第一步：为什么永远不该触发 $n \times n$

只要把单词按长度从小到大填写，长单词的所有后缀都更短、已经填完，所以这种顺序一定合法。合法顺序的代价最多是 $\sum_{x=1}^{n} x = \frac{n(n+1)}{2} < n^2$ （ $n \geqslant 1$ 时成立），比任何触发 $n \times n$ 的方案都便宜。因此最优解一定是合法序：每个单词都排在它所有后缀之后。

第二步：反转单词，让"后缀"变成"前缀"

$u$ 是 $w$ 的后缀，等价于 $\text{rev}(u)$ 是 $\text{rev}(w)$ 的前缀。把每个单词反转后插入字典树，那么 $w$ 的所有后缀 = 树上从根到 $w$ 所在节点的路径上、所有"单词结尾"节点所代表的单词。后缀的偏序被字典树翻译成了树上祖先关系。

第三步：只留单词节点，得到一棵森林

路径上可能有许多"中转节点"（不是任何单词的结尾），它们对填写顺序毫无影响。对每个单词节点 $v$ ，让它连向路径上最近的单词结尾祖先 $p(v)$ （不存在就连向虚拟根 $0$ ）。因为"后缀的后缀还是后缀"，只要 $v$ 排在 $p(v)$ 之后就自动排在它所有后缀之后。

以 a、ba 为例，反转后得到 a、ab：

flowchart TD
    R(("0<br/>虚拟根")) --> N1["a ✓"]
    N1 --> N2["ab ✓"]
    style N1 fill:#d5f5d5
    style N2 fill:#d5f5d5

（✓ 表示单词结尾。）ab 的最近单词祖先正是 a，因此新树就是 0 → a → ab。a 是 ba 的后缀这件事，被准确记录成了父子关系。

第四步：代价公式化简

合法序下， $w$ 的所有后缀都在它前面。其中位置最大的那个后缀 $y$ 一定是最长的后缀（越长的后缀必须越晚填），也就是 $p(w)$ 。所以

\text{cost}(w) = \text{pos}(w) - \text{pos}(p(w)), \qquad \text{pos}(0) = 0.

整题变成：

在树上选择一个合法的 DFS 前序，最小化 $\sum_{v} \bigl(\text{pos}(v) - \text{pos}(p(v))\bigr)$ 。

第五步：贪心 —— 子树小的儿子先访问

每个节点都要为"自己与父亲之间的位置间隔"付费。把 $0$ 的每个儿子看成一件"任务"，任务耗时是它整棵子树的单词数。这和经典的排队接水完全同型：一个节点的所有儿子应当按子树大小升序访问。

交换论证：设相邻访问的两个兄弟子树为 $A$ 、 $B$ 。交换它们不影响两棵子树内部各节点的父子间隔，只影响 $A$ 之后所有兄弟子树的起点。若 $|A| \geqslant |B|$ ，交换后（ $B$ 在前）总代价变化为 $|B| - |A| \leqslant 0$ ，不会变差。反复交换即可把任意访问顺序整理成"大小升序"且代价不增。

于是最优顺序 = 树上按子树大小升序访问儿子的 DFS 前序。

样例推演

对 a、ba：a 的子树大小为 2，它是虚拟根唯一的儿子。

访问节点	位置 `pos`	父亲位置	代价
`a`（虚拟根的儿子）	1	0	$1-0=1$
`ab`（即 `ba`）	2	1	$2-1=1$
		总计	2

代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 13:24
# update_at: 2026-09-30 13:24

import sys

ROOT = 0    # 虚拟根：它不是一个单词，代表"没有任何后缀"的起点
BASE = 26   # 字母表大小，把 (节点, 字符) 压成一个整数键


def build_reversed_trie(words: list[str]) -> tuple[list[int], bytearray]:
    """把每个单词反转后插入字典树；反转后"后缀"关系变成"前缀"关系。

    返回每个节点的父节点 parent 与单词终止标记 is_end。
    节点编号沿插入路径严格递增，所以父编号一定小于子编号。
    """
    nxt: dict[int, int] = {}
    parent = [-1]
    is_end = bytearray(1)
    for word in words:
        node = ROOT
        for ch in reversed(word):                    # 插入反转串：单词的后缀成为树上的祖先
            key = node * BASE + ord(ch) - 97
            child = nxt.get(key)
            if child is None:
                child = len(parent)
                nxt[key] = child
                parent.append(node)
                is_end.append(0)
            node = child
        is_end[node] = 1
    return parent, is_end


def nearest_end_ancestor(parent: list[int], is_end: bytearray) -> list[int]:
    """每个节点最近的"单词终止"祖先，没有则挂在虚拟根 0 上。

    节点编号父小于子，正序一趟即可用父亲的答案推出自己的答案。
    """
    up = [ROOT] * len(parent)
    for v in range(1, len(parent)):
        p = parent[v]
        up[v] = p if is_end[p] else up[p]
    return up


def greedy_dfs_order(up: list[int], words_nodes: list[int]) -> int:
    """按"子树小的先填"的 DFS 前序排单词，返回 Σ(序号 − 父单词序号)。

    合法序下某个单词最后一个被填的后缀就是它的父节点，所以让每个词尽量靠近父亲，
    就是让每个节点的儿子按子树大小升序访问。
    """
    size = {v: 1 for v in words_nodes}               # 只统计单词节点，中转节点不计
    for v in reversed(words_nodes):                  # 逆序保证先算完儿子再算父亲
        p = up[v]
        if p in size:
            size[p] += size[v]

    children: dict[int, list[int]] = {ROOT: []}
    for v in words_nodes:
        children.setdefault(up[v], []).append(v)
    for kids in children.values():
        kids.sort(key=size.__getitem__)              # 子树小的先访问

    ans = 0
    pos = 0                                          # 已填单词数，也是下一个词的序号
    stack = [(v, 0) for v in reversed(children[ROOT])]  # 根的儿子没有后缀，父亲序号视作 0
    while stack:
        node, parent_pos = stack.pop()
        pos += 1
        ans += pos - parent_pos
        stack.extend((kid, pos) for kid in reversed(children.get(node, ())))
    return ans


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    words = [next(data).decode() for _ in range(n)]  # 接下来 n 个 token 是单词

    parent, is_end = build_reversed_trie(words)
    words_nodes = [v for v in range(1, len(parent)) if is_end[v]]
    print(greedy_dfs_order(nearest_end_ancestor(parent, is_end), words_nodes))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 03:27
 * update_at: 2026-10-05 03:27
 */
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 510005; // 字典树节点上限：所有单词长度之和 + 1，再留少量余量
const int MAXW = 100005; // 单词数上限

int trie[MAXN][26];        // trie[u][c]：节点 u 走字符 c 到达的子节点；0 表示不存在，0 号节点就是根
int parent_node[MAXN];     // parent_node[v]：字典树上 v 的父亲节点
int up[MAXN];              // up[v]：v 在字典树上最近的“单词结尾”祖先；没有则为虚拟根 0
char is_end[MAXN];         // is_end[v]：v 是否是某个单词的结尾，只有 0/1，用 char 省内存
int word_node[MAXW];       // word_node[i]：第 i 个单词在字典树上的节点编号
int subtree_size[MAXN];    // subtree_size[v]：模型树上以单词节点 v 为根的子树里单词的个数（非单词节点为 0）
int order[MAXW];           // order[1..n]：单词节点按（父亲升序，同父亲按子树大小升序）排序的结果
int start_child[MAXN];     // start_child[u]：u 的儿子在 order[] 中的起始下标
int child_count[MAXN];     // child_count[u]：u 的儿子个数
int stack_node[MAXW];      // 迭代 DFS 栈：待访问的单词节点
ll stack_parent_pos[MAXW]; // 迭代 DFS 栈：对应节点父亲的序号，虚拟根的儿子记 0
char buf[MAXN];            // 读入单个单词的缓冲区
int n;
int node_total; // 当前用到的最大字典树节点编号，0 号是根

// 把单词 s 反转后插入字典树，返回它所在的节点编号。
// 反转后“后缀”变成“前缀”，单词的所有后缀就对应树上从根到该节点路径上的单词节点。
int insert_reversed(const char s[], int len) {
    int u = 0; // 从根出发
    for (int j = len - 1; j >= 0; j--) {
        int c = s[j] - 'a';
        if (trie[u][c] == 0) {
            node_total++;
            trie[u][c] = node_total;
            parent_node[node_total] = u;
        }
        u = trie[u][c];
    }
    return u;
}

// order 的排序规则：先按模型树上的父亲编号升序，同一父亲时按子树大小升序。
// 子树小的先访问，等价于“排队接水”的最优贪心。
bool cmp_word(int a, int b) {
    if (up[a] != up[b]) {
        return up[a] < up[b];
    }
    return subtree_size[a] < subtree_size[b];
}

void read_input() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> buf;
        int len = strlen(buf);
        int v = insert_reversed(buf, len);
        is_end[v] = 1;
        word_node[i] = v;
    }
}

void solve() {
    // 1. 求每个节点最近的“单词结尾”祖先。字典树上父亲编号一定小于儿子编号，正序一趟即可。
    for (int v = 1; v <= node_total; v++) {
        int p = parent_node[v];
        up[v] = is_end[p] ? p : up[p];
    }

    // 2. 自底向上累加模型树的子树大小。节点编号大的先算，保证儿子的规模先汇总到父亲。
    for (int v = 1; v <= n; v++) {
        subtree_size[word_node[v]] = 1;
    }
    for (int v = node_total; v >= 1; v--) {
        if (is_end[v]) {
            subtree_size[up[v]] += subtree_size[v];
        }
    }

    // 3. 每个单词节点连向它的最近单词祖先，得到模型树；把单词节点按（父亲，子树大小）排序。
    for (int i = 1; i <= n; i++) {
        order[i] = word_node[i];
    }
    sort(order + 1, order + n + 1, cmp_word);

    // 4. 排好序后同一父亲的儿子连续，扫描出每个父亲的儿子区间。
    int i = 1;
    while (i <= n) {
        int j = i;
        int p = up[order[i]];
        while (j <= n && up[order[j]] == p) {
            j++;
        }
        start_child[p] = i;
        child_count[p] = j - i;
        i = j;
    }

    // 5. 迭代 DFS 统计答案。压栈时按区间从大到小压，弹出时就变成子树小的先访问。
    int top = 0;
    for (int k = start_child[0] + child_count[0] - 1; k >= start_child[0]; k--) {
        top++;
        stack_node[top] = order[k];
        stack_parent_pos[top] = 0; // 虚拟根的儿子没有后缀，父亲序号视作 0
    }
    ll pos = 0; // 已填单词数，也是当前单词的序号
    ll ans = 0;
    while (top > 0) {
        int u = stack_node[top];
        ll parent_pos = stack_parent_pos[top];
        top--;
        pos++;
        ans += pos - parent_pos; // 合法序下代价 = 自己的序号 - 最近单词祖先的序号
        for (int k = start_child[u] + child_count[u] - 1; k >= start_child[u]; k--) {
            top++;
            stack_node[top] = order[k];
            stack_parent_pos[top] = pos;
        }
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

复杂度

设 $S = \sum |len|$ ，字典树节点数 $V \leqslant S + 1$ 。

时间：建树 $O(S)$ ；求最近终止祖先与子树大小均 $O(V)$ ；各节点对儿子排序总计 $O(n \log n)$ ；迭代 DFS $O(n)$ 。合计 $O(S + n \log n)$ 。
空间：邻接表与各数组共 $O(S + n)$ ；单键字典把 (节点, 字符) 压成整数，实测在 $n = 10^5$ 、 $\sum|len| \approx 5 \times 10^5$ 的数据上峰值内存约 64MB，低于 128MB。

总结

本题的完整链条是：

合法序一定优于触发 $n^2$ 的顺序 → 只需考虑"后缀先填"的顺序；
反转单词后建 Trie，后缀关系 = 祖先关系；
只保留单词结尾节点、连向最近的单词祖先，得到一棵树；
代价化简为 $\text{pos}(v) - \text{pos}(p(v))$ ，等价于"排队接水"；
按子树大小升序 DFS， $O(S + n\log n)$ 解决。

图示解析

下面用一个有分支的例子走通全流程。单词为 a、ba、ca、dba，反转后为 a、ab、ac、abd。

第一步：反转建 Trie，标出单词结尾节点（✓）与每个单词节点的最近单词祖先（虚线）。

flowchart TD
    R((root)) --> A["a ✓"]
    A --> B["ab ✓<br/>ba"]
    A --> C["ac ✓<br/>ca"]
    B --> D["abd ✓<br/>dba"]
    R -. "最近祖先=0" .-> A
    A -. "最近祖先=a" .-> B
    A -. "最近祖先=a" .-> C
    B -. "最近祖先=ba" .-> D

第二步：只保留单词节点并按最近祖先连边，得到模型树；括号内是子树大小。

flowchart TD
    V0(("0")) --> VA["a (4)"]
    VA --> VC["ca (1)"]
    VA --> VB["ba (2)"]
    VB --> VD["dba (1)"]

第三步：按子树大小升序 DFS。a 的儿子有 ca(1) 和 ba(2)，先访问小的 ca，再访问 ba，ba 之后才轮到 dba。

访问顺序	单词	$\text{pos}$	父亲位置	代价
1	`a`	1	0	1
2	`ca`	2	1	1
3	`ba`	3	1	2
4	`dba`	4	3	1
			总计	5

观察重点：把小的子树 ca 提前，可以让 ba 和 dba 这两个"大块"整体后移，反之则会让 ca 凭空多出与 ba 的间隔代价。这就是该贪心的直观来源。