POJ 2418 Hardwood Species（辞書ツリー）

Hardwood Species
テーマリンク:
http://poj.org/problem?id=2418
問題解決の考え方：
辞書の木の問題ですが、dfsのちょっとしたテクニックを使います。もちろんmapでもできます。
ACコード(map):

#include <iostream>
#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
using namespace std;

const int maxn = 1000010;
string str,name[10010];
int ans = 0,tot = 0;

int main(){

    string str;
    map<string,int> tree;
    while(getline(cin,str) && str!=""){
        if(tree.find(str) == tree.end()){
            tree[str] = 1;
            name[ans++] = str;
        }
        else
            tree[str]++;
        tot++;
    }
    sort(name,name+ans);
    for(int i = 0; i < ans; i++)
        printf("%s %.4lf
",name[i].c_str(),tree[name[i]]*1.0/tot*100);
    return 0;
}

ACコード(辞書ツリー):

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

struct node{
    int cnt;
    struct node *next[130];
    node(){
        cnt = 0;
        memset(next,0,sizeof(next));
    }
};

node *root = NULL;
int n;

void build(char *s){
    node *p = root,*tmp;
    int l=strlen(s);
    for(int i = 0; i < l; i++){
        if(p->next[s[i]] == NULL){
            tmp = new node;
            p->next[s[i]] = tmp;
        }
        p = p->next[s[i]];
    }
    p->cnt++;
}

void dfs(node *root){
    static char word[31];
    static int pos;
    int i;
    if(root->cnt){   //  cnt  0，          
        word[pos] = '\0';
        if(word[0])
            printf("%s %.4lf
",word,root->cnt*100*1.0/n);
    }
    for(int i = 0; i < 130; i++){
        if(root->next[i]){
            word[pos++] = i;
            dfs(root->next[i]);
            pos--;
        }
    }
}

int main(){
    char str[31];
    n = 0;
    root = new node;
    while(gets(str) && str!=""){
        build(str);
        n++;
    }
    dfs(root);
    return 0;
}