题目背景

PA 2024 4A

题目描述

题目译自 PA 2024 Runda 4 Kolorowy las，感谢 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$ 的颜色。

输入格式

第一行三个整数 $n,m,q\ (2\le n\le 200\,000,0\le m\le n-1,1\le q\le 200\,000)$，分别表示点数，边数和操作数。

接下来 $m$ 行，每行三个整数 $a_i,b_i,d_i\ (1\le a_i,b_i\le n,1\le d_i\le 10^9)$，表示点 $a_i$ 和 $b_i$ 之间有一条长度为 $d_i$ 的边。

接下来 $q$ 行描述操作，格式如题目描述。保证 $1\le a_i,b_i,v_i,u_i\le n$，$1\le d_i\le 10^9$，$0\le z_i\le 10^{15}$，$1\le k_i\le 10^9$。

保证给定的 $m$ 条边形成一个合法的森林，图在经过修改后仍然形成一个合法的森林，并且保证不会删除图中不存在的边。

此外，还保证至少存在一个操作 $4$。

输出格式

对于每一个操作 $4$ 输出一行一个整数，表示答案。

4 2 9
1 2 2
3 2 5
4 2
3 2 2 5
4 1
3 2 4 3
4 1
4 3
2 2 1
1 1 4 1
4 4

0
5
3
0
0

提示

• 在某些子任务中，不存在操作 $1$ 和 $2$，且 $m=n-1$；
• 在某些子任务中，操作 $3$ 中均有 $z_i=10^{15}$。

对于上述每种附加限制，都至少有一个子任务能满足。满足两种附加限制的子任务集合可能相交，也可能不相交。