题意：有n个由小写字母组成的名字，任何一个名字都不是另一个名字的前缀，对于每个名字，只取它的最短前缀，使得这n个取出来的前缀互不相同，问这些前缀的总字母个数（1 <= n <= 1000, 所有名字的总长度不超过1000000，测试数据级数T <= 10）。

题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3950

——>>看完题，想着这会不会是前缀树的题目，又看到名字长度不超过1000000，26^1000000个结点？于是不再考虑Trip。。。赛后才发现，看错题目了，1000000是所有名字加起来的最大总字母个数，正正是用Trip的题目。

设cnt[i]为第i个结点有多少个名字经过，那么，若cnt[i]为1，则表明只有1个名字经过，下面只表示1个人，于是可以停止往下的扫描；若cnt[i] > 1，则表明不止1个名字经过，必须往下扫描，直到能分辨出来为止。

Trip的数组写法：

#include <cstdio>
#include <cstring>
#include <queue>using namespace std;const int maxnode = 1000000 + 10;
const int maxn = 1000 + 10;
char name[maxn];
int n, ch[maxnode][26];
int cnt[maxnode];struct Trip{int sz;Trip(){sz = 1;memset(ch[0], 0, sizeof(ch[0]));memset(cnt, 0, sizeof(cnt));}int idx(char c){return c - 'a';}void insert(char *s){int len = strlen(s), u = 0, i;for(i = 0; i < len; i++){int c = idx(s[i]);if(!ch[u][c]){memset(ch[sz], 0, sizeof(ch[sz]));ch[u][c] = sz++;}cnt[ch[u][c]]++;u = ch[u][c];}}void solve(){int ret = 0, i, u;queue<int> qu;qu.push(0);while(!qu.empty()){u = qu.front(); qu.pop();for(i = 0; i < 26; i++) if(ch[u][i]){ret += cnt[ch[u][i]];if(cnt[ch[u][i]] > 1) qu.push(ch[u][i]);}}printf("%d\n", ret);}
};int main()
{int T;scanf("%d", &T);while(T--){Trip trip;scanf("%d", &n);for(int i = 0; i < n; i++){scanf("%s", name);trip.insert(name);}trip.solve();}return 0;
}

Trip的指针写法（事先不用预定空间，比较灵活）：

#include <cstdio>
#include <cstring>
#include <queue>using namespace std;const int maxn = 1000 + 10;
char name[maxn];
int n;struct node{int cnt;node *next[26];node(){cnt = 0;memset(next, 0, sizeof(next));}
};struct Trip{node *root;Trip(){root = new node;}int idx(char c){return c - 'a';}void insert(char *s){int len = strlen(s), i;node *t = root;for(i = 0; i < len; i++){int c = idx(s[i]);if(!t->next[c]) t->next[c] = new node;t->next[c]->cnt++;t = t->next[c];}}void solve(){int ret = 0, i;node *t = new node;queue<node*> qu;qu.push(root);while(!qu.empty()){t = qu.front(); qu.pop();for(i = 0; i < 26; i++) if(t->next[i]){ret += t->next[i]->cnt;if(t->next[i]->cnt > 1) qu.push(t->next[i]);}}printf("%d\n", ret);}
};int main()
{int T;scanf("%d", &T);while(T--){Trip trip;scanf("%d", &n);for(int i = 0; i < n; i++){scanf("%s", name);trip.insert(name);}trip.solve();}return 0;
}