#P4683. 动态仙人图

    ID: 3816 传统题 3000ms 256MiB 尝试: 41 已通过: 6 难度: 10 上传者: 标签>CF3500NOI/NOI+/CTSLink-Cut TreeSplay点双连通分量耳分解图的边细分实链/虚链维护动态路径聚合有序映射byAwD&

动态仙人图

题目描述

有一张包含 nn 个结点的无向加权图,初始没有边。若每条边至多属于两个简单环,则称这张图为仙人图。重边按各自的边区分,两条连接同一对结点的边也可以组成一个简单环。

需要依次处理以下三类操作。

  • link a b w:尝试添加一条连接 a,ba,b、权重为 ww 的边。若 a=ba=b 或添加后不满足仙人图条件,输出 failed 并保持原图。否则添加该边并输出 ok。
  • cut a b w:尝试删除一条连接 a,ba,b、权重为 ww 的边。如果存在,任意删除其中一条并输出 ok。如果不存在,输出 failed。
  • distance? a b:输出 aa 到 bb 的最短路长度。如果两点不连通,输出 -1。如果 a=ba=b,输出 0。

输入格式

第一行两个整数 n,mn,m,分别表示结点数和操作数。接下来 mm 行,每行描述一条操作,格式如上。

输出格式

每个操作输出一行。

数据范围

1≤n≤1051\le n\le10^5,1≤m≤3×1051\le m\le3\times10^5,1≤a,b≤n1\le a,b\le n。本站评测数据中,添加和删除操作的权重参数均为整数,满足 0≤w≤327680\le w\le32768。边长相关的计算结果在有符号 32 位整数范围内。

样例

5 12
link 1 2 3
link 2 3 3
distance? 1 3
cut 2 3 3
distance? 1 3
cut 2 3 2
link 2 3 2
cut 2 3 3
link 3 4 3
link 4 1 5
link 1 3 8
link 2 4 7
ok
ok
6
ok
-1
failed
ok
failed
ok
ok
ok
failed
6 25
link 1 2 3
link 1 2 2
link 1 2 5
cut 1 2 2
cut 1 2 5
link 1 2 3
link 1 2 3
cut 1 2 3
cut 1 2 3
cut 1 2 3
cut 1 2 3
link 1 2 4
link 1 3 5
distance? 2 3
link 2 4 1
link 3 4 2
link 2 3 3
link 1 4 7
link 1 4 7
cut 1 4 7
link 5 6 8
distance? 3 6
distance? 2 6
cut 2 4 1
distance? 1 5
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
failed
ok
ok
9
ok
ok
ok
failed
failed
failed
ok
-1
-1
ok
-1

题目来源