P15949 Festivals in JOI Kingdom 3

JOI Kingdom consists of $N$ cities and $N-1$ highways. The cities are numbered $1$ through $N$, and the highways are numbered $1$ through $N-1$. It is possible to travel from any city to any other city by traversing a number of highways. Each city has a **popularity**, represented by a non-negative integer. The popularity of city $i$ ($1 \leq i \leq N$) is initially $C_i$. Each highway has a **travel time**, represented by a positive integer. Highway $j$ ($1 \leq j \leq N-1$) connects city $A_j$ and city $B_j$, and its travel time is initially $D_j$. Each city in JOI Kingdom has a cauldron. JOI Kingdom keeps its tradition that, in a festival, cities ignite their cauldrons, and these ignitions signal the departure of parades from those cities. City $u$ is **adjacent** to city $v$ if these two cities are directly connected by a highway. At the exact moment when a city ignites its cauldron, one parade will depart from this city for each of its adjacent cities, spending time equal to the travel time of the corresponding highway. To be precise, for two adjacent cities $v$ and $u$, the parade from city $v$ reaches city $u$ at time $t + d$, where $t$ is the time when the cauldron of city $v$ is ignited, and $d$ is the travel time of the highway connecting cities $v$ and $u$. Some cities ignite their cauldron the moment the festival starts, while other cities only do so after the festival heats up enough. Let the time $0$ be the start of the festival. For the city $i$ whose popularity is $c$, the time when city $i$ ignites its cauldron is determined as follows: - If $c = 0$, city $i$ ignites its cauldron at time $0$. - If $c \geq 1$, city $i$ ignites its cauldron at the time when the number of parades that have arrived from adjacent cities becomes at least $c$. If this never happens, city $i$ never ignites its cauldron. Mr. K will stay at JOI Kingdom. During his stay, JOI Kingdom will have $Q$ events related to its festival. These events are numbered $1$ through $Q$ from earliest to latest. Event $k$ ($1 \leq k \leq Q$) is one of the following $3$ types: - Type $1$: The popularity of city $V_k$ changes to $X_k$. - Type $2$: The travel time of highway $E_k$ changes to $X_k$. - Type $3$: Mr. K visits city $V_k$. Assuming a festival starts at this moment, you must determine whether city $V_k$ would ignite its cauldron, and if so, calculate the time that the cauldron is ignited. Write a program which, given the structure of JOI Kingdom, popularity of each city, travel time of each highway, and details of the events, for each Type $3$ event, determines when the city Mr. K visits ignites its cauldron.

Read the following data from the standard input. > $N$\ > $A_1 B_1 D_1$\ > $\vdots$\ > $A_{N-1} B_{N-1} D_{N-1}$\ > $C_1$\ > $\vdots$\ > $C_N$\ > $Q$\ > (Query $1$)\ > $\vdots$\ > (Query $Q$) (Query $k$) represents the details of event $k$ ($1 \leq k \leq Q$). In (Query $k$), space-separated integers are written. Let $P_k$ be the first integer. $P_k$ is $1$, $2$, or $3$, which means the type of event $k$. Then (Query $k$) means as follows: - If $P_k = 1$, there are two more integers $V_k, X_k$ written in this order. This means that the popularity of city $V_k$ changes to $X_k$. - If $P_k = 2$, there are two more integers $E_k, X_k$ written in this order. This means that the travel time of highway $E_k$ changes to $X_k$. - If $P_k = 3$, there is one more integer $V_k$ written. This means Mr. K visits city $V_k$ and, assuming a festival starts at this moment, you must determine the time that the cauldron at city $V_k$ is ignited.

To standard output, output the following in one line for each event $k$ ($1 \le k \le Q$) with $P_k = 3$, in the increasing order of $k$. - If the city Mr. K visits would ignite its cauldron, output the time that the cauldron is ignited. - Otherwise, output $\texttt{-1}$.

### Sample 1 In the festival considered in event $1$, the times when the cities ignite their cauldrons are as follows: - At time $0$, cities $3, 4, 5, 7$ ignite their cauldrons. - At time $50$, city $2$ ignites its cauldron. By then, the parades from cities $3, 5, 7$ have reached city $2$. - At time $80$, city $1$ ignites its cauldron. By then, the parades from cities $2, 4$ have reached city $1$. - At time $90$, city $6$ ignites its cauldron. By then, the parade from city $1$ has reached city $6$. Since city $1$ would ignite its cauldron at time $80$, output $80$. In the festival considered in event $3$, the times when the cities ignite their cauldrons are as follows: - At time $0$, cities $3, 4, 5, 6, 7$ ignite their cauldrons. - At time $50$, city $2$ ignites its cauldron. By then, the parades from cities $3, 5, 7$ have reached city $2$. - At time $70$, city $1$ ignites its cauldron. By then, the parades from cities $4, 6$ have reached city $1$. Since city $1$ would ignite its cauldron at time $70$, output $70$. In the festival considered in event $5$, the times when the cities ignite their cauldrons are as follows: - At time $0$, cities $3, 4, 5, 6, 7$ ignite their cauldrons. - At time $30$, city $2$ ignites its cauldron. By then, the parades from cities $3, 5, 7$ have reached city $2$. - At time $60$, city $1$ ignites its cauldron. By then, the parades from cities $2, 6$ have reached city $1$. Since city $1$ would ignite its cauldron at time $60$, output $60$. In the festival considered in event $8$, the times when the cities ignite their cauldrons are as follows: - At time $0$, cities $3, 4, 5, 7$ ignite their cauldrons. Cities $1, 2, 6$ would never ignite their cauldrons. Since city $1$ would never ignite its cauldron, output $-1$. This sample input satisfies the constraints of Subtasks $1, 3, 5, 7$. ### Sample 2 This sample input satisfies the constraints of Subtasks $1, 2, 5, 7$. ### Constraints - $2 \le N \le 150000$. - $0 \le C_i \le N$ ($1 \le i \le N$). - $1 \le A_j < B_j \le N$ ($1 \le j \le N-1$). - $1 \le D_j \le 1000000$ ($1 \le j \le N-1$). - It is possible to travel from any city to any other city by traversing a number of highways. - $1 \le Q \le 150000$. - If $P_k = 1$, we have $1 \le V_k \le N$, $0 \le X_k \le N$ ($1 \le k \le Q$). - If $P_k = 2$, we have $1 \le E_k \le N-1$, $1 \le X_k \le 1000000$ ($1 \le k \le Q$). - If $P_k = 3$, we have $1 \le V_k \le N$ ($1 \le k \le Q$). - Given values are all integers. ### Subtasks 1. (6 points) $N \le 2000$, $Q \le 2000$. 2. (7 points) $A_j = 1$, $B_j = j+1$ ($1 \le j \le N-1$). If $P_k = 3$, we have $V_k = 1$ ($1 \le k \le Q$). 3. (14 points) $N-1$ is divisible by $3$. $A_j = ((j-1) \mod \frac{N-1}{3}) + 1$, $B_j = j+1$ ($1 \le j \le N-1$). If $P_k = 3$, we have $V_k = 1$ ($1 \le k \le Q$). 4. (25 points) $P_k \ne 1$. If $P_k = 3$, we have $V_k = 1$ ($1 \le k \le Q$). 5. (12 points) If $P_k = 3$, we have $V_k = 1$ ($1 \le k \le Q$). 6. (22 points) $P_k \ne 1$ ($1 \le k \le Q$). 7. (14 points) No additional constraints.