P2173 [ZJOI2012] 网络

有一个无向图 $G$，每个点有个权值，每条边有一个颜色。这个无向图满足以下两个条件： 1、 对于任意节点连出去的边中，相同颜色的边不超过两条。 2、图中不存在同色的环，同色的环指相同颜色的边构成的环。 在这个图上，你要支持以下三种操作： - `0 x y` 表示把节点 $x$ 的权值改为 $y$ - `1 u v w` 表示将边 $(u,v)$ 的颜色改为 $w$。 - `2 c u v` 表示查询由颜色 $c$ 的边构成的图中，所有可能在 $u \to v$ 之间的简单路径上的节点的权值的最大值。

无

无

 颜色 $0$ 为实线的边，颜色 $1$ 为虚线的边， 由颜色 $0$ 构成的从节点 $1$ 到节点 $4$ 的路径有 $1 \to 2 \to 4$，故$\max\{v_1, v_2, v_4\} = \max\{ 1, 2, 4 \} = 4$。 将连接节点 $1$ 和节点 $2$ 的边修改为颜色 $1$，修改成功，输出 `Success.` 将连接节点 $4$ 和节点 $3$ 的边修改为颜色 $1$，由于修改后会使得存在由颜色 $1$ 构成的环( $1 – 2 – 4 – 3 – 1$ )，不满足条件 $2$，故不修改，并输`Error 2`。 不存在颜色 $0$ 构成的从节点 $1$ 到节点 $4$ 的边，输出 `-1`。 将连接节点 $2$ 和节点 $3$ 的边修改为颜色 $1$，由于修改后节点 $2$ 的连出去的颜色为 $1$ 的边有 $3$ 条，故不满足条件 $1$，故不修改，并输出`Error 1.` 。 将节点 $2$ 的权值修改为 $5$。 由颜色 $1$ 构成的从节点 $1$ 到节点 $4$ 的路径有 $1 \to 2 \to 4$，故$\max\{v_1, v_2, v_4\} = \max\{ 1, 5, 4 \} = 5$。 【数据范围】 对于 $30\%$ 的数据：$n ≤ 1000$，$m ≤ 10^4$，$k ≤ 1000$； 另有 $20\%$ 的数据：$n ≤ 10^4$，$m ≤ 10^5$，$C = 1$，$k ≤ 10^5$； 对于 $100\%$ 的数据：$n ≤ 10^4$，$m ≤ 10^5$，$C ≤ 10$，$k ≤ 10^5$。 $1\le u,v,x \le n$，$0 \le c < C$，保证图中没有重边和自环。