P17336 【MX-X30-T2】青蛙跳荷叶

池塘上有 $n$ 片荷叶，从 $1$ 编号到 $n$。现在有一棵大小为 $n$ 的有根树 $T$ 描述了这些荷叶的关系。$T$ 的根是 $1$。 每片荷叶上都有一个符号 $\texttt{U}$ 或者 $\texttt{D}$。这个符号表示如果青蛙在第 $i$ 片荷叶上，则： + 若符号是 $\texttt{U}$，则可以跳到 $T$ 上 $i$ 的祖先（不包含自身）。 + 若符号是 $\texttt{D}$，则可以跳到 $T$ 上 $i$ 的子孙（不包含自身）。 定义这棵树对青蛙是友好的，当且仅当青蛙可以从任意一个荷叶 $s$ 开始，跳过所有荷叶**至少一次**，回到 $s$。 由于一些原因，一些荷叶上的符号模糊了，记为 $\texttt{?}$ 符号。定义 $f(T)$ 为把每个 $\texttt{?}$ 符号替换成 $\texttt{U}$ 或 $\texttt{D}$ 后，这棵树对青蛙是友好的方案数。 由于一些原因，这些荷叶上的三种符号可能会发生局部变化，有 $q$ 次修改，每次修改让第 $x$ 片荷叶的符号变成 $y$，你需要在每次修改后和初始时求出 $f(T)$ 对 $998244353$ 取模的结果。

第一行包含两个整数 $n,q$。 第二行包含一个长度为 $n$ 的字符串，第 $i$ 个字符表示第 $i$ 片荷叶上的符号 $a_i$。 接下来 $n-1$ 行，第 $i$ 行两个整数 $u_i,v_i$，表示树 $T$ 上存在一条 $u_i$ 到 $v_i$ 的边。 接下来 $q$ 行，第 $i$ 行一个整数和一个字符 $x_i,y_i$，表示让第 $x_i$ 片荷叶的符号变成 $y_i$。

包含 $q+1$ 行，第 $i$ 行包含一个整数，表示前 $i-1$ 次修改按顺序执行完后，$f(T)$ 对 $998244353$ 取模的结果。

| 子任务编号 | $n,q\le$ | 特殊性质 | 分数| |:-:|:-:|:-:|:-:| | $1$ | $10$ | 无 | $13$| | $2$ | $10^3$ | A | $23$ | | $3$ | $10^3$ | B | $23$ | | $4$ | $3\times 10^5$ | A | $15$| | $5$ | $3\times 10^5$ | B | $15$ | | $6$ | $3\times 10^5$ | 无 | $11$ | 特殊性质 A：保证 $a_i,y_i\in \{\texttt{U},\texttt{D}\}$。 特殊性质 B：保证 $q=0$，且 $a_i=\texttt{?}$。 对于所有数据，保证 $1\le n\le 3\times 10^5$，$0\le q\le 3\times 10^5$。 保证 $1\le u_i,v_i\le n$，给定的边构成一棵以 $1$ 为根的树。 保证 $a_i,y_i\in \{\texttt{U},\texttt{D},\texttt{?}\}$。保证 $1\le x_i\le n$。