奇特的猫

GitHub跳转原题关系图返回列表

每天的字符串集合是前缀封闭的,恰为一棵 Trie 的结点集;编辑距离就是树上距离。三天答案化为子树大小、换根距离和与一次 LCA 配对 DP。

OJ: roj

题目 ID: 1704

难度:提高+/省选-

标签:字符串Trie树形DP换根DPpython

创建: 2026-10-07 17:18

更新: 2026-10-07 17:18

形式化题目

键盘只有两种操作:敲一个字符(追加到串尾)、按退格(删除串尾一个字符)。三天各给出 一串按键(ASCIIASCII 值,退格是 88),记第 dd 天"屏幕上出现过的所有串(含空串)"为集合 SdS_d,即 A,B,CA, B, C。同一个集合内的距离为编辑距离

d(P,Q)=∣P∣+∣Q∣−2⋅LCP(P,Q),d(P, Q) = |P| + |Q| - 2 \cdot \mathrm{LCP}(P, Q),

其中 LCP\mathrm{LCP} 是最长公共前缀长度。LCP\mathrm{LCP} 的定义本身就说明 SdS_d 是前缀封闭的。

第 1 天:求 AA 内所有无序对的距离之和 W(A)W(A),最小值和最大值相同。

第 2 天:选定特殊串 A0∈AA_0 \in A、B0∈BB_0 \in B,规定跨集合的距离为 d(P,Q)=d(P,A0)+1+d(B0,Q)d(P, Q) = d(P, A_0) + 1 + d(B_0, Q)(P∈A,Q∈BP \in A, Q \in B)。求 ∑P∈A∑Q∈Bd(P,Q)\sum_{P \in A} \sum_{Q \in B} d(P, Q) 的最小值与最大值。

第 3 天:选定 A0∈AA_0 \in A、B0,B1∈BB_0, B_1 \in B(可相同)、C0∈CC_0 \in C,跨集合距离规定为

d(A,B)=d(P,A0)+1+d(B0,Q),d(B,C)=d(P,B1)+1+d(C0,Q),d(A,B) = d(P,A_0)+1+d(B_0,Q), \quad d(B,C) = d(P,B_1)+1+d(C_0,Q),
d(A,C)=d(P,A0)+1+d(B0,B1)+1+d(C0,Q).d(A,C) = d(P,A_0)+1+d(B_0,B_1)+1+d(C_0,Q).

求 ∑P∈A∑Q∈B+∑P∈B∑Q∈C+∑P∈A∑Q∈C\sum_{P \in A}\sum_{Q \in B} + \sum_{P \in B}\sum_{Q \in C} + \sum_{P \in A}\sum_{Q \in C} 的最小值与最大值。

输出三行,每行两个整数(该天的最小值与最大值)。

以样例 1 为例,三天按键分别是 97、97、97 8 97 8,于是 A={ε,a}A = \{\varepsilon, \texttt{a}\}、B={ε,a}B = \{\varepsilon, \texttt{a}\}、 C={ε,a}C = \{\varepsilon, \texttt{a}\}(第三个串敲 a、退格、再敲 a,集合没有新增元素)。 第 1 天 W(A)=d(ε,a)=1W(A) = d(\varepsilon, \texttt{a}) = 1;第 2 天取 A0=B0=εA_0 = B_0 = \varepsilon 时 A×BA \times B 四对距离之和是 1+1+1+3=61 + 1 + 1 + 3 = 6,但取 A0=B0=aA_0 = B_0 = \texttt{a} 时是 1010—— 无论怎么取都是 1010,故输出 10 10。

正解

思路

关键观察一:集合就是 Trie 的结点集。 光标永远在串尾,敲字符 = 从当前结点走一个孩子, 退格 = 回父结点。所以"屏幕出现过的串"就是走出来的所有结点,SdS_d 恰好是这棵 Trie 的 结点集合(含根 = 空串),而

