#P2173. [ZJOI2012] 网络

    ID: 1191 远端评测题 2000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2012各省省选浙江SplayLink-Cut TreeLCT

[ZJOI2012] 网络

题目描述

有一个无向图 GG,每个点有个权值,每条边有一个颜色。这个无向图满足以下两个条件:

1、 对于任意节点连出去的边中,相同颜色的边不超过两条。

2、图中不存在同色的环,同色的环指相同颜色的边构成的环。

在这个图上,你要支持以下三种操作:

  • 0 x y 表示把节点 xx 的权值改为 yy

  • 1 u v w 表示将边 (u,v)(u,v) 的颜色改为 ww

  • 2 c u v 表示查询由颜色 cc 的边构成的图中,所有可能在 uvu \to v 之间的简单路径上的节点的权值的最大值。

输入格式

第一行四个正整数 n,m,C,kn,m,C,k,分别表示节点数、边数、颜色数和操作数。

接下来 nn 行,每行一个正整数 viv_i,为节点 ii 的权值。

之后 mm 行,每行三个正整数 u,v,wu,v,w,为一条连接 u,vu,v 节点的边,颜色为ww

最后 kk 行,每行若干个正整数,表示一次操作。

输出格式

输出若干行,每行输出一个对应的信息。

1、 对于修改节点权值操作,不需要输出信息。

2、对于修改边的颜色操作,按以下几类输出:

  • 若不存在连接节点 uu 和节点 vv 的边,输出 No such edge.

  • 若修改后不满足条件 11,不修改边的颜色,并输出 Error 1.

  • 若修改后不满足条件 22,不修改边的颜色,并输出 Error 2.

  • 其他情况,成功修改边的颜色,并输出 Success.

输出满足条件的第一条信息即可,即若同时不满足条件 1,21,2 ,则只需要输出Error 1.

3、 对于查询操作,输出一个整数表示答案。若 u,vu,v 之间没有颜色 cc 构成的路径,则输出 1-1

4 5 2 7
1
2
3
4
1 2 0
1 3 1
2 3 0
2 4 1
3 4 0
2 0 1 4
1 1 2 1
1 4 3 1
2 0 1 4
1 2 3 1
0 2 5
2 1 1 4
4
Success.
Error 2.
-1
Error 1.
5

提示

颜色 00 为实线的边,颜色 11 为虚线的边,

由颜色 00 构成的从节点 11 到节点 44 的路径有 1241 \to 2 \to 4,故max{v1,v2,v4}=max{1,2,4}=4\max\{v_1, v_2, v_4\} = \max\{ 1, 2, 4 \} = 4

将连接节点 11 和节点 22 的边修改为颜色 11,修改成功,输出 Success.

将连接节点 44 和节点 33 的边修改为颜色 11,由于修改后会使得存在由颜色 11 构成的环( 124311 – 2 – 4 – 3 – 1 ),不满足条件 22,故不修改,并输Error 2

不存在颜色 00 构成的从节点 11 到节点 44 的边,输出 -1

将连接节点 22 和节点 33 的边修改为颜色 11,由于修改后节点 22 的连出去的颜色为 11 的边有 33 条,故不满足条件 11,故不修改,并输出Error 1.

将节点 22 的权值修改为 55

由颜色 11 构成的从节点 11 到节点 44 的路径有 1241 \to 2 \to 4,故max{v1,v2,v4}=max{1,5,4}=5\max\{v_1, v_2, v_4\} = \max\{ 1, 5, 4 \} = 5

【数据范围】

对于 30%30\% 的数据:n1000n ≤ 1000m104m ≤ 10^4k1000k ≤ 1000
另有 20%20\% 的数据:n104n ≤ 10^4m105m ≤ 10^5C=1C = 1k105k ≤ 10^5
对于 100%100\% 的数据:n104n ≤ 10^4m105m ≤ 10^5C10C ≤ 10k105k ≤ 10^5

1u,v,xn1\le u,v,x \le n0c<C0 \le c < C,保证图中没有重边和自环。