UOJ Logo Universal Online Judge

UOJ

#106. 动态仙人掌 IV

附件下载 统计

有一天,wangyisong1996到森林里游玩,回来之后跟VFleaKing说,我发现好多棵会动的树耶!VFleaKing说,这有什么好稀奇的,我用手指头就能维护每棵树的形态。

于是又过了几天wangyisong1996到沙漠里游玩,回来之后跟VFleaKing说,我发现好多棵会动的仙人掌耶!VFleaKing说,这有什么好稀奇的,我用脚丫子就能维护每棵仙人掌的形态。

于是wangyisong1996很郁闷,他向你求助,请帮帮他吧。

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

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

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

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

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

输入格式

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

接下来一行 n 个正整数,第 i 个正整数为 wi

接下来 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
-2 -2
5 73
16 85
ok
5 263
16 185
ok
1005 4233
ok
1011 9907

样例二

见样例数据下载。

限制与约定

1n50000,1m250000

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

保证初始的 wi 不超过 109,保证所有 add1 和 add2 操作中的 d 之和不超过 109

时间限制:6s

空间限制:256MB

下载

样例数据下载