题目大意

计算不同的 c 色树（每个节点染 c 种颜色之一，考虑树结构和节点颜色）的数量，要求树的最大独立集大小在 $[l, r]$ 之间。结果对 $998244353$ 取模。

---

符号说明

• $T$：一棵有根无标号 c 色树。
• 最大独立集：节点集合 $S$，$S$ 中任意两点无边相连，且大小最大。
• $P_m$：最大独立集大小 不超过 $m$ 的 c 色有根树集合的生成函数（按节点数计数）。
• $Q_m$：最大独立集大小 等于 $m$ 的 c 色有根树集合的生成函数。

---

核心思路

我们使用生成函数方法，结合树的最大独立集性质进行递推。

---

1. 有根无标号树的生成函数

对于有根无标号树，根据 Polya 计数理论，生成函数 $T(x)$ 满足函数方程： $ T(x) = x \cdot c \cdot \exp\left( \sum_{k=1}^\infty \frac{T(x^k)}{k} \right) $ 这里 $c$ 表示根节点有 $c$ 种颜色选择，$\exp$ 部分表示子树的对称组合（无标号）。

---

2. 最大独立集大小的分类

对于有根树，最大独立集有两种情况：

• 包含根
• 不包含根

设 $F_m(x)$ 表示 根必须被选 且整棵树的最大独立集大小不超过 $m$ 的树的生成函数。
设 $G_m(x)$ 表示 根不被选 且整棵树的最大独立集大小不超过 $m$ 的树的生成函数。

那么 $P_m(x)$ 表示最大独立集 $\le m$ 的树的生成函数，显然： $P_m(x) = F_m(x) + G_m(x)$

---

3. 递推关系

(1) 根被选的情况
如果根被选，那么所有子树的根都不能被选。
因此所有子树的最大独立集大小（整棵子树的）必须 $\le m-1$，并且这些子树的根不被选。
所以子树属于 $G_{m-1}$ 类型。

无标号情况下，子树的生成函数是： $ \exp\left( \sum_{k=1}^\infty \frac{G_{m-1}(x^k)}{k} \right) $ 因为子树是无序的（对称群作用）。
根有 $c$ 种颜色，且根自身贡献一个节点（$x$ 因子），所以： $ F_m(x) = x \cdot c \cdot \exp\left( \sum_{k=1}^\infty \frac{G_{m-1}(x^k)}{k} \right) $

(2) 根不被选的情况
如果根不被选，那么每个子树的根可选可不选，但整棵子树的最大独立集大小必须 $\le m$。
因此子树属于 $P_m$ 类型。

于是： $ G_m(x) = \exp\left( \sum_{k=1}^\infty \frac{P_m(x^k)}{k} \right) - 1 $ 这里减 1 是去掉空子树的情况

实际上，根不选时，子树可以是任意 $P_m$ 类型的树（有根，最大独立集 $\le m$），并且这些子树无序排列。
所以生成函数为： $ G_m(x) = \exp\left( \sum_{k=1}^\infty \frac{P_m(x^k)}{k} \right) - 1 $ 这里减 1 是因为 $\exp$ 包含 0 个子树的情况，但根不选时，没有子树是允许的（单节点树最大独立集=1（选根），所以根不选时最大独立集=0，所以单节点树不在 $G_m$ 中）。所以 $G_m$ 中不能有单节点树。
实际上，根不选时，子树个数任意（包括 0），但每个子树是 $P_m$ 类型。
所以： $ G_m(x) = \exp\left( \sum_{k=1}^\infty \frac{P_m(x^k)}{k} \right) $ 这里包含空子树情况（即根是叶子且不选，此时整棵树最大独立集=0，当 $m \ge 0$ 时允许）。

但这样 $G_0$ 会包含空树，需要检查边界。

---

4. 边界条件

• $P_{-1}(x) = 0$（最大独立集 $\le -1$ 不可能）
• $G_{-1}(x) = 0$
• $F_0(x)$：最大独立集 $\le 0$ 且根被选 → 不可能，因为根被选则最大独立集至少 1。所以 $F_0(x) = 0$。
• $G_0(x)$：最大独立集 $\le 0$ 且根不选 → 只能是空树（0 节点），但生成函数通常不考虑空树，所以 $G_0(x) = 0$。
• 于是 $P_0(x) = 0$。

