题目链接：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1115
解题报告：输入n个字符串，让你求出可以用来区别这些字符串的最少的前缀总共有多少个字母。可以区别是指每个字符串都取一个自己的前缀，同时保证所有取的这些前缀没有完全相同。
这题用字典树可以做，就是输入的时候把所有的字符串都插入到字典树中，最后把所有被走过不止一次的节点的值都加起来，每个节点的值表示这个节点被走过多少次，然后如果碰到这个节点的值是1的时候总和加1，同时要退出，后面的就不用统计了，因为这个节点只被走过一次，所以经过这个节点的那个字符串到这里已经是唯一的了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<deque>
#include<map>
#include<queue>
#include<cstdlib>
using namespace std;
const int maxn = ;
char temp[];
int ans;
typedef struct node
{
node* ch[];
int tot;
}*Linklist;
void Init(Linklist& p)
{
p->tot = ;
for(int i = ;i < ;++i)
p->ch[i] = NULL;
}
void push(Linklist p,char* str,int f,int len)
{
if(f >= len)
return ;
if(p->ch[str[f]-'a'] == NULL)
{
p->ch[str[f]-'a'] = new node;
Init(p->ch[str[f]-'a']);
p->ch[str[f]-'a']->tot++;
p = p->ch[str[f]-'a'];
}
else
{
p->ch[str[f]-'a']->tot++;
p = p->ch[str[f]-'a'];
}
push(p,str,f+,len);
} void get_tot(Linklist p)
{
if(p == NULL || p->tot == )
{
if(p != NULL && p->tot == ) ans++;
return ;
}
else ans += p->tot;
for(int i = ;i < ;++i)
get_tot(p->ch[i]);
}
void clean(Linklist p)
{
if(p == NULL)
return ;
for(int i = ;i < ;++i)
if(p->ch[i] != NULL)
clean(p->ch[i]);
delete p;
}
int main()
{
int T,n;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
Linklist head = new node;
Init(head);
for(int i = ;i < n;++i)
{
scanf("%s",temp);
push(head,temp,,strlen(temp));
}
// printf("%d %d %d %d\n",head->ch[0]->tot,head->ch[0]->ch[0]->tot,head->ch[0]->ch[1]->tot,head->ch[1]->tot);
ans = ;
for(int i = ;i < ;++i)
get_tot(head->ch[i]);
printf("%d\n",ans);
clean(head);
}
return ;
}