Trie+贪心
倒插进树+取出重建+子树处理+贪心遍历
倒插进树：把后缀转化为前缀，所以把字符串倒着插进Trie中
取出重建：重新建立一棵以单词为节点的树，如果存在包含（前缀）关系就连边
子树处理：处理出每棵树的大小用于贪心
贪心遍历：遍历整棵新树，累加答案
关于贪心：每次找到最小的子树统计答案
end.
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; struct data{ int nxt[27],end; data(){memset(nxt,0,sizeof(nxt)); end=0;} }a[510003]; vector <int> g[100002]; //存边 int n,cnt,len,siz[100002]; long long f[100002]; char q[510003]; inline bool cmp(const int &A,const int &B) {return siz[A]<siz[B];} inline void read_q(){ char c=getchar(); len=0; while(c<'a'||c>'z') c=getchar(); while('a'<=c&&c<='z') q[len++]=c,c=getchar(); } inline void insert_(int id){ //建树 read_q(); int u=0; for(int i=len-1;i>=0;--i){ int p=q[i]-'a'; if(!a[u].nxt[p]) a[u].nxt[p]=++cnt; u=a[u].nxt[p]; }a[u].end=id; //编号代替单词 } inline void rebuild(int x,int p){ //重新建树 if(a[x].end) g[p].push_back(a[x].end); //存在前缀关系连边 for(int i=0;i<26;++i){ int to=a[x].nxt[i]; if(!to) continue; rebuild(to,a[x].end ? a[x].end:p); } } inline void dfs1(int x){ siz[x]=1; for(int i=0;i<g[x].size();++i){ int to=g[x][i]; dfs1(to); siz[x]+=siz[to]; } sort(g[x].begin(),g[x].end(),cmp); //按子树从小到大排序 } inline void dfs2(int x){ f[x]=x? 1:0; long long tmp=0; for(int i=0;i<g[x].size();++i){ int to=g[x][i]; dfs2(to); f[x]+=f[to]+tmp; //贪心累加答案 tmp+=siz[to]; } } int main(){ scanf("%d",&n); for(int i=1;i<=n;++i) insert_(i); rebuild(0,0); dfs1(0); dfs2(0); printf("%lld",f[0]); return 0; }