D - Phone List（hdu 1671） （字典树）

这道题是在vj上的字典树专题上面看到的，在vj上提交TLE，然后就懵了，怎么会超时呢？!然后在hdu上提交是MTE，原来是没有释放内存空间，然后稍作改动就AC了……

#include<bits/stdc++.h>
using namespace std;
string s;
struct cmp
{
    bool operator()(const string &a,const string &b)
    {
        if(a.size()!=b.size()) return a.size()>b.size();
        else return a>b;
    }
};
set<string,cmp>ss;
struct trie
{
    int v;
    trie *next[10];
}*a;
void init()
{
    a=new trie;
    for(int i=0;i<10;i++)
        a->next[i]=NULL;
}
int trie_insert()
{
    int n=s.size();
    trie *p=a;
    p->v++;
    for(int i=0;i<n;i++)
    {
        int id=s[i]-'0';
        if(p->next[id]==NULL)
        {
            p->next[id]=new trie;
            p=p->next[id];
            p->v=1;
            for(int j=0;j<10;j++)
                p->next[j]=NULL;
        }
        else
        {
            p->next[id]->v++;
            p=p->next[id];
        }
    }
    if(p&&p->v>1) return 1;
    else return 0;
}
void trie_delete(trie *root)//避免内存泄露
{
    if(root==NULL) return;
    else
    {
        for(int i=0;i<10;i++)
          trie_delete(root->next[i]);
    }
    delete (root);
}
int main()
{
    int t,n;
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        init();
        ss.clear();
        cin>>n;
        string aa;
        while(n--) cin>>aa,ss.insert(aa);
        int flag=1;
        for(set<string,cmp>::iterator it=ss.begin();it!=ss.end();it++)
        {
            s=*it;
            if(trie_insert())
            {
                flag=0;
                break;
            }
        }
        trie *root=a;
        trie_delete(root);
        if(flag) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}