d(P,Q)=∣P∣+∣Q∣−2 LCP(P,Q)=depth(P)+depth(Q)−2 depth(lca(P,Q))d(P, Q) = |P| + |Q| - 2\,\mathrm{LCP}(P,Q) = \mathrm{depth}(P) + \mathrm{depth}(Q) - 2\,\mathrm{depth}(\mathrm{lca}(P,Q))

正是树上距离。记 nd=∣Sd∣n_d = |S_d|,它就是 Trie 的结点数。于是三天的问题全部变成 树上距离的统计。

关键观察二:跨集合的那 11 个单位可以摊到每个串上。 第 2 天固定 A0,B0A_0, B_0 后

∑P∈A∑Q∈Bd(P,Q)=∑P∈A∑Q∈B[d(P,A0)+d(B0,Q)]⏟nB⋅DA[A0]  +  nA⋅DB[B0]+  nAnB, \sum_{P \in A}\sum_{Q \in B} d(P,Q) = \underbrace{\sum_{P \in A}\sum_{Q \in B}\bigl[d(P,A_0) + d(B_0,Q)\bigr]}_{n_B \cdot D_A[A_0] \;+\; n_A \cdot D_B[B_0]} + \; n_A n_B,

其中 DS[v]=∑u∈Sd(v,u)D_S[v] = \sum_{u \in S} d(v, u)。注意 AA、BB 内部的距离项一次都不出现: 第 2 天只统计 A×BA \times B 之间的对。

同理第 3 天的三项分别是

nBDA[A0]+nADB[B0]+nAnB⏟A×B,nCDB[B1]+nBDC[C0]+nBnC⏟B×C, \underbrace{n_B D_A[A_0] + n_A D_B[B_0] + n_A n_B}_{A \times B},\qquad \underbrace{n_C D_B[B_1] + n_B D_C[C_0] + n_B n_C}_{B \times C},
nCDA[A0]+nADC[C0]+nC⋅d(B0,B1)+2nAnC⏟A×C. \underbrace{n_C D_A[A_0] + n_A D_C[C_0] + n_C \cdot d(B_0,B_1) + 2 n_A n_C}_{A \times C}.

把固定项合起来,第 3 天的总距离为

base+(nB+nC)DA[A0]+(nA+nB)DC[C0]+nADB[B0]+nCDB[B1]+nAnC d(B0,B1)⏟只有这一项需要 B0≠B1, \mathrm{base} + (n_B+n_C)D_A[A_0] + (n_A+n_B)D_C[C_0] + \underbrace{n_A D_B[B_0] + n_C D_B[B_1] + n_A n_C\, d(B_0,B_1)}_{\text{只有这一项需要 } B_0 \ne B_1},
base=W(A)+W(B)+W(C)+nAnB+nBnC+2nAnC.\mathrm{base} = W(A) + W(B) + W(C) + n_A n_B + n_B n_C + 2 n_A n_C .

最小值把三个 DD 都取到各自的最小值即可,而 B0=B1B_0 = B_1 时最后一项退化成 (nA+nC)DB(n_A + n_C)D_B,正好是 min⁡DB\min D_B——所以

day3min=base+(nB+nC)min⁡DA+(nA+nB)min⁡DC+(nA+nC)min⁡DB.\text{day3min} = \mathrm{base} + (n_B+n_C)\min D_A + (n_A+n_B)\min D_C + (n_A+n_C)\min D_B .

(用一个恒等式可以自检:取 B0=B1B_0 = B_1 时括号里恰好还原成 (nA+nC)DB(n_A+n_C)D_B。)

关键观察三:三个基础统计量都是一次 DFS。 设结点数 nn、子树大小 sz\mathrm{sz}:

  • W=∑v≠rootsz[v]⋅(n−sz[v])W = \sum_{v \ne \text{root}} \mathrm{sz}[v]\cdot (n - \mathrm{sz}[v])——每条边 (p,v)(p,v) 恰好被 "一侧在子树内、一侧在子树外"的点对跨过;
  • D[root]=∑vdepth[v]D[\text{root}] = \sum_v \mathrm{depth}[v],换根 D[v]=D[p]+n−2 sz[v]D[v] = D[p] + n - 2\,\mathrm{sz}[v] (从父结点走进子树,子树内 nn 个点里有 sz[v]\mathrm{sz}[v] 个近了 11,其余 n−sz[v]n - \mathrm{sz}[v] 个远了 11);
  • min⁡D\min D、max⁡D\max D 扫一遍即可。

