Odd Color Frequency in Tree Components

You are given an array $A$ and a tree with $n$ nodes. Each node has a color represented by an integer from $1$ to $x$. There are $m$ queries. In each query, you keep only the nodes whose colors lie in the interval $[l, r]$. In the resulting forest, consider every maximal connected component. Let $t$ be the number of colors that appear an odd number of times in that component. The component contributes $A_{t}$ to the answer. The answer to the query is the sum of contributions of all connected components. Each query is independent.

Note: All formulas are in \(\LaTeX\) format. For example, the contribution of a connected component is defined as \(A_{t}\) where \(t\) is the number of colors with odd frequency.

inputFormat

The input is given as follows:

• The first line contains three integers \(n\), \(m\), and \(x\): the number of nodes, the number of queries, and the maximum color value.
• The second line contains \(x+1\) integers: \(A_{0}, A_{1}, \dots, A_{x}\).
• The third line contains \(n\) integers, where the \(i\)-th integer represents the color of node \(i\) (1-indexed).
• Each of the next \(n-1\) lines contains two integers \(u\) and \(v\), representing an edge between nodes \(u\) and \(v\) in the tree.
• The following \(m\) lines each contain two integers \(l\) and \(r\), representing a query.

outputFormat

For each query, output one integer representing the sum of contributions of all connected components in the subgraph induced by the nodes whose colors lie in the interval \([l, r]\). Each answer should be printed on a new line.

sample

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

2
1
3