有一个 $n$ 个蛋白质的集合 (无需两两不同)，每个蛋白质是一个只包含小写字母的字符串。

科学家们给 scx 提出了一个问题，就是让她从这些蛋白质中选出 $k$ 个，并让着 $k$ 个蛋白质的代表性最大。

其中 $f(x, y)$ 表示蛋白质 $x$ 和 $y$ 所对应的字符串的最长公共前缀的长度。

发现这个性质后，scx 要求参赛者写一个程序来选择这样 $k$ 个蛋白质，请你帮她写一写吧！

输入格式

第一行包含两个整数 $n, k$ ($1 \leq k \leq n \leq 2000$)，表示蛋白质的个数和所需要的蛋白质的个数。

接下来的 $n$ 行，每行包含一个非空字符串，长度不超过 $500$ 且仅由小写字母构成，描述一个蛋白质 (所对应的的字符串)，可能有重复。

输出格式

输出一行一个整数，表示 $k$ 个蛋白质的代表性的最大可能值。

题解

由于涉及到最长公共前缀 (LCP[])，~~而这显然不适合用后缀数据结构~~，那只能考虑建立一棵字典树。

可以看出，在字典树中，两个串的 LCP[] 应该就是它们的最近公共祖先 (LCA[]) 的深度。

又因为字典树中，有些点是对应一些字符串的，而有些点仅仅是一个前缀，我们将前者记为串节点 (不一定是叶节点)，后者记为前缀节点 (一定是非叶节点)。

这样就可以进行树形 DP 了，类似地，记 $g_{i, j}$ 表示以 $i$ 为根的子树中，选取 $j$ 个串节点，两两串节点的 LCA[] 的深度之和，其中根 (点 $i$) 的深度为 $0$。

~~根据树形 DP 的基本套路~~，记 $i$ 的子节点 $c_1, c_2, \cdots, c_{\lambda_i}$，$f_{c_k, j}$ 表示以 $i$ 为根的子树中，只考虑子树 $c_1, c_2, \cdots, c_k$，选取 $j$ 个串节点，那个深度之和，则转移方程即

$$ f_{c_k, j} = \max_{0 \leq l \leq \min\{j, \mathrm{size}(c_k)\}} \left\{ f_{c_{k-1}, j-l} + g_{c_k, l} + \binom l2 \right\} $$

这是一个 $O(Vn)$ 的 DP，其中 $V$ 是节点的个数，$V$ 可以达到 $O(n|S|)$ ($|S|$ 是字符串的长度)，因此最坏复杂度 $O(n^2|S|)$，很可能过不去。

但是可以意识到，我们做了很多无用转移，因为任意两个串只会在它们 LCA[] 的时候更新 DP 值，因此可以把这棵树压缩一下，变成带权树，只保留可能是 LCA[] 的节点 (度大于 $1$ 的节点)，可以证明，这样的节点是 $O(n)$ 的，于是总复杂度降为 $O(n^2)$。

代码

#include <bits/stdc++.h>
#define W 6667
#define N 2034
#define S 505
#define NS 1024404
using namespace std;

int V = 1, n, m, i, j, k;
char s[S];
int d[N * S][26], val[NS], weight[NS], size[NS], o[NS];
int cnt = 0, id[W];
int f[W][N], g[W][N];

inline void up(int &x, const int y) {x < y ? x = y : 0;}
inline int C2(int n) {return n * (n - 1) >> 1;}

void append(char *s){
    char *p = s;
    int t = 1, id;
    for(; *p; ++p){
        id = *p - 97;
        t = d[t][id] ? d[t][id] : (d[t][id] = ++V);
    }
    ++val[t];
}

void dfs(int x){
    int i, j, k, y, la = 0, limit;
    id[++cnt] = x; o[x] = cnt;
    size[x] = val[x];
    for(i = 0; i < 26; ++i)
        if(y = d[x][i]){
            dfs(y);
            size[x] += size[y];
        }
    limit = min(size[x], m);
    for(i = 0; i < 26; ++i)
        if(y = d[x][i]){
            for(j = limit; j; --j)
                for(k = 0; k <= j && k <= size[y]; ++k)
                    up(f[o[y]][j], f[o[la]][j - k] + g[o[y]][k] + C2(k) * (weight[y] + 1));
            la = y;
        }
    memcpy(g[o[x]], f[o[la]], N << 2);
}

int main(){
    scanf("%d%d", &n, &m);
    for(i = 0; i < n; ++i){
        scanf("%s", s);
        append(s);
    }
    memset(f, 0, sizeof f); memset(g, 0, sizeof g);
    for(i = V; i > 1; --i)
        if(!val[i]){
            for(k = j = 0; j < 26; ++j)
                if(d[i][j]) {if(k) break; k = d[i][j];}
            if(j == 26 && !val[k]){
                weight[i] = weight[k] + 1;
                memcpy(d[i], d[k], 104);
            }
        }
    dfs(1);
    printf("%d\n", g[1][m]);
    return 0;
}

坑

坑1：路径压缩的时候要记录一个点是压缩了几个点而来的，比如说它压缩了 $u$ ($u \geq 0$) 个点，则转移中的二项式系数 (组合数) 就要乘以 $u + 1$。

坑2：由于 $O(n^2|S|)$ 的算法空间比较紧张，所以显然不能用，$O(n^2)$ 的算法中，压缩过后点的编号比较零散，因此数组 g[i][j] 的第一维会比较浪费，因此可以在 dfs() 的时候记录一下 dfs 序，然后在 g[i][j] 数组和 f[i][j] 数组的第一维中使用 dfs 序，这样就轻松多啦。

题目描述

输入格式

输出格式

题解

代码

坑