题解

算法分析

本题是一个 树上的所有路径形成的不同颜色序列计数 问题，使用 广义后缀自动机 (Generalized Suffix Automaton) 来统计所有不同的子串。

问题本质

给定一棵树，每个节点有一个颜色（$0$ 到 $c-1$），需要计算所有简单路径对应的颜色序列中，不同的序列个数。

核心思路

1. 利用树的特殊性质：题目中提到"只与一个空地相邻的空地数量不超过 $20$ 个"，即叶子节点不超过 $20$ 个。

2. 从每个叶子节点开始DFS：

   • 由于叶子节点很少，可以从每个叶子节点作为起点进行DFS
   • 在DFS过程中，动态构建后缀自动机

3. 在线构建广义SAM：

   • 在DFS遍历树的过程中，将路径上的颜色序列依次加入SAM
   • SAM会自动去重，并可以实时计算新加入的字符带来的不同子串数

4. 实时统计答案：

   • 在SAM的extend函数中，实时累加新产生的不同子串数量
   • 利用SAM的性质：新节点的len - len[fail]就是该节点代表的新子串数量

算法标签

• 后缀自动机 (Suffix Automaton)
• 广义后缀自动机 (Generalized SAM)
• 树上DFS
• 字符串哈希/统计（通过SAM实现）
• 树上的路径枚举

关键代码解析

namespace SAM {
struct node {
    int fail, len, go[15];  // go数组大小为颜色种类数
} d[4000005];
int cnt;

int extend(int w, int last) {
    // 在线构建SAM，支持在树遍历过程中动态添加字符
    if (d[last].go[w]) {
        // 处理已有转移的情况（广义SAM的特有情况）
        // ...
    }
    
    // 正常SAM扩展过程
    int u = last, v = ++cnt;
    d[v].len = d[u].len + 1;
    
    for (; !d[u].go[w]; u = d[u].fail)
        d[u].go[w] = v;
    
    // 实时统计新产生的不同子串数
    ans += d[v].len - d[u].len - 1;
    // ... 处理fail指针等
    return v;
}
}

// 从每个叶子节点开始DFS
void dfs(int v, int f, int last) {
    last = SAM::extend(a[v], last);  // 将当前节点颜色加入SAM
    
    for (int i : g[v]) {
        if (i != f)
            dfs(i, v, last);  // 递归遍历
    }
}

int main() {
    // 输入处理
    // ...
    
    // 关键：只从叶子节点开始DFS
    for (int i = 1; i <= n; i++) {
        if (g[i].size() == 1)  // 叶子节点
            dfs(i, 0, 0);
    }
    
    cout << ans;
}

时间复杂度

• 叶子节点数：最多 $20$ 个
• 每个DFS：$O(n)$，但受SAM构建影响
• SAM构建：均摊 $O(n)$
• 总体复杂度：$O(20 \times n)$，在 $n \leq 10^5$ 时可接受

空间复杂度

• $O(n \times c)$，主要用于存储SAM节点和转移边

算法优化点

1. 利用叶子数少的性质：避免从所有节点开始DFS，大大减少计算量
2. 在线构建SAM：在DFS过程中动态构建，避免存储所有路径
3. 实时统计：在extend过程中直接累加答案，避免后续遍历

总结

本题通过结合树的特性和广义后缀自动机，高效解决了树上所有路径对应不同颜色序列的计数问题。关键在于发现叶子节点很少的性质，以及使用在线SAM构建来实时去重和统计。