数据前缀：cirrus。

不要相信标题！

洛谷-P8202

题目描述

给定一棵 $n$ 个节点的树和 $m$ 种不同颜色。要求对每个节点染一种颜色，使得：

1. 相邻节点颜色不同；
2. 每种颜色使用次数 $\le \lfloor n/3\rfloor+1$。

求染色方案数对 $998244353$ 取模。两种方案不同当且仅当存在节点 $u$ 颜色不同。

输入格式

本题包含多组测试数据。

第一行一个整数 $T$（$1\le T\le 300$），表示测试用例数。

对于每组测试用例：

• 第一行两个整数 $n,m$（$1\le n\le 200$，$n\le m\le 10^6$）；
• 接下来 $n-1$ 行，每行两个整数 $u,v$（$1\le u,v\le n$），表示树的一条边。

保证 $\sum n \le 1000$（单文件内所有测试用例之和），且给出的图是一棵树；$n=1$ 时无边行。

输出格式

对每组测试用例输出一行一个整数，表示方案数对 $998244353$ 取模的结果。

输入输出样例

样例 #1

样例输入 #1

3
4 4
1 2
1 3
3 4
3 3
1 2
1 3
5 5
1 2
1 3
2 4
3 5

样例输出 #1

108
12
1200

样例 #2

样例输入 #2

1
1 1

样例输出 #2

1

样例 #3

样例输入 #3

2
2 2
1 2
3 3
1 2
1 3

样例输出 #3

2
12

样例 #4

样例输入 #4

2
5 5
1 2
1 3
2 4
2 5
7 8
1 2
1 3
2 4
2 5
3 6
3 7

样例输出 #4

1140
929376

样例 #5

样例输入 #5

2
6 6
1 2
1 3
3 4
4 5
3 6
10 20
1 2
1 3
2 4
2 5
2 6
2 7
3 8
5 9
9 10

样例输出 #5

18750
688946281

样例 #6

样例输入 #6

1
18 1000000
18 9
17 8
16 8
15 7
14 7
13 6
12 6
11 5
10 5
9 4
8 4
7 3
6 3
5 2
4 2
3 1
2 1

样例输出 #6

801317415

样例 #7

样例输入 #7

2
9 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9

样例输出 #7

150958080
149509080

数据范围

• $1\le T\le 300$，$1\le n\le 200$，$n\le m\le 10^6$，$\sum n\le 1000$，给出的图是一棵树。
• 本题共 $100$ 个测试点。

$$ \begin{array}{|c|l|} \hline \text{测试点} & \text{性质} \\ \hline 1\sim20 & T \le 3 \text{ 且 } n, m\le 8 \\ 21\sim35 & T \le 2 \text{ 且 } m\le 100 \text{ 且 } u =1 \\ 36\sim43 & u=1\\ 44\sim61 & v=u+1 \\ 62\sim80 & n \le 50 \text{ 且 } \sum n\le 120\\ 81\sim89 & n \le 200\text{ 且 } \sum m \le 10^4 \\ 90\sim100 & n \le 200\\ \hline \end{array} $$

背景（与题目没有任何关系）

大佬大佬，mod 1e9+7 是什么意思

贡献说明

OpenAI Codex 协助分析标准程序在不同树形下的运行开销，落实数据范围与时限调整，增强正式数据（实质：卡常）、整理并补充样例，并通过独立算法核对样例答案、校验测评数据包。