{"problem":{"name":"[PA 2024] Kolorowy las","description":{"content":"**题目译自 [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$ 编号，有正整数边权","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":5000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10359"},"statements":[{"statement_type":"Markdown","content":"**题目译自 [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\n给定 $n$ 个点的森林（无向无环图），点从 $1$ 到 $n$ 编号，有正整数边权，每个点有颜色，初始所有点颜色为 $0$。\n\n有 $4$ 种共 $q$ 个操作：\n\n- $1\\ a_i\\ b_i\\ d_i$：在 $a_i$ 和 $b_i$ 之间添加一条边权为 $d_i$ 的边（保证添加之后图中仍无环）；\n- $2\\ a_i\\ b_i$：删除 $a_i$ 和 $b_i$ 之间的边；\n- $3\\ v_i\\ z_i\\ k_i$：把所有可以到达 $v_i$ 且到 $v_i$ 的距离小于等于 $z_i$ 的顶点染色为 $k_i$；\n- $4\\ u_i$：查询点 $u_i$ 的颜色。\n\n## Input\n\n第一行三个整数 $n,m,q\\ (2\\le n\\le 200\\,000,0\\le m\\le n-1,1\\le q\\le 200\\,000)$，分别表示点数，边数和操作数。\n\n接下来 $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$ 的边。\n\n接下来 $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$。\n\n保证给定的 $m$ 条边形成一个合法的森林，图在经过修改后仍然形成一个合法的森林，并且保证不会删除图中不存在的边。\n\n此外，还保证至少存在一个操作 $4$。\n\n## Output\n\n对于每一个操作 $4$ 输出一行一个整数，表示答案。\n\n[samples]\n\n## Background\n\nPA 2024 4A\n\n## Note\n\n- 在某些子任务中，不存在操作 $1$ 和 $2$，且 $m=n-1$；\n- 在某些子任务中，操作 $3$ 中均有 $z_i=10^{15}$。\n\n对于上述每种附加限制，都至少有一个子任务能满足。满足两种附加限制的子任务集合可能相交，也可能不相交。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10359","tags":["2024","PA（波兰）"],"sample_group":[["4 2 9\n1 2 2\n3 2 5\n4 2\n3 2 2 5\n4 1\n3 2 4 3\n4 1\n4 3\n2 2 1\n1 1 4 1\n4 4\n","0\n5\n3\n0\n0\n"]],"created_at":"2026-03-03 11:09:25"}}