uva 11732 (trie树)

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

typedef long long LL;
const int maxnode = 4000 * 1000 + 10;

// 字母表为全体小写字母的Trie
struct Trie
{
    int head[maxnode]; // head[i]为第i个结点的左儿子编号
    int next[maxnode]; // next[i]为第i个结点的右兄弟编号
    char ch[maxnode];  // ch[i]为第i个结点上的字符
    int tot[maxnode];  // tot[i]为第i个结点为根的子树包含的叶结点总数
    int sz; // 结点总数
    LL ans; // 答案
    void clear() { sz = 1; tot[0] = head[0] = next[0] = 0; } // 初始时只有一个根结点
    
    // 插入字符串s（包括最后的‘\0‘），沿途更新tot
    void insert(const char *s)
    {
        int u = 0, v, n = strlen(s);
        tot[0]++;
        for(int i = 0; i <= n; i++) 
        {
            // 找字符a[i]
            bool found = false;
            for(v = head[u]; v != 0; v = next[v])
            if(ch[v] == s[i]) { found = true;break;}
            if(!found) 
            {
                v = sz++; // 新建结点
                tot[v] = 0;
                ch[v] = s[i];
                next[v] = head[u];//v添加右兄弟节点
                head[u] = v; // u添加左儿子节点
                head[v] = 0;
            }
            u = v;
            tot[u]++;
        }
    }
    
    // 统计LCP=u的所有单词两两的比较次数之和 
    void dfs(int depth, int u) 
    {
        int v;
        if(head[u] == 0) // 叶结点
            ans += tot[u] * (tot[u] - 1) * depth;
        else
        {
            int sum = 0;
            for(v = head[u]; v != 0; v = next[v])
                sum += tot[v] * (tot[u] - tot[v]); // 子树v中选一个串，其他子树中再选一个
            ans += sum / 2 * (2 * depth + 1); // 除以2是每种选法统计了两次
            for(v = head[u]; v != 0; v = next[v])
                dfs(depth+1, v);
        }
    }
    
    // 统计
    LL count() 
    {
        ans = 0;
        dfs(0, 0);
        return ans;
    }
};

#include<cstdio>
const int maxl = 1000 + 10;   // 每个单词最大长度

int n;
char word[maxl];
Trie trie;

int main() 
{
    int kase = 1;
    while(scanf("%d", &n) == 1 && n) 
    {
        trie.clear();
        for(int i = 0; i < n; i++)
        {
            scanf("%s", word);
            trie.insert(word);
        }
        printf("Case %d: %lld\n", kase++, trie.count());
    }
    return 0;
}