P12491 [集训队互测 2024] 串联

给定一棵树，每个点有两个权值 $a_i,b_i$。对于树上的一条简单路径，若这条路径上 $b$ 之和乘上 $a$ 的最小值大于等于一个常数 $V$，那么这条路径被称作一条好的路径。 即：对于一条简单路径，设 $p_1,p_2,\dots,p_k$ 为路径上的点。这条简单路径是好的，当且仅当 $\min_{i=1}^k a_{p_i} \times \sum_{i=1}^k b_{p_i}\ge V$。 求所有好的路径中，$\sum b$ 的最小值。

第一行两个整数 $n,V$。 接下来 $n$ 行每行两个整数 $a_i,b_i$。 接下来 $n−1$ 行每行两个整数 $x_i,y_i$，表示一条树边。

一行一个整数表示答案。

### 子任务 对于所有测试点均满足 $1\leq V\leq 10^{18},1\leq a_i,b_i\leq 10^9$。数据保证有解。 | Subtask | $n\leq$ | 特殊性质 | 分值 | | :-----: | :-----------: | :--------------------------: | :--: | | $1$ | $2\times10^3$ | $/$ | $15$ | | $2$ | $10^4$ | $/$ | $15$ | | $3$ | $2\times10^5$ | 存在一个点度数为 $n-1$ | $15$ | | $4$ | $2\times10^5$ | 第 $i$ 条边连接 $i$ 和 $i+1$ | $15$ | | $5$ | $5\times10^4$ | $/$ | $20$ | | $6$ | $2\times10^5$ | $/$ | $20$ |