P4695 [PA 2017] Banany

Bajtazar is a merchant. Every day, he leaves the city he is currently in and travels to another city to sell bananas. Each road has a toll fee, and the destination city provides some revenue (note that intermediate cities provide no revenue). Each day, the fee of one road changes, or the revenue of one city changes. Bajtazar wants to know, after he wakes up each day, which city he should choose as the destination to obtain the maximum profit, and on the next day he will depart from that city again. There are $n$ cities, connected by $n - 1$ roads, and every city is reachable from every other city. City $i$ has revenue $z_i$, and each edge has a fee $w$. If he does business from $s$ to $t$, the profit is $$ z_t - \sum_{e \in \mathrm{Path}(s, t)} w(e) $$ There are $q$ days in total. Initially, Bajtazar is in city $1$. Each day, after the changes take place, he will go to the next city. He will choose the one that yields the maximum profit; if there are multiple, he chooses the one with the smallest index. However, he cannot stay in the same city and must leave.

The first line contains two integers $n$ and $q$. The second line contains $n$ integers representing the revenues $z_1, z_2, \dots, z_n$. The next $n - 1$ lines each contain $u\ v\ w$, describing an edge and its fee. The next $q$ lines are of two types. - Input $1\ i\ z_i$ means replacing the revenue of city $i$ with the new value. - Input $2\ u\ v\ w$ means replacing the fee of the edge connecting cities $(u, v)$ with the new value.

For each change, output one line. In total, output $q$ answers, each indicating Bajtazar's next destination after the change.

Constraints: $n, q \le 10^5$, $1 \le z_i \le 10^{18}$, $1 \le w \le 10^{12}$. Translated by ChatGPT 5