删库

题目大意

分析

对于前缀问题，考虑 $Trie$ 树转化为树上问题

把所有字符串 $add$ 进 $Trie$ 树后记录字符串结尾的位置

贪心的去取字符串

思路是

从下向上 用 $sz[]$ 记录每个结点拥有的子树个数

对于一个结点 $u$

记录结点 $u$ 的子树 $v$ 的 $sz[v]$,存入 $vector$ 中

当 $sz[u] > k$ 时

从大到小的取走 $vector$ 中的 $sz[v] , res++$

为什么每次只能删除一个子树 $v$ 呢？

因为对于 $u$ 的另一个子树 $v^{\prime}$, 删除 $v$ 的前缀并不是 $v^{\prime}$ 的前缀

Code

int n,k;
int son[300005][26];
int ed[300005],sz[300005];
int res,idx;
void add(string &s){
    int p = 0;
    for(auto c:s){
        if(!son[p][c-'a']) son[p][c-'a'] = ++idx;
        p = son[p][c-'a'];
    }
    ed[p]++;
}

void dfs(int u){
    sz[u] = ed[u];
    vector<int> t;
    for(char c = 'a'; c<= 'z';c++){
        int v = son[u][c-'a'];
        if(v){
            dfs(v);
            sz[u] += sz[v];
            t.push_back(sz[v]);
        }
    }
    sort(t.begin(),t.end());
    while(sz[u] > k){
        res++;
        sz[u] -= t.back();
        t.pop_back();
    }
}

signed main()
{
    cin >> n >> k;
    for(int i = 1;i <= n;i++){
        string s;cin >> s;
        add(s);
    }

    dfs(0);
    cout << res + (sz[0] > 0) << endl;
    return 0;
}