P12355 「HCOI-R2」巡回演出

小 A 是 HCOI 国著名的演唱家，她打算开展一场巡回演出。

HCOI 国由 $n$ 个城市构成，可以被抽象为一棵 $n$ 个节点的有根树，首都是树的根 $r$。小 A 打算从 $r$ 开始，遍历全国进行演出。 具体地，设 $x$ 是小 A 当前在的位置，记录一个序列 $s$： - 初始时，$x=r$，$s=[r]$。 - 如果 $x$ 存在没有被访问过的儿子，任意选择一个儿子 $y$，在 $s$ 的最后插入 $y$，并前往 $y$。 - 如果不存在如上的 $y$：若 $x=r$，演出结束；否则前往 $x$ 的父亲。 我们称最后得到的 $s$ 是 $T$ 的一种**遍历方法**，选择不同的儿子可以得到多种遍历方法。可以发现遍历方法实际上是 $T$ 的 DFS 序。 小 A 的助手给出一张收费表 $\{w_{n-1}\}$，可以如下计算这次巡回演出的收入 $w(T,s)$： - 对于 $i\in[1,n]$，小 A 经过 $T$ 上 $s_{i}\to s_{i\bmod n+1}$ 的简单路径上的点（**不**包含 $s_{i}$，包含 $s_{i\bmod n+1}$）。 - 每次到达一个节点时，若当前是第 $i$ 次到达，小 A 收获 $w_i$ 枚金币作为报酬。 - $w(T,s)$ 为小 A 收到的金币枚数的总和。 小 A 的助手还给出了本次演出的遍历方法 $\{s_n\}$，定义一棵树 $T$ 合法当且仅当 $\{s_n\}$ 是它的一种**遍历方法**。你需要求出所有不同的合法 $T$ 的 $w(T,s)$ 之和对 $998244353$ 取模后的结果。 两棵有根树 $T$ 和 $T'$ 不相同当且仅当它们的根节点不同或存在一条在 $T$ 中出现而 $T'$ 中未出现的边。

无

无

#### 【样例解释 #1】 下文用 $(r,E)$ 来表示一棵有根树，其中 $E$ 是树的边集，$r$ 是树的根。 对于第一组数据，唯一一种合法的 $T$ 是 $(1,\{(1,2)\})$。小 A 经过两条路径 $1\to 2$ 和 $2\to 1$，经过了 $1,2$ 各一遍，故答案为 $1+1=2$。 对于第二组数据，合法的 $T$ 有 $(1,\{(1,2),(2,3)\}),(1,\{(1,2),(2,3)\})$，$w(T,s)$ 都是 $5$，故答案为 $5+5=10$。 对于第三组数据，合法的 $T$ 有 $(1,\{(1,2),(1,3),(1,4)\}),(1,\{(1,2),(1,3),(3,4)\}),(1,\{(1,2),$ $(2,3),(1,4)\}),(1,\{(1,2),(2,3),(2,4)\}),(1,\{(1,2),(2,3),(3,4)\})$，$w(T,s)$ 分别为 $9,8,8,$ $9,8$，故答案为 $9+8+8+9+8=42$。 对于第四组数据，一种合法的 $T$ 是 $(1,\{(1,3),(2,4),(3,2),(3,5)\})$，它的收入 $w(T,s)=13$。 #### 【数据范围与约定】 **本题采用捆绑测试。** | 子任务编号 | $\boldsymbol{n\le}$ | $\boldsymbol{\sum n\le}$ | 特殊性质 | 得分 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $4$ | $10^6$ | A | $5$ | | $2$ | $8$ | $40$ | A | $15$ | | $3$ | $12$ | $60$ | 无 | $10$ | | $4$ | $50$ | $200$ | 无 | $10$ | | $5$ | $100$ | $500$ | 无 | $10$ | | $6$ | $10^3$ | $5\times 10^3$ | B | $10$ | | $7$ | $10^3$ | $5\times 10^3$ | 无 | $5$ | | $8$ | $10^5$ | $2\times 10^5$ | B | $5$ | | $9$ | $10^5$ | $2\times 10^5$ | 无 | $15$ | | $10$ | $5\times10^5$ | $10^6$ | 无 | $15$ | - 特殊性质 A：$i\in[1,n]$，$s_i=i$。 - 特殊性质 B：$w_1=1$，对于 $i\in[2,n-1]$，$w_i=0$。 对于所有数据，$1\le T\le 10^5$，$2\le n\le 5\times10^5$，$\sum n\le 10^6$，$0\le w_i