思路与算法

把每天访问过的不同字符串建成含空串根的Trie，编辑距离就是树距离。先用子树大小和换根求每棵树内部无序点对距离和I及各点距离和F。两天连接代价由I和两侧F组成。三天时中间树两个连接点u,v的变量项为NA·FB(u)+NC·FB(v)+NA·NC·dist(u,v)，外围两树分别独立取F的极值。中间项用两趟树上最小/最大距离变换求解；最大值向上转移保留不同分支的前两名。

正确性说明

每个字符串只对应Trie一个节点，路径上的插入删除给出最短编辑距离。连接两棵树后跨树点对必经连接边，逐项求和得到公式；三棵树的非相邻点对额外经过中间路径，得到变量项。树上两趟传播分别覆盖同子树和子树外候选，最大值排除回到同分支，故取到且仅取到真实点对极值。

复杂度

设按键总数K、Trie节点总数V，字符集固定128。建树最坏O(128K)，统计和两趟变换O(V)，数组初始化O(V)，空间O(V)；大答案中间积使用128位。

易错点

重复访问同一串只计一个节点，根空串也计入。空按键行和根退格须支持。最大距离变换不能允许沿一条边往返虚增距离。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using i128 = __int128_t;
struct Stats {
    int n;
    vector<int> par;
    vector<long long> F;
    long long inside, lo, hi;
};
Stats readTree() {
    string line;
    getline(cin, line);
    vector<int> par(1, 0), head(1, -1), next(1, -1), label(1, -1), depth(1);
    int cur = 0;
    for (size_t i = 0; i < line.size();) {
        while (i < line.size() && isspace((unsigned char)line[i]))
            i++;
        if (i == line.size())
            break;
        int c = 0;
        while (i < line.size() && isdigit(line[i]))
            c = c * 10 + line[i++] - '0';
        if (i < line.size() && !isdigit(line[i]) && line[i] != ' ')
            i++;
        if (c == 8) {
            cur = par[cur];
            continue;
        }
        int v = head[cur];
        while (v >= 0 && label[v] != c)
            v = next[v];
        if (v < 0) {
            v = par.size();
            par.push_back(cur);
            head.push_back(-1);
            next.push_back(head[cur]);
            label.push_back(c);
            depth.push_back(depth[cur] + 1);
            head[cur] = v;
        }
        cur = v;
    }
    int n = par.size();
    vector<int> sz(n, 1);
    vector<long long> F(n);
    long long inside = 0;
    for (int i = n - 1; i > 0; i--) {
        sz[par[i]] += sz[i];
        inside += 1LL * sz[i] * (n - sz[i]);
    }
    F[0] = accumulate(depth.begin(), depth.end(), 0LL);
    long long lo = F[0], hi = F[0];
    for (int i = 1; i < n; i++) {
        F[i] = F[par[i]] + n - 2LL * sz[i];
        lo = min(lo, F[i]);
        hi = max(hi, F[i]);
    }
    return {n, move(par), move(F), inside, lo, hi};
}
void print(i128 x) {
    if (x == 0) {
        cout << 0;
        return;
    }
    string s;
    while (x) {
        s += char('0' + x % 10);
        x /= 10;
    }
    reverse(s.begin(), s.end());
    cout << s;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    auto A = readTree(), B = readTree(), C = readTree();
    long long a = A.n, b = B.n, c = C.n, K = a * c;
    cout << A.inside << ' ' << A.inside << '\n';
    i128 base2 = (i128)A.inside + B.inside + a * b;
    print(base2 + (i128)b * A.lo + (i128)a * B.lo);
    cout << ' ';
    print(base2 + (i128)b * A.hi + (i128)a * B.hi);
    cout << '\n';
    vector<long long> mn(b), top(b), second(b, LLONG_MIN / 4), up(b, LLONG_MIN / 4);
    vector<int> who(b, -1);
    for (int i = 0; i < b; i++)
        mn[i] = top[i] = c * B.F[i];
    for (int u = b - 1; u > 0; u--) {
        int p = B.par[u];
        mn[p] = min(mn[p], mn[u] + K);
        long long val = top[u] + K;
        if (val > top[p]) {
            second[p] = top[p];
            top[p] = val;
            who[p] = u;
        } else
            second[p] = max(second[p], val);
    }
    for (int u = 1; u < b; u++) {
        int p = B.par[u];
        mn[u] = min(mn[u], mn[p] + K);
        long long other = who[p] == u ? second[p] : top[p];
        up[u] = max(up[p], other) + K;
    }
    i128 bestMin = (i128)1 << 120, bestMax = -1;
    for (int u = 0; u < b; u++) {
        bestMin = min(bestMin, (i128)a * B.F[u] + mn[u]);
        bestMax = max(bestMax, (i128)a * B.F[u] + max(top[u], up[u]));
    }
    i128 base3 = (i128)A.inside + B.inside + C.inside + a * b + b * c + 2 * a * c;
    print(base3 + (i128)(b + c) * A.lo + (i128)(a + b) * C.lo + bestMin);
    cout << ' ';
    print(base3 + (i128)(b + c) * A.hi + (i128)(a + b) * C.hi + bestMax);
    cout << '\n';
}