字典树，可惜比赛的时候有两句话写倒了；
害得我调了一个小时；
今天不宜做题 = =
代码：
#include<cstdio>
#include<cstring>
#define maxn 2600009
using namespace std; struct node
{
bool flag;
int cnt;
node *a[];
} no[maxn]; char s[];
int ans,nonocount;
node *newnode()
{
node *p=no+nonocount++;
p->flag=;
p->cnt=;
for(int i=; i<; i++)
p->a[i]=NULL;
return p;
} void insert(node *rt,char *s)
{
int l=strlen(s);
int i=;
while()
{
if(rt->a[s[i]-'a']==NULL) rt->a[s[i]-'a']=newnode();
rt=rt->a[s[i]-'a'];
rt->cnt++;
i++;
if(i==l)
{
rt->flag=;
break;
}
}
} void query(node *rt)
{
int cot=;
for(int i=; i<; i++)
{
if(rt->a[i]!=NULL)
{
cot++;
query(rt->a[i]);
}
}
if(cot>)
{
ans+=rt->cnt;
if(rt->flag==)ans--;
}
else if(rt->flag==)
{
ans+=(rt->cnt-);
}
} int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
nonocount=;
node *p=newnode();
for(int i=; i<n; i++)
{
scanf("%s",s);
insert(p,s);
}
ans=;
query(p);
printf("%.2lf\n",(double)(ans+n)/n);
}
return ;
}