#P3466. 动态仙人掌 III

动态仙人掌 III

题目描述

有一天,VFleaKing到森林里游玩,回来之后跟pyx1997说,我发现好多棵会动的树耶!
pyx1997说,这有什么好稀奇的,我用手指头就能维护每棵树的形态。
于是又过了几天VFleaKing到沙漠里游玩,回来之后跟pyx1997说,我发现好多棵会动的仙人掌耶!
pyx1997说,这有什么好稀奇的,我用脚丫子就能维护每棵仙人掌的形态。
于是VFleaKing很郁闷,他向你求助,请帮帮他吧。

如果一个无向连通图的任意一条边最多属于一个简单环,我们就称之为仙人掌。
如果一个无向图的每个连通块都是个仙人掌,且不存在自环,我们就称之为沙漠。

为了证明你确实能够维护仙人掌,我们给你n个结点,从1到n标号。初始时没有任何边。每次进行如下操作之一:
1. link v u wA wB
    在结点v, u间连一条权值A为wA、权值B为wB的边。1 <= v, u <= n且wA, wB为正整数。
    如果连边完成后图仍为沙漠,则输出"ok"(不含引号)。
    否则操作非法,撤销此次操作并输出"failed"(不含引号)。
2. cut v u wA wB 在结点v, u间删掉权值A为wA、权值B为wB的边。1 <= v, u <= n且wA, wB为正整数。
    如果存在这样的边则输出"ok"(不含引号)(如果有多条权值A为wA、权值B为wB的边删去任意一条)。
    否则操作非法,不进行操作并输出"failed"(不含引号)。
3. distance? v u 查询结点v到结点u的按权值A计算的最短路信息。1 <= v, u <= n。
    输出两个用空格隔开的整数Lm, Wm。
    Lm代表按权值A计算的最短路的长度,Wm代表最短路上的边的权值B的最小值。
    如果v = u则Lm = 0, Wm = 2147483647。
    如果没有路可到达则Lm = -1, Wm = -1。
    如果最短路不唯一则Wm = -1。
4. add v u d 把结点v到结点u的按权值A计算的最短路上的每一条边的权值B都加上d。1 <= v, u <= n, v != u且d为正整数。
    如果有路可到达且最短路唯一,则输出"ok"(不含引号)
    否则操作非法,不进行操作并输出"failed"(不含引号)。

输入格式

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

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

输出格式

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

6 56
link 1 2 1 3
link 1 2 2 5
distance? 1 2
cut 1 2 1 3
link 1 2 2 5
distance? 1 2
cut 1 2 2 5
link 1 2 2 4
add 1 2 1
cut 1 2 2 4
cut 1 2 2 5
link 3 3 2 2
cut 4 4 2 2
link 1 2 2 4
link 1 3 3 5
link 2 3 4 3
distance? 1 2
distance? 1 3
distance? 2 4
add 1 2 3
link 2 4 3 2
link 3 5 3 4
link 4 5 1 5
distance? 4 5
cut 1 2 2 7
link 4 5 5 4
distance? 1 5
cut 2 3 4 3
link 2 5 5 3
link 1 5 2 4
distance? 1 2
add 3 4 3
cut 4 5 5 7
distance? 1 2
cut 3 5 3 7
distance? 1 2
cut 2 5 5 4
cut 2 5 5 3
distance? 1 2
add 1 2 3
link 3 5 6 7
distance? 1 3
add 3 5 1
distance? 5 3
distance? 4 3
link 4 6 3 1
link 2 6 7 2
distance? 2 6
link 5 6 2 4
distance? 1 6
distance? 2 3
cut 2 4 3 2
link 2 5 4 3
distance? 4 1
cut 4 6 3 1
distance? 4 1
ok
ok
1 3
ok
ok
2 -1
ok
ok
failed
ok
ok
failed
failed
ok
ok
ok
2 4
3 5
-1 -1
ok
ok
ok
failed
10 2
ok
ok
6 4
ok
ok
ok
7 3
ok
ok
7 3
ok
7 3
failed
ok
-1 -1
failed
ok
3 5
ok
5 5
-1 -1
ok
ok
6 1
ok
4 4
13 1
ok
ok
7 1
ok
-1 -1

数据范围与约定





1 <= n <= 100000



1 <= m <= 500000



保证中间有关边权的计算不会超过int范围。(祝pascal选手早日转C++,其实我在说longint)