最大值里的配对项。 唯一麻烦的是第 3 天最大值的最后一项

max⁡x,y∈B[ nADB[x]+nCDB[y]+L d(x,y) ],L=nAnC.\max_{x,y \in B}\Bigl[\, n_A D_B[x] + n_C D_B[y] + L\, d(x,y)\,\Bigr], \qquad L = n_A n_C .

代入 d(x,y)=depth(x)+depth(y)−2 depth(lca(x,y))d(x,y) = \mathrm{depth}(x) + \mathrm{depth}(y) - 2\,\mathrm{depth}(\mathrm{lca}(x,y)),令

f[v]=nADB[v]+L depth[v],g[v]=nCDB[v]+L depth[v],f[v] = n_A D_B[v] + L\,\mathrm{depth}[v], \qquad g[v] = n_C D_B[v] + L\,\mathrm{depth}[v],

就得到 max⁡x,y[f[x]+g[y]−2L depth(lca(x,y))]\max_{x,y}\bigl[f[x] + g[y] - 2L\,\mathrm{depth}(\mathrm{lca}(x,y))\bigr]。 按 lca\mathrm{lca} 分类:对每个结点 vv 只统计"lca\mathrm{lca} 恰好是 vv"的配对,一共三种

  1. x=y=vx = y = v:值 f[v]+g[v]f[v] + g[v];
  2. 一端是 vv、另一端在某个孩子子树 cc 内:max⁡(f[v]+best1[c], best0[c]+g[v])\max\bigl(f[v] + \mathrm{best1}[c],\ \mathrm{best0}[c] + g[v]\bigr), 其中 best0[v]=max⁡u∈subtree(v)f[u]\mathrm{best0}[v] = \max_{u \in \text{subtree}(v)} f[u],best1\mathrm{best1} 同理对 gg;
  3. 两端分别在两个不同的孩子子树里:边合并边记"已合并子树的最值" (other0+best1[c]\mathrm{other0} + \mathrm{best1}[c] 与 other1+best0[c]\mathrm{other1} + \mathrm{best0}[c]), 这样天然保证两端来自不同子树,lca\mathrm{lca} 正好是 vv。

三种情况都算完再减去 2L depth[v]2L\,\mathrm{depth}[v],对所有 vv 取 max⁡\max 即可。

实现上的两个简化。 一是建 Trie 时按创建顺序给结点编号,父结点的编号一定小于子结点, 于是"按编号倒序扫一遍"就是子树大小的拓扑序,"正序扫一遍"就是换根 DP 的拓扑序, 连显式 DFS 都不用写。二是孩子查找:把 (u,c)(u, c) 编码成 u⋅256+cu \cdot 256 + c 后塞进一张 开放寻址的哈希表,这样是 O(1)O(1) 而不是遍历孩子链表——退化成菊花形的 Trie 也不会变慢。

关于数据。 本题素材目录里带 data.py(生成器),说明 data/ 是自造的, 题面也是网络重建版本,出题意图与官方原题可能存在偏差。第 10 个点是 ∣S∣=106|S| = 10^6 的 单条链(生成器注释写的是"最坏结构"),此时 Trie 深度达到 10610^6,答案里出现 1.67×10171.67 \times 10^{17} 量级的数——必须全程 long long。

代码

Python 版:

python
#!/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-10-07 17:18
# update_at: 2026-10-07 17:18

import sys

NEG = -(1 << 62)  # 配对 DP 里的"不存在"哨兵,比任何合法权值都小


