倒过来变成查询前缀。考虑怎么排序。第一条代价n*n就相当于inf，说明一个单词的所有前缀都要排在它前面。那么串的依赖关系就是trie的结构。二三条说明代价是Σidi-idfa，那么显然最后的编号应该是trie的一个dfs序（去掉无用节点），并且显然应该先走较小的子树，因为这样使兄弟节点和父亲的编号差更小而不造成其他影响。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> #include<vector> using namespace std; #define ll long long #define N 510010 #define M 100010 int read() { int x=0,f=1;char c=getchar(); while (c<‘0‘||c>‘9‘) {if (c==‘-‘) f=-1;c=getchar();} while (c>=‘0‘&&c<=‘9‘) x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } char getc(){char c=getchar();while ((c<‘A‘||c>‘Z‘)&&(c<‘a‘||c>‘z‘)) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int n,trie[N][26],val[N],cnt; int size[M],id[M]; ll ans; vector<int> s[M],son[M]; bool cmp(const int&a,const int&b) { return size[a]<size[b]; } void ins(vector<int> s,int i) { int k=0; for (int j=0;j<s.size();j++) { if (!trie[k][s[j]]) trie[k][s[j]]=++cnt; k=trie[k][s[j]]; } val[k]=1; } void build(int k,int from) { if (val[k]) cnt++,son[from].push_back(cnt),from=cnt; for (int i=0;i<26;i++) if (trie[k][i]) build(trie[k][i],from); } void dfs(int k) { size[k]=1; for (int i=0;i<son[k].size();i++) { dfs(son[k][i]); size[k]+=size[son[k][i]]; } sort(son[k].begin(),son[k].end(),cmp); } void calc(int k,int from) { id[k]=++cnt;ans+=id[k]-id[from]; for (int i=0;i<son[k].size();i++) calc(son[k][i],k); } int main() { #ifndef ONLINE_JUDGE freopen("bzoj4567.in","r",stdin); freopen("bzoj4567.out","w",stdout); const char LL[]="%I64d\n"; #else const char LL[]="%lld\n"; #endif n=read(); for (int i=1;i<=n;i++) { s[i].push_back(getc()-‘a‘); char c=getchar(); while (c>=‘a‘&&c<=‘z‘) s[i].push_back(c-‘a‘),c=getchar(); reverse(s[i].begin(),s[i].end()); ins(s[i],i); } cnt=0; build(0,0); dfs(0); cnt=-1; calc(0,0); cout<<ans; return 0; }
原文：https://www.cnblogs.com/Gloid/p/9890265.html