P16058 [CSPro 31] Interception

The testdata on Luogu is for non-official communication only and is not official testdata. Official judging link: 。

As mentioned last time, beneath Xixi Aifu Island lies a huge group of ruins, home to a divine beast called the “Yin-Yang Dragon”. However, the neighboring Didiji Island has set its sights on Xixi Aifu Island and decided to start a war, trying to plunder valuable treasures from the ruins. Therefore, Xixi Aifu Island had to get involved in a long interception war, historically known as the “Yin-Yang Dragon Interception War”. Didiji Island has stronger technology and military power than Xixi Aifu Island, and Xixi Aifu Island soon realized the situation was bad: completely wiping out the enemy seems impossible. The only strategy is to use the home-field advantage and sheer numbers to inflict as much loss as possible. When the enemy finds that the cost of attacking is clearly greater than the gain, they will lose interest and retreat. Specifically, Xixi Aifu Island has $n$ cities and $n - 1$ roads connecting them, so that any city can reach any other city via roads. It is easy to see that between any two cities there is a unique path with no repeated cities. Because it lacks the ability to fight street battles inside cities, Xixi Aifu Island decided to focus its defense on the roads. A certain amount of troops is stationed on each road to intercept the enemy when they pass. Although the gap in strength means it cannot stop the enemy from passing through, it can still cause some losses. However, the enemy has more advanced technology and can take the chance to explore the ruins near the road and plunder treasures—this is exactly the point of the war. Thus, when the enemy passes a road, the two values “gain from digging treasures” $w$ and “loss from being intercepted” $b$ are independent. Xixi Aifu Island planted a series of spies in Didiji Island in advance and obtained the following intelligence: the enemy will choose two cities on Xixi Aifu Island as the “start point” and “end point” of the attack, land troops at the start city, and advance along the unique path between the two cities to the end city. Meanwhile, the spies also carry another important mission: influence the enemy’s decision on the start and end cities so that the enemy’s total loss is as large as possible. Here, “total loss” is defined as the sum over every road on the path of “loss from being intercepted” minus “gain from digging treasures”, i.e. $\text{Total loss} = \sum_{e\ \text{is each edge on the path}} (b_e - w_e)$. In addition, the value of treasures in the ruins is closely related to the environment’s attributes, and the “appearance” of the Yin-Yang Dragon will change the Yin-Yang attributes of the environment. This will change the “gain from digging treasures” $w$ when the enemy passes one of the roads at the appearing location. There will be $m$ such “Yin-Yang Dragon appearance” events in total. Your task is to help the spies compute, before all events and after each event, how the enemy’s decision on the start and end cities should change to maximize the enemy’s total loss.

Read from standard input. Line $1$ contains two non-negative integers $n, m$, representing the number of cities on Xixi Aifu Island and the number of “Yin-Yang Dragon appearance” events. The next $n - 1$ lines each contain $4$ non-negative integers $u_i, v_i, w_i, b_i$, indicating that the $i$-th road connects cities $u_i$ and $v_i$. On this road, the enemy’s “gain from digging treasures” is $w_i$, and the “loss from being intercepted” is $b_i$. The next $m$ lines each contain $2$ non-negative integers $x_i, y_i$, indicating one “Yin-Yang Dragon appearance” event, which changes the “gain from digging treasures” of the $x_i$-th road to $y_i$.

Write to standard output. Output $m + 1$ lines, each containing one non-negative integer, representing the maximum total loss that can be inflicted on the enemy before all events and after each event, respectively.

### Explanation of Sample 1 Initially, since attacking along any road gives the enemy a positive gain, the spies’ best strategy is to make the start point and end point the same city. In this case, the enemy’s total loss is $0$. After the $1$-st event, the spies can choose city $3$ as the start point and city $4$ as the end point, so the enemy’s total loss is $3 - 2 = 1$. After the $2$-nd event, the spies can choose city $4$ as the start point and city $5$ as the end point, so the enemy’s total loss is $(3 - 2) + (5 - 3) = 3$. After the $3$-rd event, the spies can choose city $1$ as the start point and city $5$ as the end point, so the enemy’s total loss is $(4 - 1) + (1 - 2) + (5 - 3) = 4$. ### Constraints For all testdata, it is guaranteed that: $2 \le n \le 10^5, 0 \le m \le 10^5, 1 \le u_i, v_i \le n, 1 \le x_i \le n - 1, 0 \le w_i, b_i, y_i \le 10^9$. | Test Point ID | $n \le$ | $m \le$ | Special Property | |:-------------:|:-----------:|:-----------:|:----------------:| | 1 | 20 | 20 | None | | 2 | 300 | 300 | ^ | | 3 ~ 4 | 3000 | 3000 | A | | 5 ~ 6 | ^ | ^ | B | | 7 ~ 9 | ^ | ^ | None | | 10 | $10^5$ | 0 | A | | 11 | ^ | ^ | B | | 12 | ^ | ^ | None | | 13 ~ 15 | ^ | $10^5$ | A | | 16 ~ 18 | ^ | ^ | B | | 19 ~ 21 | ^ | ^ | C | | 22 ~ 25 | ^ | ^ | None | Special Property A: $u_i = i, v_i = i + 1$。 Special Property B: $0 \le w_i, y_i \le 10^8 \le b_i$。 Special Property C: it is guaranteed that any two cities can reach each other while passing through no more than $100$ roads. Translated by ChatGPT 5