小 A 有一棵 N 个点的带边权的树,树的每个节点有重量 wi 和价值 vi。
现在小 A 要从中选出若干个节点形成一个集合 S,满足这些节点重量之和 ≤M 并且构成一个连通块。小 A 是一个完美主义者,因此他只会选择节点价值之和最大的那些 S。我们称这样的集合 S 为完美的集合。
现在小 A 要从所有完美的集合中选出 K 个,并对这 K 个完美的集合分别进行测试。在这 K 次测试开始前,小 A 首先需要一个点 x 来放置他的测试装置,这个测试装置的最大功率为 Max。
接下来的每次测试,小 A 会对测试对象 S 中的所有点进行一次能量传输,对一个点 y 进行能量传输需要的功率为 dist(x,y)×vy,其中 dist(x,y) 表示点 x,y 在树上的最短路长度。因此,如果 S 中存在一个点 y,满足 dist(x,y)×vy>Max,测试就会失败。同时,为了保证能量传输的稳定性,测试装置所在的点 x 需要在集合 S 中,否则测试也会失败。
现在小 A 想知道,有多少种从所有完美的集合选出 K 个的方法,使得他能找到一个放置测试装置的点,来完成他的测试呢?
你只需要输出方案数对 11920928955078125 取模的结果。
输入格式
第一行四个正整数,表示 N,M,K,Max。
接下来一行 N 个正整数,表示 w1,…,wN。
接下来一行 N 个非负整数,表示 v1,…,vN。
接下来 N−1 行,每行三个正整数 Ai,Bi,Ci,表示树上存在一条长度为 Ci 的边连接节点 Ai,Bi。
输出格式
一个数,表示方案数第 11920928955078125 取模的结果。
样例数据
样例输入
7 3 2 4
1 1 2 2 1 2 2
1 1 1 2 1 2 2
1 2 1
1 3 2
1 4 2
2 5 1
2 6 2
4 7 3
样例输出
2
样例解释
完美的集合有 {1,2,5},{1,4},{2,6}。
从中选出 K 个且能完成测试的方案为选择 {1,2,5},{1,4} 或选择 {1,2,5},{2,6}。
子任务
子任务编号 | N≤ | M≤ | K≤ | 特殊性质 | 分值 |
---|---|---|---|---|---|
1 | 17 | 150 | 109 | 无 | 13 |
2 | 60 | 10000 | 1 | 11 | |
3 | 2 | 104 | w1=⋯=wN=1 | 19 | |
4 | 40 | 1200 | 109 | 无 | 20 |
5 | 60 | 10000 | 104 | 15 | |
6 | 109 | 22 |
对于 100% 的数据,N≤60,M≤10000,Ci≤10000,K,wi,vi≤109,Max≤1018。