def build_tree(keys: list[int]) -> tuple[list[int], list[int], list[int]]:
    """按键序列建 Trie(退格 8 表示回父结点),返回 (父结点, 深度, 子树大小)。

    集合 S 恰好是这棵 Trie 的结点集:光标在串尾,走一步就是一个孩子,
    退格就是回父结点。字符键用 父结点*256 + ASCII 编码,同一个 (结点, 字符) 只会开一个点。
    """
    parent, depth, size = [-1], [0], [1]  # 结点 0 = 空串 = 根
    child: dict[int, int] = {}
    cur = 0
    for k in keys:
        if k == 8:
            cur = parent[cur] if cur else 0
        else:
            key = cur * 256 + k
            nxt = child.get(key, -1)
            if nxt < 0:  # 这个字符还没出现过,现场开点
                nxt = len(parent)
                child[key] = nxt
                parent.append(cur)
                depth.append(depth[cur] + 1)
                size.append(1)
            cur = nxt
    for v in range(len(parent) - 1, 0, -1):  # 结点编号即拓扑序,父结点编号一定更小
        size[parent[v]] += size[v]
    return parent, depth, size


def day_stat(parent: list[int], depth: list[int], size: list[int]) -> tuple[int, int, int, int, list[int]]:
    """算一天的统计量:返回 (结点数, 两两距离和 W, min D, max D, 每点到全集合的距离和 D)。"""
    n = len(parent)
    # 每条边 (parent[v], v) 被两侧点的每一对跨过:一侧 size[v] 个点,另一侧 n - size[v] 个
    W = sum(size[v] * (n - size[v]) for v in range(1, n))
    D = [sum(depth)] + [0] * (n - 1)  # 根(空串)到所有点的距离和 = 所有点的深度和
    for v in range(1, n):  # 换根:从父结点走进子树,子树内的点都近 1,其余点都远 1
        D[v] = D[parent[v]] + n - 2 * size[v]
    return n, W, min(D), max(D), D


def best_pair(parent: list[int], depth: list[int], D: list[int], coef_a: int, coef_c: int) -> int:
    """在 B 上求 max[nA*D[x] + nC*D[y] + L*d(x,y)],L = nA*nC(第 3 天最大值的那一项)。

    用 d(x,y) = depth[x] + depth[y] - 2*depth(lca) 拆开,改成对每个结点 v 只统计
    "lca 恰好是 v"的配对:倒序扫编号,孩子子树先并入 v 的候选(孩子编号一定更大)。
    """
    n = len(parent)
    L = coef_a * coef_c
    F = [coef_a * D[v] + L * depth[v] for v in range(n)]  # x 取 v 时的权值
    G = [coef_c * D[v] + L * depth[v] for v in range(n)]  # y 取 v 时的权值
    cross = [F[v] + G[v] for v in range(n)]               # lca = v 的候选答案(先放 x = y = v)
    best0, best1 = F[:], G[:]                             # 子树内 max F / max G,初始含 v 自身
    ans = NEG
    for v in range(n - 1, -1, -1):
        ans = max(ans, cross[v] - 2 * L * depth[v])  # 扣掉 lca 以上多算的两段深度
        p = parent[v]
        if p >= 0:  # 把孩子子树并入父结点:父结点已并入的部分与 v 的子树一定不相交
            cross[p] = max(cross[p], best0[p] + best1[v], best1[p] + best0[v])
            best0[p] = max(best0[p], best0[v])
            best1[p] = max(best1[p], best1[v])
    return ans


