自己不想写代码了，来个 tlqtj

首先有一个依赖于 $O(n\log n)-O(1)\ \text{lca}$ 的根号做法，快速讲：就是对操作分块，若查询到的是同块内的操作，则直接暴力查即可。

否则对每个块内的修改操作，做一次 $\texttt{bfs}$，可以类似理解为多源最短路，然后查询直接跳直接的整块询问"最短路"即可。

所有基于 $O(1)\ \text{lca}$ 不带 $\log$，设 $n,m$ 同阶，复杂的为 $O(n\sqrt n)$。

---

但是这题一看很 $\log$ 啊，我根本没想根号。但事实上根号好写好调，$\log$ 相对都难写。

下面是一个不需要三度化点分树的 $O(n\log n)$，基本只基于树剖，有错误请指出。

首先 $dis(u,v)=d_u+d_v-2d_{\text{lca}(u,v)}$，于是查询只需求 $\min\limits_{col_v=red} -2d_{\text{lca}(u,v)}+d_v$。

枚举 $\text{lca}$，即求 $\min\limits_{t=gp_u} \left(-2d_{t}+\left(\min\limits_{\substack{v\in subtree_u\\ \text{lca}(u,v)=t\\ col_v=red}} d_v\right)\right)$，其中 $gp$ 表示非严格祖先集合。

考虑后面那个 $\min$，发现 $\text{lca}(u,v)=t$ 是不必要的，因为若不等于，则一定存在等于的方案被计算过了，而且这里计算会更劣，大家自己思考一下。

于是即求 $\min\limits_{t=gp_u} (-2d_{t}+f_t)$，其中 $f(t)=\min\limits_{v\in subtree_u, col_v=red} d_v$。

这里是经典瓶颈了，所谓瓶颈就在 $-2d_{t}$ 上。大概一年前推到类似地方不会了。

考虑修改 $x$ 对 $f(t)$ 的影响，发现是 $\forall t\in gp_x$，$f(t)\gets\min(f(t),d_x)$。看起来是正常的取 $\min$。（其中初值 $f(1)=1$，其他初值为 $+\infty$）

但是查询是形如 $\min(a_i+b_i)$ 的，其中只修改 $b_i$。这时要智慧了。

考虑重剖，发现修改形如：对 $O(1)$ 条重链的前缀位置与 $d_x$ 取 $\min$，对剩下的 $O(\log n)$ 条重链的所有位置与 $d_x$ 取 $\min$。查询类似刻画。

由于都是取 $\min$，考虑拆开：把修改前缀位置和修改所有位置开做，发现这挺平衡的，下面对每个重链单独考虑。

---

考虑总共 $O(m\log n)$ 次修改所有位置，查询前缀 $\min\{-2d_i+f_i\}$，直接预处理每个前缀的最小值即可，修改对每位都是相同的。

---

考虑总共 $O(m)$ 次修改所有位置，查询 $O(n)$ 次前缀 $\min\{-2d_i+f_i\}$，$O(m\log n)$ 次全局这个最小值。发现 $f$ 单调，答案单调，往颜色段均摊方面想，于是考虑 $\texttt{set}$ 维护所有相同的 $f$ 连续段（下面成为同颜色段）。

修改直接对颜色段做，类似珂朵莉树，每个颜色段记那东西的 $\min$，修改后合并颜色段是好做的，由于每个段加入一次删除（被合并）一次，于是摊 $O(1)$，乘 $\texttt{set}$ 的 $\log$ 就 $O(\log n)$，这时候查询前缀显然是好 $O(\log n)$ 的，全局最小直接每次修改都更新一下即可，修改复杂的不变，查全局变成 $O(1)$。

---

这下所有复杂度都对了，是 $O(n\log n)$ 的，常数肯定不大。但个人不想写，希望后人填坑（或指出假的地方）。实现上重链记 $top$ 的同时记 $end$ 就能锁定重链，然后每个重链开 $\texttt{set}$ 做即可。

并不后的后记：当时不自信去 uoj 群问做法了，发现有人提出一样的了，大概是对的吧，还学了很多新东西：

考虑我们区间查的形如 $\min\{a_i+b_i\}$ 的东西，区间改 $b_i$，为与 $x$ 取 $\min$，存在吉司机线段树 $O(n\log n)$ 的做法（因为说没区间加是单 $\log$ 的），我不会吉老师所以没细讲。一个弱化点的版本为 loj 3033，一个好题解在这里。