【整体二分】P3250 [HNOI2016] 网络

查询相当于劈成两棵树，分别求子树内路径最大权值，直接使用数据结构维护是困难的。

考虑二分变为判定性问题，若当前询问 $x$ 上 $>\mathrm{mid}$ 的路径与全局的数量相符，则说明对于 $x$ 的答案 $\le \mathrm{mid}$，若使用树上差分 + 树状数组，则可以在 $O(n\log n)$ 内完成统计。

对于多个询问考虑整体二分，即对于 $[l,r]$ 只处理和这一部分有关的询问和操作，因为对于 $x\in [l,r]$，$>r$ 的路径已经在先前的二分证明全部经过了 $x$，所以与这一层二分是无关的。

每个操作和询问只会被二分操作 $\log n$ 次，因此时间复杂度 $O(n{\log }^{2}n)$。