思考了一會兒，發(fā)現(xiàn)這題目要一層層的考慮。

        即，在插入一個字符串str到Trie的時候，同時更新答案

        兩個字符串，在對比到第i個位置不同時，通過的比較次數(shù)是(i<<1)+1，注意，此處i是從0開始的。

        假若到最后都相同的話，比較的次數(shù)是(length+1)<<1，即length*2+2，要考慮末尾的/0

        抱著這樣的想法，我發(fā)現(xiàn)普通的Trie并不好維護這個玩意，看了題解才明白。

        沒想到在這里遇見了左兒子右兄弟表示法，也是，這個表示法是比較符合這個場景的

        邊插入邊計算答案，每到一層就+上那些當前位和自己不同的字符串的比較次數(shù)，到最后+上和自己相同的比較次數(shù)

        用val數(shù)組來維護當前通過該點的字符串個數(shù)

        總之感覺用法很好，在Trie中插入節(jié)點的時候有點數(shù)組模擬鄰接表的感覺了

#include <iostream>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;int n,kcase=1,sz,bro[4000010],son[4000010],val[4000010];char str[1005],ch[4000010];void init(),ins(char* str);ll ans;int main(){    ios_base::sync_with_stdio(false);    while(cin>>n&&n){        init();        ans=0;        for(int i=0;i<n;++i){            cin>>str;            ins(str);        }        cout<<"Case "<<kcase++<<": "<<ans<<endl;    }    return 0;}void init(){    sz=1;    ch[0]=bro[0]=son[0]=val[0]=0;}void ins(char* str){    int len=strlen(str),u=0,p;    for(int i=0;i<=len;++i){        for(p=son[u];p;p=bro[p])        if(ch[p]==str[i])            break;        if(!p){            p=sz++;            ch[p]=str[i];            bro[p]=son[u];            son[p]=val[p]=0;            son[u]=p;        }        ans+=(val[u]-val[p])*((i<<1)+1);        if(len==i){            ans+=val[p]*((i+1)<<1);            ++val[p];        }        val[u]++;        u=p;    }}