#6289. 花朵

内存限制:512 MiB 时间限制:6000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: BigFairyNBC

题目描述

小 F 的生日还有一个多月,大 F 早早地准备起了礼物。

“你想要什么礼物呀?嗯...要不要好吃的?”

“才不要呢,我想要好看的花,永远不会凋谢的花。”

小 F 和大 F 一起生活的国家—— Fairy 国,可以抽象成一棵 N 个节点的树,每个节点就是一个城市,编号为 1\ldots N

大 F 要游历各个城市,为心爱的小 F 寻找好看的花。

Fairy 国的每个城市都有一座山,山上有恰好一朵永远不会凋谢的花,编号为 i 的城市的花的美丽值为 B_i 。大 F 要在 N 个城市中选出恰好 M 个,并摘来这 M 个城市中的 M 朵花送给小F。可是呢,如果树上的一条边连接的两个城市的花都被摘去,这条边就会塌陷,Fairy 国就会陷入分裂,大 F 作为一个善良的人,不希望这样的情况发生。所以,一种摘法合法,当且仅当对于每条边,这条边相连的两个节点的花不被同时摘去

大 F 希望小 F 快乐,小 F 的快乐程度将是摘来的 M 朵花的美丽程度的积。大 F 今天闲着没事,想要求出对于所有合法的摘法,小 F 的快乐程度之和对 998244353 取模的结果。

输入格式

第一行两个正整数 N M ,表示节点的个数与大 F 要为小 F 摘的花的朵数。

第二行 N 个整数 B_{1\ldots N} ,表示 N 朵花的美丽程度。

接下来 N-1 行,每行两个正整数,描述树上的一条边,保证形成一棵树。

输出格式

一个整数,表示对于所有合法的摘法,小 F 的快乐程度之和对 998244353 取模的结果。

样例

样例输入 1

5 3
3 5 4 8 11
1 2
1 3
2 4
2 5

样例输出 1

616

样例解释 1

有两种选法,选的点集分别是 \{1,4,5\} \{3,4,5\} ,所以答案是 3\times 8 \times 11 + 4 \times 8 \times 11 ,即 616

样例输入 2

15 6
9 10 2 7 2 4 5 9 3 2 1 9 3 10 7
12 3
4 3
15 8
2 14
7 14
8 14
3 15
6 1
11 1
7 11
9 14
8 5
10 5
13 15

样例输出 2

8214265

样例解释 2

这个样例解释,真要写起来的话就会很长,所以我不解释了,你自己写个暴力看看题意有没有理解错吧 QAQ ,辛苦啦。

数据范围与提示

对于所有数据,保证 1 \le M \le N \le 8 \times 10^4 0 \le B_i < 998244353

下表为各个 Subtask 的额外限制与得分,空格表示该项无额外限制。你只有通过一个 Subtask 的所有数据才能得到该 Subtask 的分。

Subtask 编号 N M 特殊限制 分值
1 \le 500 7
2 \le 4000 15
3 \le 10
4 \forall 1\le i < N ,读入的第 i 条边是 (i,i+1) 18
5 \forall 1\le i < N ,读入的第 i 条边是 (1,i+1) 20
6 25