Background

Cdm1020 really likes games made by August-soft. While playing August’s past works, he suddenly discovered some amazing facts.

That is, all character portraits have the same face!

Even so, as an experienced “August fan”, he can still sharply tell the tiny differences between portraits (no, it’s the same face, what is there to tell). To further study August’s portrait quality, Cdm1020 put all of August’s portraits onto a tree (what on earth).

(If you do not know what a tree is, you can think of it as an undirected connected graph with no cycles.)

More specifically, each node on the tree stores exactly one portrait from August. After talking with his fellow fans, Cdm1020 found that fans with different “enthusiasm levels” like the same portrait differently. Each portrait has two attributes $a$ and $b$. For a fan whose enthusiasm index is $k$, their liking for a portrait with attributes $(a,b)$ is $ka+b$.

Now Cdm1020 wants to lead his $m$ friends (with different enthusiasm indices) to visit the portraits. For each friend, he wants you to plan a visiting route with the maximum total liking.

Of course, this problem is too easy, so he would not bother you with it. What really troubles him is that August has a new artist, Xiano (Xià Yě). His friends are now making noise and want to see August’s new portraits (it is still the same face anyway, what is there to see), so he requires that your route must start from a portrait by Uncle B and end at a portrait by Xiano. Can you help him?

Problem Description

Please ignore the nonsense above and pretend you did not see anything.

In one sentence: you are given a tree with $n$ nodes. Each node is either black or white, and each node has two attributes $a$ and $b$.

Now there are multiple queries. Each query gives only one parameter $k$. You need to find a path $(u,v)$ in the tree such that $u$ and $v$ have different colors, and

$$k\times \sum_{p \in path (u-v)}p.a+\sum_{p\in path(u-v)}p.b$$

is maximized. For each query, you only need to output this maximum value (the two summations mean the sum of attribute $a$ on the path and the sum of attribute $b$ on the path, respectively).

Tips: $a$, $b$, and $k$ can all be positive or negative, and you are not allowed to choose no path. That is, the maximum value we find may be negative. This happens when the weights of all valid paths are negative.

Input Format

The first line contains two positive integers $n,m$, representing the number of nodes in the tree and the number of queries.

The next line contains $n$ integers. The $i$-th integer is the value of attribute $a$ of node $i$.

The next line contains $n$ integers. The $i$-th integer is the value of attribute $b$ of node $i$.

The next line contains $n$ integers, each being either $0$ or $1$. If the $i$-th number is $0$, then node $i$ is a white node; if it is $1$, then node $i$ is a black node.

The next $n-1$ lines each contain two positive integers $u,v$, indicating that there is an edge between node $u$ and node $v$.

The next $m$ lines each contain one integer $k$, the parameter of the query.

Output Format

Output $m$ lines. For each query, output the maximum value of the expression given in the statement.

15 15
29 -23 -14 -50 -13 -23 5 33 50 32 27 27 -9 -42 -11
-37 39 21 50 10 -42 -2 25 1 28 40 -45 -24 -29 47
0 0 1 0 0 1 1 0 0 1 0 1 0 0 0
2 1
3 1
4 3
5 2
6 2
7 2
8 4
9 1
10 2
11 5
12 3
13 5
14 3
15 9
-8
36
44
29
-5
-4
-3
-2
-1
0
1
2
3
4
5

679
3252
3988
2608
436
355
274
199
135
126
155
232
309
386
471

Hint

Constraints: $2 \leq n\leq 10^5$, $1 \leq m \leq 10^5$, $-10^8 \leq k \leq 10^8$.

It is guaranteed that there will not be testdata where all nodes are black or all nodes are white. It is guaranteed that for any path in the tree, the absolute value of the sum of attribute $a$ on the path does not exceed $1.5×10^9$, and the absolute value of the sum of attribute $b$ on the path does not exceed $1.5×10^9$.

Translated by ChatGPT 5