P5559 Star Tower Keeper of Shizhou City

> When the moon lies low, the tides are born; when starlight dyes ten thousand isles, all is silent. That which has no change between darkness and light is called Shizhou. ———— *Notes of Shizhou City · Origin*. Shizhou City is surrounded by the sea on all sides and was founded 7325 years ago. In Shizhou City, there is no change between night and day. Since the founding of the city, a bright moon has been hanging in the sky, hence the name Shizhou. The lord of Shizhou City, Yue Lingxue, controls the Star Tower. In Shizhou City, which never has daytime, the Star Tower serves as a lighthouse for lighting and has always been a spiritual support for the people in the city. Her other identity is the Star Tower Keeper of Shizhou City. Compared with being the city lord, Yue Lingxue prefers guarding the Star Tower. The special environment of Shizhou City causes the space there to be extremely unstable. According to the city chronicles, during the more than seven-thousand-year history of Shizhou City, the total time of peace did not exceed three hundred years. During most of the remaining time, local areas of Shizhou City were covered by spatial storms. The Star Tower, which relies on special space to exist, also has the function of transmitting information to people. Under the influence of unstable space, this is the only way to keep signals stable.

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.

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 $Q$ lines, each containing one number, representing the answer to that query.

|Test Point ID|$N \leq$|$Q \leq$|Number of operation 1|Special Constraint 1|Special Constraint 2|Special Constraint 3| |:---:|:------:|:------:|:-----:|:----:|:----:|:----:| |1 |$200$ |$200$ |$\leq Q$|$0$ |$1$ |$0$ | |2 |^ |^ |^ |^ |^ |^ | |3 |^ |^ |$0$ |^ |$0$ |^ | |4 |^ |^ |^ |^ |^ |$1$ | |5 |$2000$ |$2000$ |^ |^ |^ |^ | |6 |^ |^ |^ |$1$ |^ |^ | |7 |^ |^ |$100$ |^ |$1$ |^ | |8 |^ |^ |^ |^ |^ |^ | |9 |$200000$|$200000$|^ |^ |^ |^ | |10 |^ |^ |^ |^ |^ |^ | |11 |^ |^ |^ |^ |$0$ |^ | |12 |^ |^ |^ |^ |^ |^ | |13 |^ |^ |^ |$0$ |^ |^ | |14 |^ |^ |^ |^ |^ |^ | |15 |^ |^ |$\leq Q$|^ |^ |^ | |16 |^ |^ |^ |^ |^ |^ | |17 |^ |^ |^ |^ |^ |$0$ | |18 |^ |^ |^ |^ |^ |^ | |19 |^ |^ |^ |^ |^ |^ | |20 |^ |^ |^ |^ |^ |^ | 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