405980: GYM102201 H 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.

5 2
5 4 3 2 1
1 2 3 4 5
1000000000 2 4 5 2
1 2
1 3
2 4
2 5
4 0
4 2

2
7