17457번 - Hard To Explain 다국어

문제

You are given a tree with $N$ vertices and $N-1$ edges. Vertex 1 is the root of the tree. Every vertex is associated with three positive integers $A_i, B_i, C_i,ドル where $C_1 = 10^9$ and $B_{parent(x)} \le B_x$ for all $x \neq 1,ドル where $parent(x)$ is the parent node of $x$.

If you see a tree with numbers, you naturally want to ask some queries. For each query, you are given a vertex $V$ and number $T$. Then, you should find a minimum value of $A_i + B_i \times T,ドル for all vertex $i$ which lies in some shortest path between vertex 1ドル$ and $V,ドル and which satisfies $C_i \geq T$. Note that, if $T \le 10^9,ドル then there exists a minimum value.

입력

In the first line, two integers $N, Q$ are given. (1ドル \le N \le 80000, 1 \le Q \le 160000$).

In the next line, $N$ integers $A_1, A_2, \cdots, A_N$ are given. (1ドル \le A_i \le 10^9$)

In the next line, $N$ integers $B_1, B_2, \cdots, B_N$ are given. (1ドル \le B_i \le 10^9$)

In the next line, $N$ integers $C_1, C_2, \cdots, C_N$ are given. (1ドル \le C_i \le 10^9$)

In the next $N-1$ lines, two integers $X, Y$ denoting the endpoints of edges are given. (1ドル \le X, Y \le N$)

In the next $Q$ lines, two integers $V, T$ denoting the arguments of queries are given. (1ドル \le V \le N, 0 \le T \le 10^9$)

It is guaranteed that $C_1 = 10^9,ドル and $B_{parent(x)} \le B_x$ for all $x \neq 1,ドル when $parent(x)$ is the parent node of $x$.

출력

Print $Q$ lines. In each line, print a single integer which is the minimum value asked by the given query.

제한

힌트