P3294 [SCOI2016]背单词

首先第一个是非常不划算的 所以我们想办法先将没有前缀的前放进去

第二就是第三的特殊情况

有公共后缀的一定是连在一起的 几堆不同公共后缀的 一定是先排数量小的一堆 因为这样对后面几堆产生的贡献最小

最后说白了就是先按照sz排序 最后按照dfs序走一遍dfs统计答案就好

#include
#include
#include
#include
#include
using namespace std;
string a[100005];
int trie[510005][26],dp[510005],num[510005],numm;
bool yes[510005];
vector edge[510005];
long long ans;
bool cmp(int x,int y){
    return dp[x]>a[i];
	}
    sort(a+1,a+n+1,cmp1);
	for(i=1;i<=n;i++){
		int len,u=0,bj=0;
		for(j=a[i].size()-1;j>=0;j--){
			if(!trie[u][a[i][j]-'a']){
				trie[u][a[i][j]-'a']=++cnt;
			}
            if(yes[u]){
                bj=u;
            }
			u=trie[u][a[i][j]-'a'];
		}
        edge[bj].push_back(u);
        dp[u]=yes[u]=1;
	}
    dfs(0);
    dfs1(0);
	printf("%lld\n",ans);
	return 0;
}