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