def solve() -> None:
    # 一天恰好一行,空行表示该天只按过退格(集合只有空串),所以不能过滤空行;
    # 退格 8 与字符含义不同、必须按行分组,这也是这里按行读入而不是 next() 顺序消费的原因
    raw = sys.stdin.buffer.read().split(b'\n')
    days = [(raw[i] if i < len(raw) else b'') for i in range(3)]
    keys = [[int(x) for x in ln.split()] for ln in days]
    info = [day_stat(*build_tree(k)) for k in keys]
    (nA, WA, dAmin, dAmax, DA), (nB, WB, dBmin, dBmax, DB), (nC, WC, dCmin, dCmax, DC) = info
    parB, depB, _ = build_tree(keys[1])

    # 第 1 天:A 内部两两距离之和
    day1 = WA

    # 第 2 天:A×B 的对距离为 d(P,A0)+1+d(B0,Q),展开后 A0 的系数是 nB,B0 的系数是 nA
    day2min = WA + WB + nA * nB + nB * dAmin + nA * dBmin
    day2max = WA + WB + nA * nB + nB * dAmax + nA * dBmax

    # 第 3 天:A×C 的对多走一趟 B0→B1,故 A0 系数 nB+nC、C0 系数 nA+nB,B0/B1 分别带 nA/nC
    base = WA + WB + WC + nA * nB + nB * nC + 2 * nA * nC
    day3min = base + (nB + nC) * dAmin + (nA + nB) * dCmin + (nA + nC) * dBmin
    day3max = base + (nB + nC) * dAmax + (nA + nB) * dCmax + best_pair(parB, depB, DB, nA, nC)

    print(f"{day1} {day1}")
    print(f"{day2min} {day2max}")
    print(f"{day3min} {day3max}")


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * 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-07 17:18
 * update_at: 2026-10-07 17:18
 */
// main.cpp:奇特的猫(一本通 1704)。
// 每天按键产生的所有屏幕字符串(含空串)构成一个前缀封闭集合 S,恰好是一棵 Trie 的结点集,
// 串间编辑距离 d(P,Q)=|P|+|Q|-2*LCP(P,Q) 正是这棵 Trie 上的树距。
// 于是三天的答案都归结为 Trie 上的统计:子树大小、换根距离和、以及一次自底向上的配对 DP。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXNODE = 1000005; // 单天 Trie 的结点数上限:|S| ≤ 10^6,再加一个根
const int HASH_BITS = 22;    // 孩子查找哈希表大小 2^22,装载因子 ≤ 1/4
const int HASH_SIZE = 1 << HASH_BITS;
const int HASH_MASK = HASH_SIZE - 1;
const ll NEG_INF = -(1LL << 62); // DP 里的"不存在"哨兵

struct Node {
    int parent;      // 父结点编号,根(空串)为 -1
    int depth;       // 深度 = 该结点代表的字符串长度
    int firstChild;  // 孩子链表的头,-1 表示叶子
    int nextSibling; // 兄弟链表的后继
    int subSize;     // 子树结点个数
    int ch;          // 从父结点下来的那个字符(ASCII 值;用 int 免去字符与键之间的转换)
    ll distSum;      // 到本集合内所有结点的距离之和
};

Node trie[MAXNODE]; // 结点 v 就是 trie[v],编号按创建顺序分配,父结点编号一定小于子结点
int nodeCnt;        // 已经创建的结点个数(编号 0..nodeCnt-1)

// 孩子哈希表:键 = 父结点编号 * 256 + 字符。键与 (结点, 字符) 一一对应,
// 因此不存在"两个不同的孩子落到同一个键"的情况,只需处理桶下标冲突。
// 0xFFFFFFFF 是空槽标记(真实键最大只有 1e6*256 ≈ 2.6e8)。
unsigned hashKey[HASH_SIZE];
int hashVal[HASH_SIZE];

ll bestB0[MAXNODE]; // bestB0[v] = 子树 v 内 max(nA*D[x] + L*depth[x]),供第 3 天取 b0 用
ll bestB1[MAXNODE]; // bestB1[v] = 子树 v 内 max(nC*D[x] + L*depth[x]),供第 3 天取 b1 用

ll dayN[3];    // 三天的 |S|
ll dayW[3];    // 三天的集合内两两距离之和
ll dayDmin[3]; // 三天里 min_v (v 到集合内所有点的距离和)
ll dayDmax[3]; // 三天里 max_v (v 到集合内所有点的距离和)

vector<char> inBuf; // 一次性读入的全部输入,避免逐字符读入的开销
size_t dayBegin[3]; // 三天按键行在 inBuf 里的起始下标
size_t inPos;       // 当前解析位置

