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.