Candyland Happiness

Candyland has a unique park with n attractions (numbered from 1 to n) connected by n − 1 bidirectional roads, forming a tree structure. At each attraction, a specific type of candy (from 1 to m) is handed out. The candy at attraction i is of type C_i.

There are a total of m candy types. The tastiness (or "美味") index of candy type j is given by V_j. In addition, when a visitor tastes the same candy type repeatedly, its novelty decreases. In particular, the i-th time a visitor tastes a candy of a given type, the novelty index is W_i. Thus, when a visitor tastes candy type j for the i-th time (on that route), the happiness increases by

[ V_j \times W_i ]

The total happiness for a visitor is the sum of these products over the candies encountered along the path.

The park’s structure is fixed (i.e. the roads do not change) but the candy types at attractions can be updated.

You are given the initial candy types at all attractions and the tree structure of the park. Then, you are given q operations. Each operation is one of the following two types:

• Query: Given two attractions u and v, a visitor travels from u to v along the unique simple path. For each candy type encountered along the path, suppose it is tasted r times. Then its contribution is
  \( V_j \times \Big(\sum_{i=1}^{r}W_i\Big) \). The visitor's total happiness is the sum of such contributions over all candy types encountered. Output the total happiness.
• Update: Given an attraction u and a candy type x (1 ≤ x ≤ m), update the candy type at attraction u to x.

Input Format:

• The first line contains three integers n, m and q, representing the number of attractions, the number of candy types, and the number of operations, respectively.
• The second line contains n integers: C₁, C₂, ..., C_n, where C_i denotes the candy type at attraction i.
• The third line contains m integers: V₁, V₂, ..., V_m, the tastiness indices for each candy type.
• The fourth line contains n integers: W₁, W₂, ..., W_n, representing the novelty indices. (Note: For any candy type, if it is tasted r times, its total novelty is \(\sum_{i=1}^{r}W_i\).)
• Each of the next n − 1 lines contains two integers u and v, indicating that there is a road connecting attractions u and v.
• Each of the next q lines describes an operation in one of the following formats:
  • 1 u v — Query: Compute the happiness for the visitor who travels from u to v.
  • 2 u x — Update: Change the candy type at attraction u to x.

Output Format:

For each query operation (operations of the first type), output a single line containing the total happiness.

Note: All formulae are given in LaTeX format.

inputFormat

The input begins with three integers n m q. The next line contains n integers specifying the initial candy types at the n attractions. The following line contains m integers representing the tastiness indices V1, V2, ..., Vm. The next line contains n integers representing the novelty indices W1, W2, ..., Wn. After that, there are n-1 lines each with two integers denoting roads between attractions. Finally, there are q lines of operations. For a query, the line is in the format 1 u v; for an update, it is 2 u x.

outputFormat

For each query operation, output one line with the total happiness obtained along the unique path from u to v as defined by the formula \(\sum_{\text{candy type } j}\Big(V_j\times\sum_{i=1}^{r_j}W_i\Big)\), where \(r_j\) is the number of times candy type j appears on the path.

sample

3 2 1
1 2 1
5 10
1 2 3
1 2
2 3
1 1 3

25

</p>