CF1168D Anagram Paths

蟾蜍 Ilya 拥有一棵以顶点 $1$ 为根的二叉树。树是一种无环连通图。如果选定一个顶点作为根，则称这棵树为有根树。若顶点 $u$ 和顶点 $v$ 之间有一条边，并且 $v$ 离根更近，则称 $u$ 是 $v$ 的子节点。叶子节点是指非根节点且没有子节点的顶点。 在 Ilya 的树中，每个顶点最多有两个子节点，每条边上都写有一个字符。该字符可以是小写英文字母，也可以是问号 '?'。 Ilya 将对树进行 $q$ 次更新。每次更新会将某条边上的字符替换为另一个字符。每次更新后，Ilya 需要判断这棵树是否可以“变为字母异位树”，如果可以，还要计算每个字母的“异位性”。这听起来有点难以解释，但我们会尽力说明。 首先，如果字符串 $a$ 可以通过重新排列字母（不改变字母本身）变成字符串 $b$，则称 $a$ 是 $b$ 的一个字母异位词。例如，字符串 "fortyfive" 是 "overfifty" 的字母异位词，但 "aabb" 不是 "bbba" 的字母异位词。 考虑从树的根到某个叶子的路径。该路径上的边上的字符按顺序组成一个字符串，我们称这个字符串与该叶子节点相关联。如果可以将所有问号替换为小写英文字母，使得所有叶子节点对应的字符串两两互为字母异位词，则称这棵树可以“变为字母异位树”。 如果树可以“变为字母异位树”，则对于每个字母 $c$，其“异位性”定义为在所有合法替换问号后的叶子路径字符串中，$c$ 出现次数的最大值。 请在每次更新后，判断树是否可以“变为字母异位树”。如果可以，输出所有字母的“异位性” $f(c)$ 与其字母序 $ind(c)$ 的乘积之和，即 $\sum{f(c) \cdot ind(c)}$，其中 $ind($"a"$)=1$，$ind($"b"$)=2$，……，$ind($"z"$)=26$。

输入的第一行包含两个整数 $n$ 和 $q$（$2 \leq n \leq 150\,000$，$1 \leq q \leq 150\,000$），分别表示树的顶点数和操作次数。 接下来的 $n-1$ 行描述初始树。第 $i$ 行包含一个整数 $p_i$ 和一个字符 $c_i$（$1 \leq p_i \leq i$，$c_i$ 是小写英文字母或问号 '?'），表示在顶点 $p_i$ 和 $i+1$ 之间有一条边，边上写有字符 $c_i$。 树的根为顶点 $1$，且每个顶点最多有两个子节点。 接下来的 $q$ 行描述操作。第 $i$ 行包含一个整数 $v$ 和一个字符 $c$（$2 \leq v \leq n$，$c$ 是小写英文字母或问号 '?'），表示将顶点 $p_{v-1}$ 到 $v$ 之间的边上的字符更新为 $c$。更新后的字符可以与原字符相同。

输出 $q$ 行。对于第 $i$ 次操作后，如果树无法“变为字母异位树”，则输出 "Fou"。 否则输出 "Shi" 和 $\sum{f(c) \cdot ind(c)}$ 的值。

在第一个样例中，第一次操作后，可以将所有边的字符都设置为同一个字母，这样每条路径上都会有 $1$ 个该字母，所以答案为 $1 \cdot (1+2+\ldots+26) = 351$。 第一次样例的第二次操作后，所有路径都应为 "a"，所以答案为 $1 \cdot 1 = 1$。 第一次样例的第三次操作后，有两条路径分别为 "a" 和 "b"，它们不是字母异位词，所以答案为 "Fou"。 第一次样例的第四次操作后，所有路径都应为 "b"，所以答案为 $1 \cdot 2 = 2$。 第二个样例第一次操作后，$f($'a'$)=2$，其余字母 $f(c)=1$，所以答案为 $1 \cdot (2+3+\ldots+26) + 2 = 352$。 第二个样例第二次操作后，每条路径都应包含一个 'a' 和一个 'b'，所以答案为 $1 \cdot 1 + 1 \cdot 2 = 3$。 由 ChatGPT 4.1 翻译