Maximizing Weighted Path with Color Constraint

Problem Statement:

Given a tree with \(n\) nodes. Each node is colored either black or white and has two attributes \(a\) and \(b\). You are given multiple queries. For each query, given an integer parameter \(k\), find a path \((u,v)\) in the tree such that the colors of \(u\) and \(v\) are different and the following value is maximized:

\[ k \times \sum_{p \in path(u,v)} p.a + \sum_{p \in path(u,v)} p.b \]

The summations denote the sum of the \(a\) and \(b\) values for all nodes on the unique path between \(u\) and \(v\) (inclusive). Note that \(a\), \(b\), and \(k\) can be positive or negative. You are not allowed to choose an empty path. Therefore, if all valid paths have negative values, the answer can be negative.

inputFormat

Input Format:

• The first line contains two integers \(n\) and \(q\) representing the number of nodes in the tree and the number of queries.
• The next \(n-1\) lines each contain two integers \(u\) and \(v\), representing an edge between nodes \(u\) and \(v\). The nodes are numbered from 1 to \(n\).
• The next line contains \(n\) space-separated characters, each being either B (black) or W (white), representing the color of each node (from node 1 to \(n\)).
• The following line contains \(n\) integers, where the \(i\)th integer is the attribute \(a\) of node \(i\).
• The next line contains \(n\) integers, where the \(i\)th integer is the attribute \(b\) of node \(i\).
• The next \(q\) lines each contain a single integer \(k\), representing a query.

outputFormat

Output Format:

For each query, output a single line containing the maximum value of \( k \times \sum_{p \in path(u,v)} p.a + \sum_{p \in path(u,v)} p.b \) over all valid paths \((u,v)\) whose endpoints have different colors.

sample

4 3
1 2
2 3
2 4
B W B W
1 -2 3 4
2 5 -1 0
1
-1
2

10
8
14

</p>