P17417 [MX-X31-T7] "FAOI-R14" Hello & Bye, Days (Enhanced Version).

>on this lonely day > >Cheers for the farewell against the light. > >Maybe I am just a puppet. > >Forced to cry before an inevitable ending. >

**The original problem is [P17411](https://www.luogu.com.cn/problem/P17411), but it was passed by some solutions that were not intended to pass, so extra constraints were added to make the memory and time limits stricter.** You are given a tree with $n$ nodes. You need to maintain a set of key nodes $S$, which is empty at the beginning. Let $\mathrm{dis}(x,y)$ be the distance between $x$ and $y$ on the tree, and define $d(x)=\min\limits_{y\in S}\mathrm{dis}(x,y)$. **Each node $i$ also has a positive integer weight $w_i$.** Then there are $q$ operations. The $i$-th operation is of one of the following two types: - `1 x`: If $x$ is in $S$, delete $x$ from $S$; otherwise, add $x$ into $S$. - `2 x`: Output $\sum\limits_{i=1}^n[d(i)=\mathrm{dis}(x,i)]w_i$. It is guaranteed that $x\in S$ here. That is, count how many nodes $i$ satisfy that $x$ is one of the closest key nodes to $i$. Some test points require you to answer queries online.

The first line contains three integers $n,q,t$, representing the number of nodes, the number of operations, and a parameter related to forced online queries. Next $n-1$ lines each contain a pair of integers $x_i,y_i$, representing an edge. The next line contains $n$ integers $w_1\cdots w_n$, representing the weight of each node. Next $q$ lines each contain two integers $op\space z$, where $op$ is the operation type, and $z$ is the information before decryption. Let $$ x=z\mathbin{\operatorname{xor}}\mathrm{(lastans\times t)}, $$ then $x$ is the real node index for this operation, where $\mathrm{lastans}$ is the answer to the previous query, initially $0$. It is guaranteed that: - After decryption, $1\le x\le n$. - For operation `2`, after decryption $x\in S$. - After each operation is executed, the set $S$ is non-empty. The encrypted node index $z$ in the input may be $0$.

Output several lines, each line is the answer to one query.

### Sample Explanation The tree is a chain: $$ 1-2-3-4-5 $$ * After adding key node $1$, $S=\{1\}$. The closest key node of every node is $1$, so the first query outputs $5$. * After adding key node $5$, $S=\{1,5\}$: * For key node $1$, the nodes that satisfy the condition are $1,2,3$. * For key node $5$, the nodes that satisfy the condition are $3,4,5$. Node $3$ has distance $2$ to both key nodes, so it will be counted in both queries. * Finally, delete key node $1$. Now $S=\{5\}$. The closest key node of every node is $5$, so the output is $5$. ### Constraints This problem has subtasks. - For $10\%$ of the testdata, $n,q\leq 3000$. - For $40\%$ of the testdata, $n,q\leq 5\times 10^4$. - For another $10\%$ of the testdata, the tree is a chain. - For another $20\%$ of the testdata, $t=0$. - For $100\%$ of the testdata, $1\leq n,q\leq 2\times 10^5$, $1\leq x_i,y_i\leq n$, $t\in \{0,1\}$, $op\in \{1,2\}$, $0\leq z