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

Luogu
IDLGP8202
Time500ms
Memory512MB
DifficultyP6
O2优化树形 DP容斥原理传智杯
传智专修学院的老师给小智布置了一项任务。 老师给了小智一张纸,上面画着一棵有 $n$ 个节点的树(如果你不知道什么是树,可以参考上一题对此的解释)。老师还给了小智 $m$ 支彩色笔,每支笔的颜色都是不同的。老师想要让小智用这 $m$ 种颜色给树的节点涂色,使得这棵树满足如下约束: 1. 每个节点都被涂上了这 $m$ 个颜色之一的**一种**颜色。 2. 相邻两个节点(若存在一条边直接连接 $u$ 和 $v$,则我们称 $u,v$ 相邻)的颜色是不同的。 3. 任何一种颜色被使用的次数都不能超过 $\lfloor\frac{n}{3}\rfloor + 1$。 需要指出的是,虽然每个节点都必须被涂上一种颜色,但是每个颜色并不必须被使用。 如此简单的任务难不倒小智,所以小智提出了一个更困难的问题:他想知道一共有多少种染色的方案满足老师的要求。小智不会解答这个问题,所以来求助你,请你帮他解决他的问题。 因为方案数可能非常大,你只需要输出这个方案数除以 $998,244,353$ 的余数。两种染色方案不同当且仅当存在一个节点 $u$,使得 $u$ 在两种方案种被染上的颜色不同。 ## Input 第一行是两个整数,依次表示树的节点数 $n$ 和颜色的个数 $m$。 接下来 $(n - 1)$ 行,每行两个整数 $u, v$,表示树上有一条连接 $u, v$ 的边。 ## Output 输出一行一个整数,表示方案数除以 $998,244,353$ 的余数。 [samples] ## Background 传智杯 2021 决赛 G 题。 ## Note ### 数据规模与约定 对于全部的测试点,保证 $1 \leq u, v \leq n\leq 100$,$n \leq m \leq 10^6$,保证给出的是一棵树。 ### 提示 **请注意常数因子对程序效率造成的影响**。
Samples
Input #1
4 4
1 2
1 3
3 4
Output #1
108
Input #2
3 3
1 2
1 3
Output #2
12
Input #3
5 5
1 2
1 3
2 4
3 5
Output #3
1200
Input #4
5 5
1 2
1 3
2 4
2 5
Output #4
1140
Input #5
7 8
1 2
1 3
2 4
2 5
3 6
3 7
Output #5
929376
Input #6
6 6
1 2
1 3
3 4
4 5
3 6
Output #6
18750
Input #7
10 20
1 2
1 3
2 4
2 5
2 6
2 7
3 8
5 9
9 10
Output #7
688946281
API Response (JSON)
{
  "problem": {
    "name": "[传智杯 #4 决赛] [yLOI2021] 染色",
    "description": {
      "content": "传智专修学院的老师给小智布置了一项任务。 老师给了小智一张纸,上面画着一棵有 $n$ 个节点的树(如果你不知道什么是树,可以参考上一题对此的解释)。老师还给了小智 $m$ 支彩色笔,每支笔的颜色都是不同的。老师想要让小智用这 $m$ 种颜色给树的节点涂色,使得这棵树满足如下约束: 1. 每个节点都被涂上了这 $m$ 个颜色之一的**一种**颜色。 2. 相邻两个节点(若存在一条边直接连接 $u",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 500,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8202"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "传智专修学院的老师给小智布置了一项任务。\n\n老师给了小智一张纸,上面画着一棵有 $n$ 个节点的树(如果你不知道什么是树,可以参考上一题对此的解释)。老师还给了小智 $m$ 支彩色笔,每支笔的颜色都是不同的。老师想要让小智用这 $m$ 种颜色给树的节点涂色,使得这棵树满足如下约束:\n\n1. 每个节点都被涂上了这 $m$ 个颜色之一的**一种**颜色。\n2. 相邻两个节点(若存在一条边直接连接 $u...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments