Join the Joint

题号：NC295137
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Recently, Eva learned several advanced data structure techniques for trees. To show her progress, she asked Colin to give her a challenging problem about tree statistics.

However, Colin just gave her a very typical problem:

Given a tree with $n$ vertices, and the vertex $1$ is the root. Each vertex has an integer weight $w_i$ .
Let $lca(u,v)$ represent the lowest common ancestor of the vertex $u$ and $v$ .
Given two integer sequences $a_1,a_2,\cdots,a_x~(1\le a_i\le n)$ and $b_1,b_2,\cdots,b_y~(1\le b_i\le n)$ .
Define the joint power of these two sequences to be
$\sum_{i=1}^x\sum_{j=1}^yw_{lca(a_i,b_j)}$
Please calculate the value of this joint power.

Eva thinks this problem is too easy, so she decided to change the problem into an online problem:
First, given the tree and the weight of each vertex. Initially, both sequences are empty.
Then there will be $m$ operations, each one is of the following two types:

1 u : append $u~(1\le u\le n)$ to the end of the first sequence.
2 u : append $u~(1\le u\le n)$ to the end of the second sequence.

After each operation, you need to output the current joint power of the two sequences.

However, this version of the problem is too hard for Eva, so she added an additional limitation that, after each operation, the sum of values in the first sequence will not exceed $10^6$ .

Now Eva turns this problem to you, do you know how to solve it?

输入描述:

The first line contains two integers , representing the number of vertices in the tree, and the number of operations.

The second line contains  integers , representing the weight of each vertex.

For the following  lines, each line contains two integers , representing that there is an edge connecting  and  in the tree. It's guaranteed that all the edges in the input forms a tree.

For the following  lines, each line contains two integers , representing an operation. It's guaranteed that after each operation, the sum of values in the first sequence will not exceed .

输出描述:

For each operation, output a single line with a single integer, representing the joint power of the two sequences after processing the corresponding operation.

示例1

输入

复制

输出

复制

示例2

输入

复制

10 6
1 2 10 5 5 6 5 6 2 2
1 2
2 3
1 4
4 5
2 6
3 7
6 8
2 9
6 10
2 10
1 7
2 5
1 9
1 5
2 6

输出

复制