// 把整份输入读进内存,并在末尾补一个换行,解析时不必单独处理文件尾。
void readInput() {
    char tmp[1 << 20];
    size_t got;
    while ((got = fread(tmp, 1, sizeof(tmp), stdin)) > 0)
        inBuf.insert(inBuf.end(), tmp, tmp + got);
    inBuf.push_back('\n');
}

// 定位三行输入在缓冲里的起点:一天恰好一行,空行也是一天(该天只有空串)。
// 读入时已在末尾补了换行,所以最后一行的行尾也一定能找到。
void splitLines() {
    size_t p = 0;
    for (int d = 0; d < 3; ++d) {
        dayBegin[d] = p;
        while (p < inBuf.size() && inBuf[p] != '\n')
            ++p;
        ++p; // 跳过行尾换行,下一行的起点
    }
}

// 动态化静态开点:新建一个结点并返回编号。
int newNode(int par, int c) {
    int id = nodeCnt++;
    trie[id].parent = par;
    trie[id].depth = (par == -1 ? 0 : trie[par].depth + 1);
    trie[id].firstChild = -1;
    trie[id].nextSibling = -1;
    trie[id].subSize = 1;
    trie[id].ch = c;
    trie[id].distSum = 0;
    return id;
}

// 乘法散列:把键摊到 2^22 个桶上,装载因子低,线性探测足够快。
unsigned hashPos(unsigned key) {
    return (key * 2654435761u) >> (32 - HASH_BITS);
}

// 结点 u 沿字符 c 向下走一步:没有对应孩子就现场新建一个。
int walkChild(int u, int c) {
    unsigned key = u * 256 + c;
    unsigned pos = hashPos(key);
    while (hashKey[pos] != 0xFFFFFFFFu && hashKey[pos] != key)
        pos = (pos + 1) & HASH_MASK;
    if (hashKey[pos] == key)
        return hashVal[pos];
    int id = newNode(u, c);
    trie[id].nextSibling = trie[u].firstChild; // 头插进父结点的孩子链表
    trie[u].firstChild = id;
    hashKey[pos] = key;
    hashVal[pos] = id;
    return id;
}

// 建好一天的 Trie 后统计这一天的三个量。
// 关键性质:结点编号就是拓扑序(父结点编号一定小于子结点编号),
// 所以倒着扫一遍能累加子树大小,正着扫一遍能由父结点推出子结点的距离和。
void calcDay(int d) {
    for (int v = nodeCnt - 1; v >= 1; --v)
        trie[trie[v].parent].subSize += trie[v].subSize; // 孩子编号更大,此时子树大小已完整

    dayN[d] = nodeCnt;
    dayW[d] = 0;
    for (int v = 1; v < nodeCnt; ++v) {
        ll s = trie[v].subSize; // 边 (parent,v) 一侧有 s 个点,另一侧有 n-s 个点
        dayW[d] += s * (dayN[d] - s);
    }

    ll d0 = 0; // 根(空串)到所有结点的距离和 = 所有结点的深度和
    for (int v = 0; v < nodeCnt; ++v)
        d0 += trie[v].depth;
    trie[0].distSum = d0;
    for (int v = 1; v < nodeCnt; ++v) { // 换根:从父结点走到子结点,子树内的点都近 1,其余点都远 1
        int p = trie[v].parent;
        trie[v].distSum = trie[p].distSum + dayN[d] - 2 * trie[v].subSize;
    }

    dayDmin[d] = trie[0].distSum;
    dayDmax[d] = trie[0].distSum;
    for (int v = 1; v < nodeCnt; ++v) {
        dayDmin[d] = min(dayDmin[d], trie[v].distSum);
        dayDmax[d] = max(dayDmax[d], trie[v].distSum);
    }
}

