P6666 [Tsinghua Training 2016] Data Interaction

A simple network system can be described as an unrooted tree. Each node is a server. A cable connecting two servers is considered an edge of the tree. When two servers perform a data interaction, the data passes through all servers on the path connecting these two servers (including the two servers themselves). Each data interaction request has a non-negative importance value. Obviously, more important requests should be processed with higher priority. In addition, if at some moment there is an extremely important (can be considered to have infinite importance) and very large data-volume interaction request, then all servers on the path of this interaction will prioritize this interaction and become blocked, which causes delays to other interactions that pass through these servers. Now, as the administrator of this network system, you need to monitor the running status of the whole system. The system operation is also simple: at each moment, only one of the following two types of events may occur: - A new data interaction request appears between two servers. - A data interaction request ends. We assume that the data volume of the interaction requests in these events is small enough. Your task is: after the event at each moment ends, compute the following value: if an extremely important and very large data-volume interaction request suddenly appears, what is the maximum possible sum of importance values of the data interaction requests that would be delayed because of it?

The first line contains two positive integers $n, m$, representing the number of servers and the number of events (moments), respectively. The next $n - 1$ lines each contain two integers $u, v$, describing an edge of the tree. $u$ and $v$ are server indices, and the servers are numbered $1, \ldots, n$. The next $m$ lines describe each event in chronological order; that is, line $i$ ($i = 1, 2, 3, \ldots, m$) describes the event that occurs at moment $i$. There are two types of event descriptions: - `+ u v w`: a data interaction request with importance $w$ appears between servers $u$ and $v$. - `- t`: the data interaction request that appeared at moment $t$ ends.

Output $m$ lines, each containing one integer, describing in order, after each event, if an extremely important and very large data-volume interaction request suddenly appears, the maximum possible sum of importance values of the data interaction requests that would be delayed because of it. If there is no data interaction request at this moment, output $0$.

For $30\%$ of the testdata, $1 \le n, m \le 100$. For another $30\%$ of the testdata, there is no second type of event, i.e., all requests will never end. For $100\%$ of the testdata, $1 \le n, m \le 10^5$, and all input data are non-negative integers within the `int` range. It is guaranteed that the input is valid. Translated by ChatGPT 5