Codeforces 178F. Representative Sampling

题意：

给你$n$个串，你要选出一个大小为$k$的集合，使得价值最大。一个集合的价值定义为元素两两之间的最长公共前缀之和。

题解：

%%%tyb
我们可以建一个trie，然后在上面做背包。因为两棵子树的LCP都是一样的，所以可以直接转移。但是trie的节点太多了，所以我们可以建个虚树，就可以做了。
但是虚树太难写了我们可以先把所有串按字典序排好，然后求出相邻两个串的LCP，然后按LCP从大到小合并（相当于trie上从深到浅处理），然后用并查集把它们合起来。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;

int n, k, fa[2010], f[2010][2010], lcp[2010], order[2010], sz[2010];
string s[2010];

int fd(int x) { return fa[x] == x ? x : fa[x] = fd(fa[x]);}
int cmp(int x, int y) { return lcp[x] > lcp[y]; }
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> s[i];
    sort(s + 1, s + 1 + n);
    for (int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;
    for (int i = 1; i < n; i++)
        while (lcp[i] < min(s[i].size(), s[i + 1].size()) && s[i][lcp[i]] == s[i + 1][lcp[i]])
            lcp[i]++;
    for (int i = 1; i < n; i++) order[i] = i;
    sort(order + 1, order + n, cmp);/*
    for (int i = 1; i < n; i++)
        cerr << order[i] << endl;*/
    for (int i = 1; i < n; i++)
    {
        int hh = order[i];
        // cerr << lcp[hh] << endl;
        int x = fd(hh), y = fd(hh + 1);/*
        for (int i = 1; i <= min(sz[x], k); i++)
            cerr << f[x][i] << ' ';
        cerr << endl;
        for (int i = 1; i <= min(sz[y], k); i++)
            cerr << f[y][i] << ' ';
        cerr << endl;*/
        for (int i = min(sz[x] + sz[y], k); i > 0; i--)
            for (int j = 0; j <= min(i, sz[x]); j++)
            {
                f[x][i] = max(f[x][i], f[x][j] + f[y][i - j] + lcp[hh] * j * (i - j));
                // cerr << i << ' ' << j << endl;
            }/*
        for (int i = 1; i <= min(sz[x] + sz[y], k); i++)
            cerr << f[x][i] << ' ';
        cerr << endl;*/
        fa[y] = x;
        sz[x] += sz[y];
    }
    cout << f[fd(1)][k] << endl;
}