// 读入第 d 天的按键序列并建 Trie(退格 8 = 回父结点),然后统计该天。
void buildDay(int d) {
    memset(hashKey, 0xFF, sizeof(hashKey)); // 清空孩子哈希表
    nodeCnt = 0;
    newNode(-1, 0); // 根 = 空串

    inPos = dayBegin[d];
    int cur = 0;
    while (inPos < inBuf.size() && inBuf[inPos] != '\n') {
        char c = inBuf[inPos];
        if (c == ' ' || c == '\r' || c == '\t') {
            ++inPos;
            continue;
        }
        int val = 0;
        while (inPos < inBuf.size() && inBuf[inPos] >= '0' && inBuf[inPos] <= '9') {
            val = val * 10 + (inBuf[inPos] - '0');
            ++inPos;
        }
        if (val == 8) { // 退格:光标回退,串变成父结点代表的串
            if (cur != 0)
                cur = trie[cur].parent;
        } else {
            cur = walkChild(cur, val);
        }
    }
    calcDay(d);
}

// 第 3 天最大值里唯一需要配对优化的部分:
//   max over b0,b1 in B of [ nA*D[b0] + nC*D[b1] + L*d(b0,b1) ],L = nA*nC。
// 用 d(b0,b1) = depth(b0) + depth(b1) - 2*depth(lca) 拆开,就变成
//   max over b0,b1 of [ f[b0] + g[b1] - 2*L*depth(lca(b0,b1)) ],
// 再按 lca 分类:对每个结点 v 枚举"lca 恰好是 v"的配对(两端都是 v / 一端是 v 另一端在某个孩子子树 /
// 两端在两个不同的孩子子树),倒序编号保证孩子先算好。
ll maxPairInB(ll coefA, ll coefC) {
    ll L = coefA * coefC;
    ll best = NEG_INF;
    for (int v = nodeCnt - 1; v >= 0; --v) {
        ll f = coefA * trie[v].distSum + L * trie[v].depth; // 取 b0 = v 时的权值
        ll g = coefC * trie[v].distSum + L * trie[v].depth; // 取 b1 = v 时的权值
        ll cur = f + g;                                     // b0 = b1 = v
        ll sub0 = f, sub1 = g;                              // 子树内 max f / max g
        ll other0 = NEG_INF, other1 = NEG_INF;              // 已处理过的孩子子树里 max f / max g
        for (int c = trie[v].firstChild; c != -1; c = trie[c].nextSibling) {
            cur = max(cur, f + bestB1[c]);   // 一端是 v,另一端在子树 c
            cur = max(cur, bestB0[c] + g);
            if (other0 != NEG_INF)
                cur = max(cur, other0 + bestB1[c]); // 两端分别在两个不同的孩子子树
            if (other1 != NEG_INF)
                cur = max(cur, other1 + bestB0[c]);
            other0 = max(other0, bestB0[c]);
            other1 = max(other1, bestB1[c]);
            sub0 = max(sub0, bestB0[c]);
            sub1 = max(sub1, bestB1[c]);
        }
        bestB0[v] = sub0;
        bestB1[v] = sub1;
        cur -= 2 * L * trie[v].depth; // lca 恰好是 v,扣掉多算的两段 depth
        best = max(best, cur);
    }
    return best;
}

