P10359 [PA 2024] Kolorowy las

PA 2024 4A

**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 4 [Kolorowy las](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/kol/)，感谢 Macaronlin 提供翻译** 给定 $n$ 个点的森林（无向无环图），点从 $1$ 到 $n$ 编号，有正整数边权，每个点有颜色，初始所有点颜色为 $0$。 有 $4$ 种共 $q$ 个操作： - $1\ a_i\ b_i\ d_i$：在 $a_i$ 和 $b_i$ 之间添加一条边权为 $d_i$ 的边（保证添加之后图中仍无环）； - $2\ a_i\ b_i$：删除 $a_i$ 和 $b_i$ 之间的边； - $3\ v_i\ z_i\ k_i$：把所有可以到达 $v_i$ 且到 $v_i$ 的距离小于等于 $z_i$ 的顶点染色为 $k_i$； - $4\ u_i$：查询点 $u_i$ 的颜色。

无

无

- 在某些子任务中，不存在操作 $1$ 和 $2$，且 $m=n-1$； - 在某些子任务中，操作 $3$ 中均有 $z_i=10^{15}$。 对于上述每种附加限制，都至少有一个子任务能满足。满足两种附加限制的子任务集合可能相交，也可能不相交。