前言

最近字符串模拟赛中遇到了一道诡异的题，std 的方法是启发式合并 Trie 树，但我写了个更简单（？）的 BFS＋Trie树+LCA 做法。

后来得知是 CF 的题，就上来交一波，结果确实 AC 了。

这做法大概是对的，但是似乎有点慢（还难写）…

题意

有一棵以结点 $1$ 为根的树，每个结点上都有一个小写字母，对于以每个结点，从该结点出发向其子树中走，路上经过的点能形成一个字符串。求以每个结点为根的子树中能用此方法走出的不同的字符串数量。

链接

CF上原题还有一些奇怪的操作就不说了，对上述答案做一下简单的处理就行了。

Solution

显然这道题和 Trie 树有关。

对每个点 $i$ 记录一个 $mus[i]$，表示以 $i$ 为根的子树中有多少个重复的字符串。（mus的意思大概是minus，即“减”）

考虑 BFS 原树，将遍历到的点插入到 Trie 树中，BFS 时候记录一下 Trie 树上每个点对应的在原树上的点数组 $trie$，如果插入的时候发现这个字符串已经被插入到 Trie 树中，说明有一个重复的字符串，将这个点和 Trie 树上的点对应在原树上点的 LCA 的 $mus$ 数组 $+1$，更新上面的 $trie$ 数组。

最后跑一遍 DFS 统计答案即可。

值得一提的是可以发现如果字符串相同，那么他们在原树上深度必定相同，所以所以求 LCA 的时候不用跳到深度相同了。

至于为什么在 LCA 上打标记，大概是因为打标记的时候要走到两个结点相同的，最早出现有至少两个儿子的字符相同的结点，在这里打标记，才会不重不漏。可以画画图理解。

时间复杂度 $O(n\log n)$，足以通过本题。

Code

我这代码常数贼大，别人最慢也跑 $30s$，我直接干到 $50s$。

还好这题时限开得也大（

#include <bits/stdc++.h>
using namespace std;
const int maxn = 300010;
int ch[maxn][28], tot = 1, trie[maxn]; // ch 是 Trie 树
// trie[i] 代表在 Trie 树上编号为 i 的结点对应在原树上的结点编号。
vector<int> e[maxn];
void add(int x, int y) { e[x].push_back(y), e[y].push_back(x); }
string s;
int mus[maxn], siz[maxn], ans[maxn], v[maxn], a[maxn], n;
int f[maxn][32];
struct node // BFS 用结构体
{
    int fa, x, tfa; // fa，x 代表在原树中该结点父亲、该结点编号。
    // tfa 代表在 Trie 树上该结点的父亲
};
void dfs_lca(int x, int fa)
{
    f[x][0] = fa;
    for (int i = 1; i <= 31; i++)
        f[x][i] = f[f[x][i - 1]][i - 1];
    for (int i = 0; i < e[x].size(); i++)
        if (e[x][i] != fa)
            dfs_lca(e[x][i], x);
}
int LCA(int x, int y)
{
    if (x == y)
        return x;
    for (int i = 31; i >= 0; i--)
        if (f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];
}

void init()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> s;
    s = " " + s;
    int x, y;
    for (int i = 0; i < n - 1; i++)
        scanf("%d%d", &x, &y), add(x, y);
    dfs_lca(1, 0);
}
void bfs()
{
    queue<node> q;
    q.push((node){0, 1, 1});
    while (!q.empty())
    {
        node now = q.front();
        q.pop();
        //now.P();
        if (v[now.x])
            continue;
        v[now.x] = 1;
        int c = s[now.x] - 'a';
        if (ch[now.tfa][c]) // 如果当前结点对应字符串已经被插入到 Trie 树中
            mus[LCA(now.x, trie[ch[now.tfa][c]])]++, trie[ch[now.tfa][c]] = now.x;
        // 在两点 LCA 上打标记，并将 Trie 树上该点对应原树上结点更新
        else
            ch[now.tfa][c] = ++tot, trie[ch[now.tfa][c]] = now.x;
        // 没被插入就新开个点，并更新 trie 数组
        for (int i = 0; i < e[now.x].size(); i++)
            q.push((node){now.x, e[now.x][i], ch[now.tfa][c]});
    }
}
void dfs(int x, int fa) // DFS 统计答案
{
    siz[x] = 1;
    for (int i = 0; i < e[x].size(); i++)
    {
        if (e[x][i] != fa)
        {
            dfs(e[x][i], x);
            siz[x] += siz[e[x][i]];
            mus[x] += mus[e[x][i]];
        }
    }
    ans[x] = siz[x] - mus[x];
}
void out_put()
{
    int mx = -1, cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        if (mx == ans[i] + a[i])
            cnt++;
        else if (ans[i] + a[i] > mx)
            mx = ans[i] + a[i], cnt = 1;
    }
    cout << mx << endl
         << cnt << endl;
}
void solve()
{
    bfs();
    memset(v, 0, sizeof(v));
    dfs(1, 0);
}
int main()
{
    init();
    solve();
    out_put();
    return 0;
}