#2462. 「2018 集训队互测 Day 1」完美的集合

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

题目描述

小 A 有一棵 NN 个点的带边权的树,树的每个节点有重量 wiw_i 和价值 viv_i

现在小 A 要从中选出若干个节点形成一个集合 SS,满足这些节点重量之和 M\leq M 并且构成一个连通块。小 A 是一个完美主义者,因此他只会选择节点价值之和最大的那些 SS。我们称这样的集合 SS 为完美的集合。

现在小 AA 要从所有完美的集合中选出 KK 个,并对这 KK 个完美的集合分别进行测试。在这 KK 次测试开始前,小 A 首先需要一个点 xx 来放置他的测试装置,这个测试装置的最大功率为 MaxMax

接下来的每次测试,小 A 会对测试对象 SS 中的所有点进行一次能量传输,对一个点 yy 进行能量传输需要的功率为 dist(x,y)×vydist(x,y)\times v_y,其中 dist(x,y)dist(x,y) 表示点 x,yx,y 在树上的最短路长度。因此,如果 SS 中存在一个点 yy,满足 dist(x,y)×vy>Maxdist(x,y)\times v_y>Max,测试就会失败。同时,为了保证能量传输的稳定性,测试装置所在的点 xx 需要在集合 SS 中,否则测试也会失败。

现在小 A 想知道,有多少种从所有完美的集合选出 KK 个的方法,使得他能找到一个放置测试装置的点,来完成他的测试呢?

你只需要输出方案数对 1192092895507812511920928955078125 取模的结果。

输入格式

第一行四个正整数,表示 N,M,K,MaxN,M,K,Max

接下来一行 NN 个正整数,表示 w1,,wNw_1,\dots,w_N

接下来一行 NN非负整数,表示 v1,,vNv_1,\dots,v_N

接下来 N1N-1 行,每行三个正整数 Ai,Bi,CiA_i,B_i,C_i,表示树上存在一条长度为 CiC_i 的边连接节点 Ai,BiA_i,B_i

输出格式

一个数,表示方案数第 1192092895507812511920928955078125 取模的结果。

样例

样例输入

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}\{1,2,5\},\{1,4\},\{2,6\}

从中选出 KK 个且能完成测试的方案为选择 {1,2,5},{1,4}\{1,2,5\},\{1,4\} 或选择 {1,2,5},{2,6}\{1,2,5\},\{2,6\}

数据范围与提示

子任务编号 NN\leq MM\leq KK\leq 特殊性质 分值
11 1717 150150 10910^9 1313
22 6060 1000010000 11 1111
33 6060 22 10410^4 w1==wN=1w_1=\dots=w_N=1 1919
44 4040 12001200 10910^9 2020
55 6060 1000010000 10410^4 1515
66 6060 1000010000 10910^9 2222

对于 100%100\% 的数据,N60,M10000,Ci10000,K,wi,vi109,Max1018N\leq 60,M\leq 10000,C_i\leq 10000,K,w_i,v_i\leq 10^9,Max\leq 10^{18}