P9248 [CTT Mock Test 2018] Perfect Set

Little A has a weighted tree with $N$ nodes. Each node has a weight $w_i$ and a value $v_i$. Now Little A wants to select some nodes to form a set $S$, such that the total weight of these nodes is $\leq M$ and they form a connected component. Little A is a perfectionist, so he will only choose those $S$ with the maximum possible total value among all sets that satisfy the conditions. We call such a set $S$ a perfect set. Now Little A wants to choose $K$ sets from all perfect sets, and test these $K$ perfect sets separately. Before these $K$ tests begin, Little A first needs a node $x$ to place his testing device, whose maximum power is $Max$. In each subsequent test, Little A will transmit energy once to all nodes in the test object $S$. The power required to transmit energy to a node $y$ is $dist(x,y)\times v_y$, where $dist(x,y)$ denotes the length of the shortest path between nodes $x$ and $y$ on the tree. Therefore, if there exists a node $y$ in $S$ such that $dist(x,y)\times v_y>Max$, the test will fail. At the same time, in order to ensure stable energy transmission, the node $x$ where the device is placed must be in the set $S$, otherwise the test will also fail. Now Little A wants to know: how many ways are there to choose $K$ sets from all perfect sets, such that he can find a node to place the testing device and complete his tests? You only need to output the number of ways modulo $11920928955078125$.

The first line contains four positive integers, denoting $N,M,K,Max$. The next line contains $N$ positive integers, denoting $w_1,\dots,w_N$. The next line contains $N$ **non-negative** integers, denoting $v_1,\dots,v_N$. The next $N-1$ lines each contain three positive integers $A_i,B_i,C_i$, meaning there is an edge of length $C_i$ connecting nodes $A_i,B_i$ in the tree.

One number, denoting the number of ways modulo $11920928955078125$.

### Sample Explanation The perfect sets are $\{1,2,5\},\{1,4\},\{2,6\}$. The ways to choose $K$ sets from them and still complete the tests are: choosing $\{1,2,5\},\{1,4\}$, or choosing $\{1,2,5\},\{2,6\}$. ### Constraints | Subtask ID | $N\leq$ | $M\leq$ | $K\leq$ | Special Property | Score | |:----------------:|:----------------:|:----------------:|:----------------:|:-----------------------------------:|:----------------:| | $1$ | $17$ | $150$ | $10^9$ | | $13$ | | $2$ | $60$ | $10000$ | $1$ | | $11$ | | $3$ | $60$ | $2$ | $10^4$ | $w_1=\dots=w_N=1$ | $19$ | | $4$ | $40$ | $1200$ | $10^9$ | | $20$ | | $5$ | $60$ | $10000$ | $10^4$ | | $15$ | | $6$ | $60$ | $10000$ | $10^9$ | | $22$ | For $100\%$ of the testdata: $N\leq 60$, $M\leq 10000$, $C_i\leq 10000$, $K,w_i,v_i\leq 10^9$, and $Max\leq 10^{18}$. Translated by ChatGPT 5