P5439 【XR-2】永恒

> 我一直认为这世界没有永恒，如果非要说永恒，宇宙间唯一的永恒就是——所有的一切都会随着时光消失。——梧桐《那片星空，那片海》

有一棵 $n$ 个点的永恒的树，树中每个点 $x(1 \le x \le n)$ 上都有一个永恒的字符串 $S(x)$。 但这世界没有永恒，所有的一切都会随着时光消失。我们只能给每个所谓永恒的东西定义一个永恒值 $f$。这个值本身没有意义，只是一个象征罢了。 - 一个字符串 $S$ 的永恒值 $f(S)$ 定义为它的长度 $\mathrm{Len}(S)$，即： $$f(S) = \mathrm{Len}(S)$$ - 树上的一条无向路径 $K = [u, v](u < v)$ 指的是 $u,v$ 之间的简单路径（包括 $u, v$），其永恒值 $f(K)$ 定义为路径上所有不同的无序点对 $(x, y)(x \in K, y \in K, x < y)$ 上的字符串 $S(x), S(y)$ 的最长公共前缀 $\mathrm{LCP}(S(x), S(y))$ 的永恒值 $f(\mathrm{LCP}(S(x), S(y)))$ 之和，即： $$f(K) = \sum_{x \in K, y \in K, x < y} f(\mathrm{LCP}(S(x), S(y)))$$ - 一棵树 $T$ 的永恒值 $f(T)$ 定义为树上所有的无向路径 $[u, v](u \in T, v \in T, u < v)$ 的永恒值之和，即： $$f(T) = \sum_{u \in T, v \in T, u < v} f([u,v])$$ 特别的是，树中每个点上的字符串都来自一棵永恒的以点 $1$ 为根的 Trie 树，即每个树中的点都对应着一个 Trie 树中的点，点上的字符串就是 Trie 树中从根节点到其对应的点形成的字符串。 你需要求出这棵树的永恒值，答案对 $998244353$ 取模。

无

无

【样例 $1$ 说明】 所有的 $S(x)$ 为： $S(1) = \texttt{"mayqueen"}$ $S(2) = \texttt{"mayking"}$ $S(3) = \texttt{"market"}$ 所有的 $f(\mathrm{LCP}(S(x), S(y)))$ 为： $f(\mathrm{LCP}(S(1), S(2))) = f(\mathrm{LCP}(\texttt{"mayqueen"}, \texttt{"mayking"})) = f(\texttt{"may"}) = \mathrm{Len}(\texttt{"may"}) = 3$ $f(\mathrm{LCP}(S(1), S(3))) = f(\mathrm{LCP}(\texttt{"mayqueen"}, \texttt{"market"})) = f(\texttt{"ma"}) = \mathrm{Len}(\texttt{"ma"}) = 2$ $f(\mathrm{LCP}(S(2), S(3))) = f(\mathrm{LCP}(\texttt{"mayking"}, \texttt{"market"})) = f(\texttt{"ma"}) = \mathrm{Len}(\texttt{"ma"}) = 2$ 所有的 $f([u, v])$ 为： $f([1,2]) = f(\mathrm{LCP}(S(1), S(2))) = 3$ $f([1,3]) = f(\mathrm{LCP}(S(1), S(2))) + f(\mathrm{LCP}(S(1), S(3))) + f(\mathrm{LCP}(S(2), S(3))) = 3 + 2 + 2 = 7$ $f([2,3]) = f(\mathrm{LCP}(S(2), S(3))) = 2$ 所以： $f(T) = f([1,2]) + f([2,3]) + f([1,3]) = 3 + 7 + 2 = 12$ 【数据规模与约定】 **本题采用捆绑测试。** Subtask 1（3 points）：$n, m \le 10$，时限 1s。 Subtask 2（5 points）：$n, m \le 100$，时限 1s。 Subtask 3（9 points）：$n, m \le 1000$，时限 1s。 Subtask 4（7 points）：$n, m \le 5000$，时限 2s。 Subtask 5（9 points）：$n, m \le 20000$，时限 3s。 Subtask 6（11 points）：$n, m \le 10^5$，时限 4s。 Subtask 7（19 points）：$m=2$，时限 3s。 Subtask 8（37 points）：无特殊限制，时限 10s。 对于 $100\%$ 的数据，$2 \le n,m \le 3\times 10^5$。