Occupation

Miceren finds a huge country named HY. HY has $N$ cities numbered from 1 to $N$ connected by $N~-~1$ bidirectional roads. There exists a path between any two cities.

It can be imagined as a tree with $n$ vertices rooted at vertex 1.

Miceren wants to occupy some cities here. Each city has a value $v_i$. (Notice that the value of a city may be negative. Nevertheless, Miceren wants to occupied this city.)

As some usual stories, someone named Cloud wants to "steal" some cities from Miceren.

At the beginning, Miceren and Cloud don't occupy any city.

In the following $Q$ days, one of three events may happen

1. Miceren will walk from the a-th city to the b-th city and all cities visited in this trip will belong to Miceren. ($1~\le~a, b~\le~N$)

2. Cloud will steal the x-th city. If Miceren occupied the x-th city before, Miceren will lost the control of this city. ($1~\le~x~\le~N$)

3. Miceren will occupy the subtree rooted at x.($1~\le~x~\le~N$)

As Miceren's friend, you must tell Miceren the total value of all cities which belong to Miceren after each day.

The first line contains a single integer $T$, indicating the number of test cases.

Each test case begin with one integer $N$, indicating the number of cities in HY.

The next line contains $N$ integer $V_i$, indicating the value of each city.

The next $N~-~1$ lines contain the details of the roads. Each line contains two integers $u,~v$ meaning that there is a road between cities $u$ and $v$.

The next line contains one integer $Q$.

The next $Q$ lines contain the details of event. If the format is "1 a b", it means the first event happened where Miceren walks from a-th city to b-th city. If the format is “2 x”, it means the second event happened where Cloud "steal"s the x-th city. Otherwise the format is “3 x” and the third event happened where Micron occupied the subtree rooted at x.

$T$ is about 100.

$1~\le~N, Q~\le~100000.$

$-1000~\le~V_i~\le~1000.$

The ratio of test cases with $N~\gt~100$ is less than 5%.

For each test queries, print the answer.

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

21
41
36
36
32
43

If you need a larger stack size,
please use #pragma comment(linker, "/STACK:102400000,102400000") and submit your solution using C++.

赛码"BestCoder"杯中国大学生程序设计冠军赛