int main() {
    readInput();
    splitLines();

    buildDay(0);
    buildDay(1);
    buildDay(2);

    ll nA = dayN[0], nB = dayN[1], nC = dayN[2];

    // 第 1 天:集合 A 内所有字符串对的距离之和。
    ll day1 = dayW[0];

    // 第 2 天:把 A、B 并成一个整体,A0、B0 固定后所有对的距离之和
    //   = W(A) + W(B) + [A×B 的对:nA*nB + nB*D_A[A0] + nA*D_B[B0]]。
    ll day2min = dayW[0] + dayW[1] + nA * nB + nB * dayDmin[0] + nA * dayDmin[1];
    ll day2max = dayW[0] + dayW[1] + nA * nB + nB * dayDmax[0] + nA * dayDmax[1];

    // 第 3 天:A、B、C 三个集合并成一个整体,A0、B0、B1、C0 固定后所有对的距离之和
    //   = W(A)+W(B)+W(C) + [A×B 的对] + [B×C 的对] + [A×C 的对],
    // 其中 A×C 的距离是 d(P,A0)+1+d(B0,B1)+1+d(C0,Q),展开后系数为:
    //   base 部分 (nA*nB + nB*nC + 2*nA*nC) 固定,
    //   A0 的系数是 nB+nC,C0 的系数是 nA+nB,B0/B1 的系数分别是 nA/nC 且带 d(B0,B1) 一项。
    ll base = dayW[0] + dayW[1] + dayW[2] + nA * nB + nB * nC + 2 * nA * nC;
    ll day3min = base + (nB + nC) * dayDmin[0] + (nA + nB) * dayDmin[2] + (nA + nC) * dayDmin[1];

    // 最小值取 B0 = B1 同为 D_B 最小的点即可(d ≥ 0);
    // 最大值要在 B 上重新建树做配对 DP,所以重读一次第 2 天的按键。
    buildDay(1);
    ll maxPair = maxPairInB(nA, nC);
    ll day3max = base + (nB + nC) * dayDmax[0] + (nA + nB) * dayDmax[2] + maxPair;

    cout << day1 << " " << day1 << "\n";
    cout << day2min << " " << day2max << "\n";
    cout << day3min << " " << day3max << "\n";
    return 0;
}

复杂度

  • 时间:每个按键摊到 O(1)O(1),一天的处理是 O(按键数+nd)O(\text{按键数} + n_d)。 生成器给的最坏点是三天的 ∣S∣|S| 都是 10610^6,按键数各为 2(∣S∣−1)2(|S|-1),总操作量约 6×1066 \times 10^6,实测 C++ 在限时 1000 ms 内轻松通过。第 3 天的配对 DP 只对 BB 做一次, O(nB)O(n_B)。
  • 空间:单天 Trie 的结点数上界 106+110^6 + 1,结点用 struct 数组存,配 2222^{22} 的开放寻址哈希表(装载因子 ≤1/4\le 1/4),再加两个 long long 的 DP 数组, 峰值约 80 MB,限时内存 256 MB。
  • 与 C++ 解法的关系:main.py 用同一套公式和同一套 Trie,只是把"孩子哈希表" 换成 Python 的 dict(键同样是 u * 256 + c),把换根 DP 与配对 DP 写成倒序扫编号的 for 循环。Python 侧的主要风险是 ∣S∣=106|S| = 10^6 那一点会 TLE / MLE(dict 与三个 长度为 10610^6 的 list 开销都在数百 MB 量级),算法本身与 C++ 同阶。

总结

  • 把操作序列翻译成树:光标在串尾 + 退格回退,等价于在 Trie 上走一条路径, "出现过的所有串"就是访问过的结点集合。这一步之后,字符串的编辑距离问题 就完全变成了树上距离问题。
  • 前缀封闭是关键结构:SS 是 Trie 的结点集而非任意字符串集合, 所以 ∣S∣|S| 可以直接当结点数用,子树大小也有明确含义。
  • 跨集合的那 11 个单位可摊分:d(P,Q)=d(P,A0)+1+d(B0,Q)d(P,Q) = d(P,A_0) + 1 + d(B_0,Q) 拆开后, 只有三个"距离和" DS[⋅]D_S[\cdot] 参与优化,其余都是与选择无关的固定项, 于是最小/最大只需在 min⁡D\min D / max⁡D\max D 上取值。
  • B0≠B1B_0 \ne B_1 才带来真正的难度:最大值里出现 d(B0,B1)d(B_0,B_1), 用 lca\mathrm{lca} 拆项后变成"在每个结点上合并两棵不同子树的最值", 这是典型的树形 DP 合并套路。
  • 编号即拓扑序:按创建顺序给 Trie 结点编号,父结点编号恒小于子结点, 于是子树大小与换根 DP 都退化成一次数组扫描,省掉显式 DFS 和递归栈。