Description

Shizhou City consists of $N$ islands, connected by $N-1$ space channels for transmitting information.

As the Star Tower Keeper of Shizhou City, Yue Lingxue can deploy Star Towers. Specifically, in order to transmit messages to every island where residents live by relying on special spatial fluctuations, Yue Lingxue may deploy any number of Star Towers. Each island can have at most one Star Tower. However, at the same time, all deployed Star Towers must be connected into a single chain through space channels.

Shizhou City is troubled by spatial storms all year round. Often, an island will be hit by a spatial storm and all residents on it are forced to leave. At this time, the Star Towers no longer need to transmit messages to that place. After the spatial storm dissipates and residents return, the Star Towers need to resume transmitting information to that place.

Due to interference from spatial fluctuations, Star Towers must rely on space channels connecting islands to transmit messages. Specifically, if a Star Tower needs to transmit a message to an island, the energy cost equals the sum of energy costs of all space channels along the path from the island where the Star Tower is located to the destination island. Of course, if a Star Tower sends a message to the island it is on, no energy is needed. The signal fluctuations of Star Towers transmitting messages to islands are independent of each other, that is, for each Star Tower and each island, the energy transmission does not interfere with others.

As both the city lord and the Star Tower Keeper, Yue Lingxue has recently been studying how to deploy Star Towers to minimize the energy consumed for message transmission. She has found records of spatial storm outbreaks over the past seven thousand years and the Star Tower deployment data at those times. Since the history is too old, the energy consumption of each time is no longer known. Now Yue Lingxue hopes you can help her reconstruct these historical materials. See the input format for details.

Input Format

The first line contains three integers $N,Q,Type$, representing the number of islands in Shizhou City, the number of queries by Yue Lingxue, and the special properties of this test point. In binary, if the $(i-1)$-th bit of $Type$ is $1$, then special property $i$ exists.

The next $N-1$ lines each contain three integers $u_{i},v_{i},w_{i}$, indicating that there is a bidirectional space channel between islands $u_i$ and $v_i$, and the energy cost for a message to pass through this channel is $w_i$.

The next line contains $N$ numbers, consisting only of $0$ and $1$, indicating whether there is a spatial storm on the $i$-th island at the time the city was founded. $0$ means there is a spatial storm, and $1$ means there is no spatial storm. We also assume that if an island has no spatial storm, then it will definitely attract people to live there; if it has a spatial storm, then nobody lives on that island.

The last $Q$ lines each describe an event, as follows:

$1$ $x$: For island $x$, if there was originally no spatial storm on this island, then a spatial storm occurs and all residents evacuate the island; otherwise, it means the spatial storm on this island dissipates and people return to live here.

$2$ $x$ $y$: Yue Lingxue asks you a query: if Star Towers are deployed on the simple path from $x$ to $y$ at this moment, what is the minimum possible total energy consumption required to transmit one message to all islands with residents. A Star Tower can transmit messages to multiple islands at the same time, and it may also transmit to no island.

Output Format

Output $Q$ lines, each containing one number, representing the answer to that query.

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

7
12

6 3 0
2 1 3
3 1 5
4 1 2
6 4 8
4 5 9
1 1 1 0 0 1
2 1 1
1 5
2 3 6

18
12

Hint

Special property $1$: $v_{i}=u_{i}+1$.

Special property $2$: In all of Yue Lingxue’s queries, $x$ and $y$ are the same.

Special property $3$: In all of Yue Lingxue’s queries, $x=1$.

For all $w_{i}$, it is guaranteed that $0 \leq w_{i}\leq 10^{5}$.

For $100\%$ of the data, it is guaranteed that $N,Q\leq 200000,0\leq Type\leq 7$.

Sample 1 explanation:

The initial graph is shown on the left.

For the first query, as shown in the middle, islands $2,3,5$ have residents, so $ans_2=ans_3=0,ans_5=7$, hence $ans=7$.

For the second query, as shown on the right, $ans_2=2+3=5,ans_3=0,ans_5=7$, hence $ans=7+5=12$.

Sample 2 explanation:

The initial graph is shown at the upper left.

For query $1$, as shown at the upper right, islands $1,2,3,6$ have residents. $ans_1=0,ans_2=3,ans_3=5,ans_6=8+2=10$, hence $ans=3+5+10=18$.

After one operation 1, all islands with residents are shown at the lower left.

The subsequent operations are shown at the lower right. Similarly, $ans_1=0,ans_2=3,ans_3=0,ans_5=9,ans_6=0$, so $ans=3+9=12$.

Input Format

Output Format

Translated by ChatGPT 5