核心难点

动态连接/断开：需要高效维护树结构的变化 距离限制的范围操作：传统的子树操作不适用，因为距离限制可能跨越多个子树 大规模数据：n, q ≤ 2×10^5，需要 O(n log n) 或 O(n log² n) 的算法

关键观察

观察1：距离限制的等价表述 对于操作 3 v z k，在以 v 为根的树中，我们要染色所有满足 dist(v, u) ≤ z 的点 u。

这等价于：dist(v, u) = dist(v, w) + dist(w, u) ≤ z，其中 w 是 u 到 v 路径上的任意点。

观察2：离线处理的可能性 由于操作可离线，我们可以： 先建立完整的操作时间线，用线段树分治处理，动态连接/断开，对每个连通块独立处理

核心思路：

用动态树维护森林结构 对每个染色操作，在动态树上从v开始进行有限范围的BFS/DFS，用时间戳记录每个点最后一次被染色的时间和颜色

算法选择与优化

对于不同数据范围： 小规模 (n ≤ 5000)：直接BFS染色 只有查询3和4：预处理 + 离线处理 z_i很大：直接染色连通块

完整动态：Link-Cut Tree + 有限BFS

时间复杂度优化： 动态树：O(log n) 每次连接/断开 范围染色：O(受影响节点数)， 但通过提前终止可优化 查询：O(1) 直接访问数组