SP25892 PLNDTREE - Palindrome in a Tree

约翰拥有一棵包含 $N$ 个顶点的树。顶点从 $1$ 编号到 $N$，并将顶点 $1$ 作为树的根节点。每个节点都储存了一个字符 $C$。 现在，约翰正在进行一场别开生面的实验。他时常会调整某个节点上的字符，然后偶尔会随机挑选一个节点 $v$，希望用该节点子树中的所有字符拼成一个回文字符串。不过，约翰忙于其他实验，实在难以分身，需要你来帮他解决这个问题。 ### 输入 - 第一行是一个整数 $N$（$1 \le N \le 100000$），表示树中顶点的数量。 - 接下来的 $N-1$ 行中，每行有两个整数 $A$ 和 $B$（$1 \le A, B \le N$），表示顶点 $A$ 和 $B$ 之间有一条连接边。 - 下一行是一个长度为 $N$ 的字符串，第 $i$ 个字符代表第 $i$ 个节点上的字符。 - 随后的一行有一个整数 $M$（$1 \le M \le 100000$），表示查询的次数。接下来的 $M$ 行包含一个查询指令。 - 每个查询有两种格式： - `0 x C`：将节点 $x$ 的字符更改为 $C`。 - `1 x`：询问是否能将节点 $x$ 的子树中的所有字符拼接成一个回文字符串。保证至少存在一个这种形式的查询。 ### 输出 对每个 `1 x` 类型的查询，如果可以构成一个回文字符串，输出 `YES`；否则输出 `NO`。 输入中所有字符均为英语小写字母（a 至 z）。 ### 示例输入 ``` 7 5 4 1 5 6 3 1 7 5 6 6 2 abdaabc 7 1 1 1 5 1 3 0 7 a 1 1 0 4 z 1 5 ``` ### 示例输出 ``` NO YES YES YES NO ``` 在第二个查询中，可以组成回文字符串“badab”或“abdba”。在第三个查询中，只有一个字符 “d”，这个字符本身就是回文。 **本翻译由 AI 自动生成**

无

无