Background

on this lonely day

Cheers for the farewell against the light.

Maybe I am just a puppet.

Forced to cry before an inevitable ending.

Problem Description

The original problem is 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.

Input Format

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 Format

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

5 7 0
1 2
2 3
3 4
4 5
1 1 1 1 1
1 1
2 1
1 5
2 1
2 5
1 1
2 5

5
3
3
5

Hint

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<2^{30},1\leq w_i\leq 10^3$.

Translated by ChatGPT 5