P3345 [ZJOI2015] Gensokyo Strategy Game

The tsundere girl Yuuka is playing a very interesting strategy game. At first, the game map was not too large, and Yuuka could still manage it. But for some reason, the online game developers are making the map larger and larger, to the point that Yuuka can no longer take it all in at a glance, let alone fight others. Before going to war, Yuuka needs to solve a very basic management problem. The entire map is a tree with $n$ empty fields (nodes), connected by $n - 1$ weighted edges, so that there is a unique path between any two nodes. In the game, Yuuka may increase or decrease troops on empty fields. At the same time, she can place one supply station on a node. If the supply station is at node $u$, and there are $d_v$ units of troops at node $v$, then Yuuka must spend $d_v \times \text{dist}(u,v)$ money per day to supply these troops. Since Yuuka needs to supply all troops, the total cost is $\sum (d_v \times \text{dist}(u,v))$ (where $1 \le v \le n$). Here, $\text{dist}(u,v)$ denotes the distance between $u$ and $v$ on the tree (the sum of weights along the unique path). Due to the game rules, Yuuka can choose only one node as the supply station. During the game, she may create troops on some nodes or reduce troops on some nodes. After such operations, for economic reasons, she may move the supply station to save money. However, since the map is just too large, Yuuka cannot easily make the optimal arrangement. Can you help her? You may assume that initially all nodes have no troops.

The first line contains two integers $n$ and $Q$, denoting the number of nodes in the tree and the number of Yuuka’s operations, respectively. Nodes are labeled from $1$ to $n$. The next $n - 1$ lines each contain three positive integers $a, b, c$, indicating that there is an edge between $a$ and $b$ with weight $c$. The next $Q$ lines each contain two integers $u, e$, meaning Yuuka adds $e$ units of troops at node $u$ (if $e < 0$, that means Yuuka removes $|e|$ units at $u$; in other words, $d_u \leftarrow d_u + e$). It is guaranteed that at any time, the number of troops at each node is non-negative.

For each of Yuuka’s operations, output the minimal daily cost after the operation, i.e., the cost if Yuuka chooses the optimal supply station.

For all testdata, $1 \le c \le 10^3$, $0 \le |e| \le 10^3$, $1 \le n \le 10^5$, $1 \le Q \le 10^5$. Interestingly, for all testdata, the degree of each node in the tree does not exceed $20$. Translated by ChatGPT 5