P16058 [CSPro 31] 阻击

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：。

上回提到，西西艾弗岛下方有一个庞大的遗迹群，栖息着一种名为“阴阳龙”的神兽。然而隔壁的狄迪吉岛盯上了西西艾弗岛，决定发动一场战争，试图从遗迹群中掠夺有价值的宝物。由此，西西艾弗岛不得不陷入一场漫长的阻击战中，史称“阴阳龙阻击战”。 狄迪吉岛拥有胜过西西艾弗岛的科技实力和武装水平，西西艾弗岛很快发现形势不妙：全歼敌军似乎是不可能的，唯一的策略是凭借主场作战的优势和人海战术，尽可能给敌军带来损失，当敌军发现发动进攻的损失明显超过收益时，就会无趣而归。 具体而言，西西艾弗岛共有 $n$ 座城市，有 $n - 1$ 条道路连接这些城市，使得所有城市之间均可以通过道路互相到达。容易发现，任意两座城市之间都有唯一一条不经过重复城市的路径。 由于缺乏城市巷战的实力，西西艾弗岛决定将防御重心放在道路上。在每条道路上均派遣了一定的军队防守，当敌军经过时对其发动阻击。虽然由于实力的差距，并不能阻止敌军通过道路，但仍然可以对敌军造成一定的损失。 然而，敌军具有更强的科技，可以趁机对道路附近的遗迹进行探索，并掠夺其中的宝物——这也正是敌军发动战争的意义所在。如此，敌军通过一条道路时，“发掘宝物的收益”$w$ 和“受到阻击的损失”$b$ 两个值是独立的。 西西艾弗岛事先在狄迪吉岛中安插了一系列间谍，得到的情报消息如下：敌军将选择西西艾弗岛的两座城市作为进攻的“起点”和“终点”，并派遣军队在进攻起点城市登陆，沿两座城市间唯一的路径进攻至终点城市。同时，间谍还背负着另外一个重要的使命：影响敌军对于起点和终点城市的决策，使得敌军受到的总损失尽可能大，其中“总损失”定义为敌军经过的每条道路上的“受到阻击的损失”减去“发掘宝物的收益”之和，即 $\text{总损失} = \sum_{e\ \text{是路径上的每条边}} (b_e - w_e)$。 此外，遗迹中宝物的价值与所处的环境属性密切相关，而阴阳龙的“现身”会使得环境的阴阳属性发生变化，这会使得敌军通过现身位置处的某一条道路时“发掘宝物的收益”$w$ 发生变化。 这样的“阴阳龙现身”事件共会发生 $m$ 次，你的任务就是帮助间谍计算出在所有事件前及每次事件后，敌军对于起点和终点城市的决策应当怎样改变，以最大化敌军的总损失。

从标准输入读入数据。 第 $1$ 行，两个非负整数 $n, m$，分别表示西西艾弗岛的城市数和“阴阳龙现身”事件数。 接下来 $n - 1$ 行，每行 $4$ 个非负整数 $u_i, v_i, w_i, b_i$，表示第 $i$ 条道路连接城市 $u_i$ 和 $v_i$，敌军在这条道路上“发掘宝物的收益”为 $w_i$，“受到阻击的损失”为 $b_i$。 接下来 $m$ 行，每行 $2$ 个非负整数 $x_i, y_i$，表示一次“阴阳龙现身”事件，使得第 $x_i$ 条道路的“发掘宝物的收益”变为 $y_i$。

输出到标准输出。 输出 $m + 1$ 行，每行一个非负整数，分别表示在所有事件前及每次事件后，对敌军造成的最大总损失。

### 样例 1 解释 在最初，由于敌人攻打每一条道路都会有正收益，因此间谍最好的策略就是将进攻起点和终点选为同一座城市，这样敌军的总损失为 $0$。 第 $1$ 次事件后，间谍可以将进攻起点和终点分别选在城市 $3$ 和 $4$，这样敌军的总损失为 $3 - 2 = 1$。 第 $2$ 次事件后，间谍可以将进攻起点和终点分别选在城市 $4$ 和 $5$，这样敌军的总损失为 $(3 - 2) + (5 - 3) = 3$。 第 $3$ 次事件后，间谍可以将进攻起点和终点分别选在城市 $1$ 和 $5$，这样敌军的总损失为 $(4 - 1) + (1 - 2) + (5 - 3) = 4$。 ### 数据范围 对于所有测试数据保证：$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$。 | 测试点编号 | $n \le$ | $m \le$ | 特殊性质 | |:----------:|:-----------:|:-----------:|:--------:| | 1 | 20 | 20 | 无 | | 2 | 300 | 300 | ^ | | 3 ~ 4 | 3000 | 3000 | A | | 5 ~ 6 | ^ | ^ | B | | 7 ~ 9 | ^ | ^ | 无 | | 10 | $10^5$ | 0 | A | | 11 | ^ | ^ | B | | 12 | ^ | ^ | 无 | | 13 ~ 15 | ^ | $10^5$ | A | | 16 ~ 18 | ^ | ^ | B | | 19 ~ 21 | ^ | ^ | C | | 22 ~ 25 | ^ | ^ | 无 | 特殊性质 A：$u_i = i, v_i = i + 1$。 特殊性质 B：$0 \le w_i, y_i \le 10^8 \le b_i$。 特殊性质 C：保证任意两座城市均可在经过不超过 $100$ 条道路的前提下互相到达。