Rabbit

Build the Kruskal reconstruction tree of the original graph. The maximum bottleneck value between two vertices is represented by the value of their LCA in this tree.

Fix the final vertex $t$. If a unit of mana at vertex $v$ is collected as the $k$-th unit, then after collecting it the rabbit must still be able to travel from $v$ to $t$ while carrying $k$ units. Thus each mana unit can be treated as a unit-time job with a deadline.

If there are $c$ units with deadline $d$, the greedy transition is

$$x \mapsto \min(d,x+c).$$

Equivalently, the answer is

$$\min_D \left(D+\text{the number of mana units with deadline greater than }D\right).$$

For a query edge $(s,t,w)$, the two sides of the edge are connected while the threshold is below $w$. Therefore, on the Kruskal tree, we pull the two current components upward in decreasing order of edge values and update the answer candidates.

Processing the whole path for every query gives an $O(QH)$ solution, where $H$ is the height of the Kruskal tree. Under special condition B, the original graph is a path with random distinct capacities, so the Kruskal tree is a random Cartesian tree and has expected logarithmic height.

For the full solution, choose special vertices in the Kruskal tree so that every vertex is within $O(\sqrt N)$ edges from its nearest special ancestor. Each query is directly processed until one side reaches a special vertex.

For a fixed special vertex $b$, all remaining queries with one endpoint $b$ are processed together. Precompute prefixes of type X operations on the chain from $b$ to the root, and simulate all type Y operations on the other endpoints by DFS. This processes one special vertex in $O(N)$ time. Since there are $O(\sqrt N)$ special vertices, the total running time is .