#2473. 「九省联考 2018」秘密袭击

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

题目描述

We could have had it all……

我们本该,拥有一切

Counting on a tree……

何至于此,数数树上

Counting on a Tree(CoaT)即是本题的英文名称。

Access Globe 最近正在玩一款战略游戏。在游戏中,他操控的角色是一名 C 国士兵。他的任务就是服从指挥官的指令参加战斗,并在战斗中取胜。C 国即将向 D 国发动一场秘密袭击。作战计划是这样的:选择 D 国的 ss 个城市,派出 C 国战绩最高的 ss 个士兵分别秘密潜入这些城市。每个城市都有一个危险程度 did_i,C 国指挥官会派遣战绩最高的士兵潜入所选择的城市中危险程度最高的城市,派遣战绩第二高的士兵潜入所选择的城市中危险程度次高的城市,以此类推(即派遣战绩第 ii 高的士兵潜入所选择城市中危险程度第 ii 高的城市)。D 国有 nn 个城市,n1n − 1 条双向道路连接着这些城市,使得这些城市两两之间都可以互相到达。为了任务执行顺利,C 国选出的 ss 个城市中,任意两个所选的城市,都可以不经过未被选择的城市互相到达。

Access Globe 操控的士兵的战绩是第 kk 高,他希望能估计出最终自己潜入的城市的危险程度。Access Globe 假设 C 国是以等概率选出任意满足条件的城市集合 SS,他希望你帮他求出所有可能的城市集合中,Access Globe 操控的士兵潜入城市的危险程度之和。如果选择的城市不足 kk 个,那么 Access Globe 不会被派出,这种情况下危险程度为 00

当然,你并不想帮他解决这个问题,你也不打算告诉他这个值除以 998,244,353998, 244, 353 的余数,你只打算告诉他这个值除以 64,12364,123 的余数。

输入格式

从标准输入中读入数据。

11 行包含 33 个整数 n,k,Wn, k, W,表示 D 国城市的个数、Access Globe 所操控士兵潜入的城市战绩排名以及 D 国的所有城市中最大的危险程度;

22 行包含 nn11WW 之间的整数 d1,d2,,dnd_1, d_2 ,\dots , d_n,表示每个城市的危险程度;

33 行到第 n+1n + 1 行,每行两个整数 xi,yix_i , y_i,表示 D 国存在一条连接城市 xix_i 和城市 yiy_i 的双向道路。

输出格式

输出到标准输出中。

输出一个整数,表示所有可行的城市集合中,Access Globe 操控的士兵潜入城市的危险程度之和除以 64,12364,123 的余数。

样例

样例输入 1

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

样例输出 1

11

样例解释 1

D 国地图如下,其中危险程度为 dd 的城市的形状是 (d+3)(d + 3) 边形。

Explanation

以下是所有符合条件且选择的城市不少于 33 个的方案:

  • 选择城市 1,2,31, 2, 3,Access Globe 的士兵潜入的城市危险程度为 11
  • 选择城市 1,2,3,41, 2, 3, 4,Access Globe 的士兵潜入的城市危险程度为 11
  • 选择城市 1,2,3,51, 2, 3, 5,Access Globe 的士兵潜入的城市危险程度为 11
  • 选择城市 1,2,3,4,51, 2, 3, 4, 5,Access Globe 的士兵潜入的城市危险程度为 22
  • 选择城市 1,2,41, 2, 4,Access Globe 的士兵潜入的城市危险程度为 11
  • 选择城市 1,2,51, 2, 5,Access Globe 的士兵潜入的城市危险程度为 11
  • 选择城市 1,2,4,51, 2, 4, 5,Access Globe 的士兵潜入的城市危险程度为 22
  • 选择城市 1,4,51, 4, 5,Access Globe 的士兵潜入的城市危险程度为 22

而在选择的城市少于 33 时,Access Globe 的士兵潜入的城市危险程度均为 00

所以你应该输出 (1+1+1+2+1+1+2+2)mod64,123=11(1 + 1 + 1 + 2 + 1 + 1 + 2 + 2) \bmod 64, 123 = 11

样例输入 2

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

样例输出 2

435

数据范围与提示

测试点n=n=kk\leqW=W=地图是一条链
1133nn1,6661,666保证
221515不保证
332020
443003001010保证
551,6661,6661,6661,666
665050不保证
77200200
88500500
991,1111,11110210^210210^2
101050501,1111,111
111110210^21,6661,666
12121,6661,666
1313200200
1414500500
1515nn
1616
1717
1818
1919
2020

对于所有的数据,1kn,1diW,1n,k,W1,6661 \leq k \leq n, 1 \leq d_i \leq W, 1\leq n, k, W \leq 1, 666