时间限制： 4.0 秒

空间限制： 1024 MB

题目描述

给定一棵 $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$，描述一组询问。

输出格式

输出到标准输出。

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

3 4
1 2
1 3
1 -2
-2 1
-5 2
1 1
1 3
3 1
1 10

0
1
1
15

样例 1 解释

四组询问选择的集合依次是 $\varnothing,\{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$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

特殊性质：$\forall~ 1\le i\le n-1$，$i$ 和 $i+1$ 有一条边。