U413065 集合 subtask 01 & 02

**时间限制：** 4.0 秒 **空间限制：** ~~1024 MB~~ 512 MB 由于洛谷个人用户无法设置 512 MB 以上的空间限制，故本题空间限制设置在 512 MB 。可以确定的是满分做法的空间占用**远达不到** 512 MB 。 如果你的部分分正确做法**仅因为**超过 512 MB 且在 1024 MB 以内而获得 `Memory Limit Exceeded` 的反馈信息，请优化你的空间常数。（例 : 树上倍增算法在本题的数据范围上限下可以优化到 400 MB~450 MB 左右。此算法并不一定是可以拿到部分分的解法，仅用来举例。） **该提交为本题的 subtask 01 & 02 部分，满分为 $8$ 分。各子任务的限制具体见最下方。各 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) 注 : subtask 01 & 02 部分为了使用尽可能多的数据进行准确性评测，该评测的时限将由 4 秒改为 1 秒。

给定一棵 $n$ 个点的有根树 $T$，树的节点从 $1$ 到 $n$ 标号，$1$ 为根。每个点有两个整数值 $a_i,b_i$ 。 称一个点集 $S$ 是好的当且仅当其满足以下条件： $\forall\text{ } u, v\in S~(u\ne v)$ 满足 $u$ 是 $v$ 的祖先，$\exist\text{ } 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$ 。

无

无

### 样例 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$ 。 子任务 1（3 分）：$n,q\le 5$ 。 子任务 2（5 分）：$n,q\le 10$ 。 子任务 3（5 分）：$n,q\le 300$ 。 子任务 4（9 分）：$n,q\le 3000$ 。 子任务 5（13 分）：$n\le 3000,q\le 3\times 10^5$ 。 子任务 6（14 分）：$n\le 7\times 10^4,q\le 200;\text{ }\forall\text{ } 1\le i\le n-1,$ $i$ 和 $i+1$ 有一条边。 子任务 7（7 分）：$n\le 7\times 10^4,q\le 3\times 10^5;\text{ }\forall\text{ } 1\le i\le n-1,$ $i$ 和 $i+1$ 有一条边。 子任务 8（6 分）：$n,q\le 3\times 10^5;\text{ }\forall\text{ } 1\le i\le n-1,$ $i$ 和 $i+1$ 有一条边。 子任务 9（15 分）：$n\le 7\times 10^4,q\le 200$ 。 子任务 10（13 分）：$n\le 7\times 10^4,q\le 3\times 10^5$ 。 子任务 11（10 分）：无额外限制。