ZYB's kingdom

"Dad, our city and the neighboring city haven't got any income for years. What's happening?"
"Well, son, there's an ongoing pandemic in the neighboring city, you know..."
"Fine. And what about our city?"
"I really wish to knock his head off when the king decided to build this country like a tree and made our city a leaf!"

There are $n$ cities in ZYB's kingdom, and it's connected by $n-1$ bidirectional roads between the cities. Initially, the $i$th city has a prosperity index equal to $c_i$, when a trade happens between two cities $u$ and $v$, the income of city $u$ increases by $c_v$, and the income of city $v$ increases by $c_u$. (Strange definition, isn't it?)

Every once in a while, ZYB will hold a trading festival to boost the economy in his kingdom(and to get more taxes, of course!). However, some cities must be shut down and not allowed to pass during the festival due to the pandemic. Formally, when a trading festival is held, a list of $k$ cities $a_1,a_2,\dots,a_k$ that are shut down are informed, and for any pair of cities $(u,v)(u<v)$, if the unique path between them doesn't contain any of the $k$ cities, then a trade happens between them, i.e., the income of city $u$ increases by $c_v$, and the income of city $v$ increases by $c_u$.

Initially, the income of every city in ZYB's kingdom is zero. Then $q$ events happen, each in one of the following forms:

• Let's hold a trading festival! A list of $k$ cities $a_1,a_2,\dots,a_k$ are given, then for any pair of cities $(u,v)(u<v)$, if the unique path between them doesn't contain any of the $k$ cities, then a trade happens between them.


• Find the current total income of some city $v$.

It is guaranteed that $\sum n \leq 10^6, \sum q \leq 10^6$ and $\sum k \leq 10^6$ over all test cases.

The first line contains a number $T(1\leq T\leq 20)$, denoting the number of test cases.

The first line of each test case contains two integers $n,q(1\leq n,q\leq 2\cdot 10^5)$, denoting the number of cities in zyb's kingdom and the number of events, respectively.

Then $n-1$ lines follow. Each line contains two integers $u,v$, denoting an edge between city $u$ and city $v$.

Then one line containing $n$ integers $c_1,c_2,\dots,c_n(1\leq c_i\leq 10^6)$ follows, denoting the prosperity index of each city.

Then $q$ lines follow, each line describing an event in one of the following forms:

• $1\,\, k(1\leq k\leq n), a_1,a_2,...,a_k(\forall 1\leq i\leq k,1\leq a_i\leq n$ and all $a_i$ are distinct), denoting an event of the first type.


• $2\,\, v(1\leq v\leq n)$, denoting an event of the second type that asks about the current income of city $v$.

For each event of type $2$, output a number in one line denoting the answer.

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

1
2
3

2021“MINIEYE杯”中国大学生算法设计超级联赛（9）