样例数据下载

#106. 动态仙人掌 IV

好评 差评 [-681]

题目描述

如果一个无向连通图的任意一条边最多属于一个简单环，我们就称之为仙人掌。

如果一个无向图的每个连通块都是个仙人掌，且不存在自环，我们就称之为沙漠。

为了证明你确实能够维护仙人掌，我们给你 $n$ 个结点，从 1 到 $n$ 标号。

初始时没有任何边，且每个结点 $i$ 有个权值 $w_i (w_i > 0)$。每次进行如下操作之一：

1. link v u w：在结点 $v, u$ 间连一条权值为 $w$ 的边。
   • $1 \le v, u \le n$ 且 $w$ 为正整数。
   • 如果连边完成后图仍为沙漠，则输出 "ok"（不含引号）。
   • 否则操作非法，撤销此次操作并输出 "failed"（不含引号）。
2. cut v u w：在结点 $v, u$ 间删掉一条权值为 $w$ 的边。
   • $1 \le v, u \le n$ 且 $w$ 为正整数。
   • 如果存在这样的边则输出 "ok"（不含引号）（如果有多条权值为 $w$ 的边删去任意一条）。
   • 否则操作非法，不进行操作并输出 "failed"（不含引号）。
3. query1 v u：查询结点 $v$ 到结点 $u$ 的最短路信息。
   • $1 \le v, u \le n$。
   • 输出两个用空格隔开的整数 $\text{min}, \sigma$，分别代表最短路上点权的最小值、和。
   • 如果没有路可到达则 $\text{min} = -1, \sigma = -1$。
   • 如果最短路不唯一则 $\text{min} = -2, \sigma = -2$。
4. query2 v u：查询以结点 $v$ 为根，子仙人掌 $u$ 的信息。
   • $1 \le v, u \le n$。
   • 以结点 $v$ 为根，子仙人掌 $u$ 的定义是，删掉 $v$ 到 $u$ 之间的所有简单路径上的边之后，$u$ 所在的连通块。
   • 输出两个用空格隔开的整数 $\text{min}, \sigma$，分别代表子仙人掌 $u$ 中点权的最小值、和。
   • 如果 $v, u$ 不连通则 $\text{min} = -1, \sigma = -1$。
5. add1 v u d：把结点 $v$ 到结点 $u$ 的最短路上的每一个结点的权值都加上 $d$。
   • $1 \le v, u \le n$ 且 $d$ 为正整数。
   • 如果有路可到达且最短路唯一，则输出 "ok"（不含引号）。
   • 否则操作非法，不进行操作并输出 "failed"（不含引号）。
6. add2 v u d：把以结点 $v$ 为根，子仙人掌 $u$ 的每一个结点的权值都加上 $d$。
   • $1 \le v, u \le n$ 且 $d$ 为正整数。
   • 如果 $v, u$ 在同一个连通块里，则输出 "ok"（不含引号）。
   • 否则操作非法，不进行操作并输出 "failed"（不含引号）。

输入格式

第一行两个用空格隔开的正整数 $n, m$ 表示一共有 $n$ 个结点，$m$ 个操作。

接下来一行 $n$ 个正整数，第 $i$ 个正整数为 $w_i$。

接下来 $m$ 行，每行代表一个操作。

输出格式

对于每个操作，输出相应的结果。

样例一

input

11 23
10 5 11 7 8 14 30 3 16 20 19
link 1 2 5
link 2 3 3
link 3 4 7
link 4 5 8
link 2 6 10
link 6 7 15
link 4 7 3
link 6 8 9
link 6 8 6
link 7 9 12
link 9 11 10
link 7 10 4
link 9 10 8
query1 6 11
query1 2 10
query2 8 7
add1 8 5 100
query1 1 7
query2 8 7
add2 11 7 1000
query1 8 3
add2 3 2 2333
query1 1 5

output

ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
-2 -2
5 73
16 85
ok
5 263
16 185
ok
1005 4233
ok
1011 9907

样例二

见样例数据下载。

限制与约定

$1 \le n \le 50000, 1 \le m \le 250000$。

保证 link 和 cut 操作中的 $w$ 满足 $1 \le w \le 10000$，所以关于边权的计算不会超出 32 位有符号整数范围。

保证初始的 $w_i$ 不超过 $10^9$，保证所有 add1 和 add2 操作中的 $d$ 之和不超过 $10^9$。

时间限制：6s

空间限制：256MB