U414939 集合 子任务 11

**时间限制：** 4.0 秒 **空间限制：** ~~1024 MB~~ 512 MB 由于洛谷个人用户无法设置 512 MB 以上的空间限制，故本题空间限制设置在 512 MB。可以确定的是满分做法的空间占用**远达不到** 512 MB。 如果你的部分分正确做法**仅因为**超过 512 MB 且在 1024 MB 以内而获得 `Memory Limit Exceeded` 的反馈信息，请优化你的空间常数。（例 : 树上倍增算法在本题的数据范围上限下可以优化到 400 MB~450 MB 左右。此算法并不一定是可以拿到部分分的解法，仅用来举例。） **该提交为本题的 subtask 11 部分，满分为 $10$ 分。各子任务的限制具体见最下方。各 subtask 评测链接如下，请各位自行计算总分数。** - [subtask 01 & 02 提交链接](https://www.luogu.com.cn/problem/U413065) - [subtask 03 & 04 提交链接](https://www.luogu.com.cn/problem/U414735) - [subtask 05 提交链接](https://www.luogu.com.cn/problem/U414737) - [subtask 06 提交链接](https://www.luogu.com.cn/problem/U414738) - [subtask 07 提交链接](https://www.luogu.com.cn/problem/U414739) - [subtask 08 提交链接](https://www.luogu.com.cn/problem/U414740) - [subtask 09 提交链接](https://www.luogu.com.cn/problem/U414741) - [subtask 10 提交链接](https://www.luogu.com.cn/problem/U414938) - [subtask 11 提交链接](https://www.luogu.com.cn/problem/U414939)

给定一棵 $n$ 个点的有根树 $T$，树的节点从 $1$ 到 $n$ 标号，$1$ 为根。每个点有两个整数值 $a_i,b_i$。 称一个点集 $S$ 是好的当且仅当其满足以下条件： $\forall~ u, v\in S~(u\ne v)$ 满足 $u$ 是 $v$ 的祖先，$\exist~ x\not\in S,y\in S$，使得： - $x$ 在 $u$ 到 $v$ 的路径上； - $b_y \le b_x$。 给出 $q$ 组询问，每组询问给出正整数 $c,d$，找到一个好的点集 $S$，最大化 $c\times (\sum\limits_{u\in S}a_u)+d\times (\min\limits_{u\in S}b_u)$。你只需要给出这个最大值。当 $S$ 为空时，认为 $\min\limits_{u\in S} b_u=0$。

从标准输入读入数据。 第一行两个整数 $n,q$，描述树的节点数和询问次数。 接下来 $n-1$ 行，每行两个整数 $u,v$，描述树的一条边。 接下来 $n$ 行，第 $i$ 行两个整数 $a_i,b_i$，描述节点 $i$ 的权值。 接下来 $q$ 行，每行两个整数 $c,d$，描述一组询问。

输出到标准输出。 对于每组询问输出一行一个整数表示答案。

### 样例 1 解释 四组询问选择的集合依次是 $\emptyset,\{2\},\{1\},\{3\}$。 ### 子任务 对于所有测试数据： - $1\le n,q\le 3\times 10^5$； - $1\le u\ne v\le n$, 保证给出的 $n-1$ 条边构成一棵树； - $-10^4\le a_i\le 10^4,-10^9\le b_i\le 10^9$； - $1\le c,d\le 10^8$。 **本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。** | 子任务编号 | 分值 | $n\le$ | $q\le$ | 特殊性质 | | :----: | :-----: | :-----: | :------: | :----: | | 1 | 3 | $5$ | $5$ | $\times$ | | 2 | 5 | $10$ | $10$ | $\times$ | | 3 | 5 | $300$ | $300$ | $\times$ | | 4 | 9 | $3000$ | $3000$ | $\times$ | | 5 | 13 | $3000$ | $3\times 10^5$ | $\times$ | | 6 | 14 | $7\times 10^4$ | $200$ | $\checkmark$ | | 7 | 7 | $7\times 10^4$ | $3\times 10^5$ | $\checkmark$ | | 8 | 6 | $3\times 10^5$ | $3\times 10^5$ | $\checkmark$ | | 9 | 15 | $7\times 10^4$ | $200$ | $\times$ | | 10 | 13 | $7\times 10^4$ | $3\times 10^5$ | $\times$ | | 11 | 10 | $3\times 10^5$ | $3\times 10^5$ | $\times$ | 特殊性质：$\forall~ 1\le i\le n-1$，$i$ 和 $i+1$ 有一条边。