http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3950

在分叉的根部统计即可。(dfs 时候传一个 bool 变量,详见代码)

(只贴出与题目有关的代码,宏定义见 GitHub

/* 0.032s */
const int mx = 1e6 + 5;

const int maxnode = mx;
const int sigma_size = 26;

struct Trie
{
    int nextid[maxnode][sigma_size];
    int cntnode[maxnode];
    int sz; // 结点总数

    void newnode(int u) {mem(nextid[u], -1), cntnode[u] = 0;}

    void clear() {sz = 1, newnode(0);}

    void insert(const char *s)
    {
        int i, u, *next;
        for (i = u = 0; s[i]; ++i, u = *next)
        {
            next = &nextid[u][s[i] - 'a'];
            if (*next == -1)
            {
                ++cntnode[u];
                newnode(sz);
                *next = sz++;
            }
        }
    }

    int dfs(int u = 0, int d = 0, bool isBranchRoot = true)
    {
        int cnt = 0, i;
        For(i, sigma_size) if (~nextid[u][i]) cnt += dfs(nextid[u][i], d + 1, cntnode[u] > 1);
        return cnt ? cnt : (isBranchRoot ? d : 0);
    }
} trie;

char s[mx];

int main()
{
    TT
    {
        trie.clear();
        QQ
        {
            SS(s);
            trie.insert(s);
        }
        PI(trie.dfs());
    }
    return 0;
}

Comments

comments powered by Disqus