#1969. 基础圆方树练习题
基础圆方树练习题
基础圆方树练习题
题目描述
标题: 基础圆方树练习题 - Problem - QOJ.ac
#8462. 基础圆方树练习题
The problem was used in the following contests:
有一天,AwD 到森林里游玩,回来之后跟 zhangzy 说,我发现好多棵会动的树耶!zhangzy 说,这有什么好稀奇的,我用手指头就能维护每棵树的形态。
于是又过了几天 AwD 到沙漠里游玩,回来之后跟 zhangzy 说,我发现好多棵会动的仙人掌耶!zhangzy 说,这有什么好稀奇的,我用脚丫子就能维护每棵仙人掌的形态。
而后又再过了几天AwD到篮球场上游玩,回来之后跟zhangzy说,我发现好多棵会动的 k-FC 耶!zhangzy 说,这有什么好稀奇的,我什么都不做就能维护每棵 k-FC 的形态了。
于是 AwD 很郁闷,他向你求助,请帮帮他吧。
如果一个无向连通图的任意一条边最多属于 k 个简单环,我们就称之为 k-FC。
如果一个无向图的每个连通块都是个 k-FC,且不存在自环,我们就称之为篮球场。
为了证明你确实能够维护 k-FC,我们给你 n 个结点,从 1 到 n 标号。
初始时没有任何边,且每个结点 i 有个非负权值 wi。每次进行如下操作之一:
-
link v u w:在结点 v,u 间连一条权值为 w 的边。- 1≤v,u≤n 且 w 为正整数,保证操作后图依然是个篮球场。
- 在进行该操作后输出
ok。
-
cut v u w:在结点 v,u 间删去一条权值为 w 的边。- 1≤v,u≤n 且 w 为正整数,保证操作后图依然是个篮球场。
- 在进行该操作后输出
ok(如果有多条权值为 w 的边删去任意一条)。
-
query1 v u:查询结点 v 到结点 u 的最短路信息。- 1≤v,u≤n。
- 输出两个用空格隔开的整数 min,σ,分别代表最短路上点权的最小值、和。
- 如果没有路到达则 min=−1,σ=−1。
- 如果最短路不唯一 min=−2,σ=−2。
-
query2 v u:查询以结点 v 为根,子k-FC u 的信息。- 1≤v,u≤n。
- 以结点 v 为根,子k-FC u 的定义是,删掉 v 到 u 之间的所有简单路径上的边之后,u 所在的连通块。
- 输出两个用空格隔开的整数 min,σ,分别代表子 k-FC u 中点权的最小值、和。
- 如果 v,u 不连通则 min=−1,σ=−1。
-
add1 v u d:把结点 v 到结点 u 的最短路上的每一个结点的权值都加上 d。- 1≤v,u≤n 且 d 为正整数。
- 如果有路可达且最短路唯一,则输出
ok; - 否则操作非法,不进行操作并输出
failed。
-
add2 v u d:把以结点 v 为根,子k-FC u 的每一个结点的权值都加上 d。- 1≤v,u≤n 且 d 为正整数。
- 如果 v,u 在同一个连通块里,则输出
ok; - 否则操作非法,不进行操作并输出
failed。
提示:众所周知,k-FC 是 k-Factors Cactus 的简称。
输入格式
第一行一个整数 T 表示测试集编号。
第二行三个用空格隔开的正整数 n,m,k 表示一共有 n 个结点,m 个操作,每条边最多属于 k 个简单环。
接下来一行 n 个正整数,第 i 个正整数为 wi。
接下来 m 行,每行代表一个操作。
输出格式
对于每个操作,输出相应的结果。
样例数据
样例输入
0
11 23 4
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
样例输出
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
子任务
一共 18 个测试集:
分数 测试集编号 k 的范围 特殊性质 6 1 k=0 AB 6 2 AC 6 3 A 5 4 B 5 5 C 5 6 6 7 k=1 AB 6 8 AC 6 9 A 5 10 B 5 11 C 5 12 6 13 k=8 AB 6 14 AC 7 15 A 5 16 B 5 17 C 5 18
特殊性质 A:link 与 cut 在其他操作之前。
特殊性质 B:没有操作 query2、操作 add1 与操作 add2。
特殊性质 C:没有操作 query2 与操作 add2。
1≤n≤50000;1≤m≤250000。
保证 link 和 cut 操作中的 w 满足 1≤w≤10000,所以关于边权的计算不会超出 32 位有符号整数范围。
保证初始的 wi 不超过 109,保证所有 add1 和 add2 操作中的 d 之和不超过 109。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
0
11 23 4
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
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