字典树问题
对于普通的字典树，可以加一个vector数组记录非空的孩子，加快速度
还可以用左孩子右兄弟来节省空间，因为普通的trie的话是
int next[MAXN][26]
而左孩子右兄弟可以把[26]省掉，这题实际上并不需要这么节省也可以AC
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#define MAXN 4000*1000+10
#define ll long long
using namespace std;
struct Trie{
int nxt[MAXN][];
int v[MAXN];
vector<int> son[MAXN];
int tot;
int newnode(){
tot++;
memset(nxt[tot],,sizeof(nxt[tot]));
v[tot]=;
son[tot].clear();
return tot;
}
void init(){
tot=;
newnode();
}
int ind(char c){
if(''<=c&&c<='') return c-;
else if('a'<=c&&c<='z') return c-;
else return c-;
}
void insert(char s[]){
int p=;
int len=strlen(s);
for(int i=;i<len;i++){
int t=ind(s[i]);
if(nxt[p][t]){
p=nxt[p][t];
}
else{
nxt[p][t]=newnode();
son[p].push_back(t);
p=nxt[p][t];
}
}
v[p]++;
}
pair<ll,int> find(int p,int dep){
ll ret=1LL*(v[p])*(v[p]-)*(dep+);
int cnt=;
for(int i=;i<son[p].size();i++){
int tt=son[p][i];
if(nxt[p][tt]){
pair<ll,int> t=find(nxt[p][tt],dep+);
ret+=t.first;
ret+=1LL*cnt*t.second*(*dep+);
cnt+=t.second;
}
}
ret+=1LL*cnt*(v[p])*(*dep+);
cnt+=v[p];
return make_pair(ret,cnt);
}
}D;
int n;
char s[];
int main()
{
int T;
while(){
scanf("%d",&n);
if(!n)break;
D.init();
for(int i=;i<=n;i++){
scanf("%s",s);
D.insert(s);
}
printf("Case %d: %lld\n",++T,D.find(,).first);
}
return ;
}
普通字典树
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#define MAXN 4000*1000+10
#define ll long long
using namespace std;
struct Trie{
int first[MAXN];
int nxt[MAXN];
int v[MAXN];
char ch[MAXN];
int cnt;
int newnode(int fa,char c){
nxt[++cnt]=first[fa];
first[fa]=cnt;
first[cnt]=;
v[cnt]=;
ch[cnt]=c;
return cnt;
}
void init(){
cnt=;
first[]=nxt[]=v[]=ch[]=;
}
void insert(char s[]){
int p=;
int len=strlen(s);
for(int i=;i<len;i++){
int ok=;
for(int j=first[p];j;j=nxt[j]){
if(ch[j]==s[i]){
ok=;
p=j;
break;
}
}
if(!ok){
p=newnode(p,s[i]);
}
}
v[p]++;
}
pair<ll,int> find(int p,int dep){
ll ret=1LL*(v[p])*(v[p]-)*(dep+);
int cnt=;
for(int i=first[p];i;i=nxt[i]){
pair<ll,int> t=find(i,dep+);
ret+=t.first;
ret+=1LL*cnt*t.second*(*dep+);
cnt+=t.second;
}
ret+=1LL*cnt*(v[p])*(*dep+);
cnt+=v[p];
return make_pair(ret,cnt);
}
}T;
int n;
char s[];
int main()
{
// freopen("data.in","r",stdin);
int kase=;
while(){
scanf("%d",&n);
if(!n)break;
T.init();
for(int i=;i<=n;i++){
scanf("%s",s);
T.insert(s);
}
printf("Case %d: %lld\n",++kase,T.find(,).first);
}
return ;
}
左孩子右兄弟