Water__Problem @ 2025-01-26 09:04:38
求usaco金组T1
by BuQiuRu4587 @ 2025-01-26 12:40:15
对于一次询问，把 <x 的点看作 0，=x 看作 1，>x 看作 2，设 f_{i,0/1/2} 表示节点 i 权值为 0/1/2 的最小值，直接dp即可。
考虑多次询问，发现不同树的形态只有 O(n) 种，并且总修改量也是 O(n) 的，每次修改只改一条链上的 dp 值，只有 \log n 个，总复杂度 O(n\log n)。