QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100

# 4781. 完美的集合

统计

小 A 有一棵 $N$ 个点的带边权的树,树的每个节点有重量 $w_i$ 和价值 $v_i$。

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

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

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

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

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

输入格式

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

接下来一行 $N$ 个正整数,表示 $w_1,\dots,w_N$。

接下来一行 $N$ 个非负整数,表示 $v_1,\dots,v_N$。

接下来 $N-1$ 行,每行三个正整数 $A_i,B_i,C_i$,表示树上存在一条长度为 $C_i$ 的边连接节点 $A_i,B_i$。

输出格式

一个数,表示方案数第 $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\leq$ $M\leq$ $K\leq$ 特殊性质 分值
$1$ $17$ $150$ $10^9$ $13$
$2$ $60$ $10000$ $1$ $11$
$3$ $2$ $10^4$ $w_1=\dots=w_N=1$ $19$
$4$ $40$ $1200$ $10^9$ $20$
$5$ $60$ $10000$ $10^4$ $15$
$6$ $10^9$ $22$

对于 $100\%$ 的数据,$N\leq 60,M\leq 10000,C_i\leq 10000,K,w_i,v_i\leq 10^9,Max\leq 10^{18}$。