学步园

字典树，需要用fre[u][v]记录出现频率。最后遍历字典树如果该节点出现频率no more than 5，ans++并返回。否则遍历其不为空的子节点。

代码中的两种dfs都可以，WA了好久最后是因为sz没有初始化为1。==

#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<ctype.h>
#include<map>
#include<time.h>
#include<bitset>
using namespace std;
//hiho 1107
int N;
const int maxnode=2000010;
const int sigmasize=26;
int sz;
int ch[maxnode][sigmasize];
int fre[maxnode][sigmasize];
int f[maxnode];
int val[maxnode];
int ans;
int idx(char c)
{
    return c-'a';
}
void Insert(char *s,int v)
{
    int u=0,n=strlen(s);
    for(int i=0;i<n;i++)
    {
        int c=idx(s[i]);
        if(!ch[u][c])
        {
            memset(ch[sz],0,sizeof(ch[sz]));
            val[sz]=0;
            ch[u][c]=sz++;
        }
        fre[u][c]++;
        u=ch[u][c];
        f[u]++;
    }
    val[u]=v;
}
void dfs2(int u)//u is the index of node
{
    if(u==0)
    {
        return;
    }
    if(f[u]>0&&f[u]<=5)
    {
       // cout<<u<<" "<<i<<" "<<ch[u][i]<<endl;
        ans++;
        return;
    }
    for(int i=0;i<26;i++)
    {
        if(ch[u][i]>0)
        {
            dfs2(ch[u][i]);
        }
    }
}
void dfs(int u,int v)
{
    if(ch[u][v]==0)
    {
        return;
    }
    if(fre[u][v]>0&&fre[u][v]<=5)
    {
        ans++;
        return;
    }
    else if(fre[u][v]>5)
    {
        for(int i=0;i<26;i++)
        {
            dfs(ch[u][v],i);
        }
    }
}
int main()
{
    freopen("input.txt","r",stdin);
    //freopen("data.txt","r",stdin);
    //freopen("out1.txt","w",stdout);
    scanf("%d",&N);
    char c[2000000];
    memset(ch,0,sizeof(ch));
    memset(fre,0,sizeof(fre));
    memset(val,0,sizeof(val));
    sz=1;//got a WA wothout it
    for(int i=0;i<N;i++)
    {
        scanf("%s",&c);
        Insert(c,1);

    }
    ans=0;
    for(int i=0;i<26;i++)
    {
        dfs2(ch[0][i]); //this is also accepted
        //dfs(0,i);
    }
    printf("%d\n",ans);
    return 0;
}