P8202 [传智杯 #4 决赛] [yLOI2021] 染色

传智杯 2021 决赛 G 题。

传智专修学院的老师给小智布置了一项任务。 老师给了小智一张纸，上面画着一棵有 $n$ 个节点的树（如果你不知道什么是树，可以参考上一题对此的解释）。老师还给了小智 $m$ 支彩色笔，每支笔的颜色都是不同的。老师想要让小智用这 $m$ 种颜色给树的节点涂色，使得这棵树满足如下约束： 1. 每个节点都被涂上了这 $m$ 个颜色之一的**一种**颜色。 2. 相邻两个节点（若存在一条边直接连接 $u$ 和 $v$，则我们称 $u,v$ 相邻）的颜色是不同的。 3. 任何一种颜色被使用的次数都不能超过 $\lfloor\frac{n}{3}\rfloor + 1$。 需要指出的是，虽然每个节点都必须被涂上一种颜色，但是每个颜色并不必须被使用。 如此简单的任务难不倒小智，所以小智提出了一个更困难的问题：他想知道一共有多少种染色的方案满足老师的要求。小智不会解答这个问题，所以来求助你，请你帮他解决他的问题。 因为方案数可能非常大，你只需要输出这个方案数除以 $998,244,353$ 的余数。两种染色方案不同当且仅当存在一个节点 $u$，使得 $u$ 在两种方案种被染上的颜色不同。

无

无

### 数据规模与约定 对于全部的测试点，保证 $1 \leq u, v \leq n\leq 100$，$n \leq m \leq 10^6$，保证给出的是一棵树。 ### 提示 **请注意常数因子对程序效率造成的影响**。