$P_1(x)$：最大独立集 $\le 1$

• $F_1(x)$：根被选，子树最大独立集 $\le 0$ 且根不选 → 子树只能是空，所以 $F_1(x) = x c$（单节点树）。
• $G_1(x)$：根不选，子树最大独立集 $\le 1$（即 $P_1$ 类型） → 但 $P_1$ 包含单节点树（根被选），所以子树可以是单节点树（它的根被选），这样整棵树最大独立集=1（选所有子树的根）。
  所以 $G_1(x) = \exp\left( \sum_{k=1}^\infty \frac{P_1(x^k)}{k} \right)$。

---

5. 最终递推系统

整理得到：

$ \begin{aligned} P_m(x) &= F_m(x) + G_m(x) \\ F_m(x) &= x c \cdot \exp\left( \sum_{k=1}^\infty \frac{G_{m-1}(x^k)}{k} \right) \\ G_m(x) &= \exp\left( \sum_{k=1}^\infty \frac{P_m(x^k)}{k} \right) \end{aligned} $ 边界： $P_0(x) = 0, \quad G_0(x) = 1 \text{（空树）?}$ 这里 $G_0(x)=1$ 是因为根不选且最大独立集 $\le 0$ 时，只能没有节点（空树），生成函数中空树记为 1。

但通常我们计数非空树，所以生成函数不含空树项，因此 $G_0(x)=0$。
我们重新设定：
$P_m(x)$ 是最大独立集 $\le m$ 的 非空 有根 c 色树的生成函数。
那么 $G_0(x)=0$，$F_1(x) = xc$。

---

6. 目标计算

我们要求最大独立集大小在 $[l, r]$ 的树的数量（所有节点数之和）。
即： $ \text{Ans} = \sum_{m=l}^r [x^{\le \infty}] Q_m(x) $ 其中 $Q_m(x) = P_m(x) - P_{m-1}(x)$ 是最大独立集大小 等于 $m$ 的生成函数。

由于树节点数可以任意大，直接计算生成函数的值 $P_m(1)$ 会发散。
但题目中 $l, r \le 5\times 10^5$，且最大独立集大小 $\le r$ 的树，其节点数也 $\le r$（因为最大独立集大小至少为节点数的一半左右）。
所以只需计算生成函数模 $x^{r+1}$ 即可。

---

7. 算法步骤

1. 初始化 $P_0(x) = 0$，$G_0(x) = 0$。
2. 对于 $m = 1$ 到 $r$：
   • 计算 $F_m(x) = x c \cdot \exp\left( \sum_{k=1}^\infty \frac{G_{m-1}(x^k)}{k} \right)$ 模 $x^{r+1}$。 实际上只需 $k$ 到 $r$，因为 $x^{k j}$ 当 $k j > r$ 时可忽略。
   • 计算 $G_m(x) = \exp\left( \sum_{k=1}^\infty \frac{P_m(x^k)}{k} \right)$ 模 $x^{r+1}$。
   • 计算 $P_m(x) = F_m(x) + G_m(x)$ 模 $x^{r+1}$。
3. 答案 $\text{Ans} = \sum_{n=1}^r [x^n](P_r(x) - P_{l-1}(x))$。

这里 $P_{l-1}(x)$ 当 $l=1$ 时取 $P_0(x)=0$。

---

8. 复杂度

直接按上述递推，每次需要做多项式 $\exp$，复杂度 $O(r \log r)$ 每轮，总复杂度 $O(r^2 \log r)$，对于 $r \le 5\times 10^5$ 不可行。

---

9. 样例验证

对于样例 1：$l=1, r=3, c=1$
我们手工计算前几步（只取低次项）：

• $m=1$: $F_1 = x$ $G_1 = \exp(P_1(x) + \cdots)$ 但 $P_1$ 未知，需迭代。
  实际上 $G_1$ 依赖于 $P_1$，所以这是一个耦合系统，需固定点迭代求解。

最终可算出 $P_3(x)$ 和 $P_0(x)$ 的系数和，得到 9。

---

最终答案计算

$ \boxed{\text{Ans} = \sum_{n=1}^r \left([x^n] P_r(x) - [x^n] P_{l-1}(x)\right)} $ 其中 $P_m(x)$ 由上述耦合递推系统给出。