P3250 [HNOI2016] Network

A simple network system can be described as an unrooted tree. Each node is a server. The data cable connecting servers is treated as a tree edge. When two servers exchange data, the data passes through all servers on the unique path connecting these two servers (including the two servers themselves). Because this path is unique, if any server on the path fails and cannot operate normally, the data cannot be exchanged. In addition, each data exchange request has an importance value, and more important requests should clearly receive higher priority. Now, as the administrator of a network system, you need to monitor the system’s operating status. The system behavior is simple: at each time, exactly one of the following three events may occur: 1. A new data exchange request appears between two servers. 2. A data exchange request ends. 3. A server fails. The system will repair it immediately after any failure. That is, right after the moment the failure occurs, this server is still normal. However, at the moment the failure occurs, it still affects data exchange requests that need to pass through this server. Your task is to maintain, for each failure, the maximum importance value among the requests that are not affected. Note that if a data exchange request has already ended, it is not considered among the unaffected requests. Note that a data exchange request may occur between a server and itself. $2 \le n \le 10^5$, $1 \le m \le 2\times 10^5$, and all other input values do not exceed $10^9$.

The first line contains two positive integers $n,m$, denoting the numbers of servers and events, respectively. Server IDs start from $1$, so the $n$ servers are numbered $1,2,3,\cdots,n$. The next $n-1$ lines each contain two positive integers $u,v$, describing a tree edge. $u$ and $v$ are server IDs. The next $m$ lines describe each event in chronological order; that is, the $i$-th line ($i=1,2,3,\ldots,m$) describes the event that occurs at time $i$. The first number $\mathrm{type}$ denotes the event type, with three types in total: 1. If $\mathrm{type}=0$, then three positive integers $a,b,v$ follow, meaning that a data exchange request with importance $v$ appears between servers $a$ and $b$. 2. If $\mathrm{type}=1$, then a positive integer $t$ follows, meaning that the data exchange request that appeared at time $t$ (i.e., the $t$-th event) ends. 3. If $\mathrm{type}=2$, then a positive integer $x$ follows, meaning that server $x$ fails at this moment. Each event with $\mathrm{type}=2$ is a query, i.e., “When server $x$ fails, what is the maximum importance among the requests that are not affected?”

For each event with $\mathrm{type}=2$ (i.e., a server failure), output one line with one integer, the maximum importance among the requests that are not affected. If there is currently no request, or all requests are affected, output $-1$.

The tree given in the sample is shown below:  Explanations for some queries; in the explanations below, $(a,b;t,v)$ denotes a request that appears at time $t$ between servers $a$ and $b$ with importance $v$: For the first query (at time $1$), there is no request, so output $-1$. For the fourth query (at time $6$), there are two requests $(8,13;2,3)$ and $(9,12;3,5)$. Both paths pass through server $2$, so output $-1$. For the fifth query (at time $8$), there are three requests $(8,13;2,3)$, $(9,12;3,5)$, and $(10,12;7,1)$. Only the request $(10,12;7,1)$ does not pass through server $2$, so output its importance $1$. For the last query (at time $23$), there are three requests $(9,5;12,6)$, $(9,12;16,4)$, and $(10,5;17,7)$. When server $3$ fails, only the request $(9,5;12,6)$ does not pass through server $3$, so output $6$. $\text{upd 2016.5.20}$：Added one set of $\text{Hack}$ testdata. Translated by ChatGPT 5