#P18436. Quake and Rebuild
Quake and Rebuild
Quake and Rebuild
Calamita 王国是一个经常遭受自然灾害的小国。居民把村庄与城镇建在王国中心的大榕树荫下。庞大的树根稳固着土地,人们也一直把它视为指引与庇护。
这棵大树是一棵根为节点 的有根树。对于每个节点 ,其父亲为 ,满足 ,两者之间有一条边。王国中会发生两类事件:地震和重建。
-
地震。 一场影响编号区间 、强度为 的地震,会将该区间内各节点的父亲编号减少 ,但最小为 。即同时更新
$$\forall i\in[l,r],\quad\mathrm{fa}'[i]=\max(1,\mathrm{fa}[i]-d).$$此后使用更新后的树结构。
-
重建。 为了在灾后恢复经济,居民选出了节点列表 作为新的贸易中心,并准备在若干节点上建设临时交通枢纽。两个贸易中心连通,当且仅当它们之间简单路径上的每一个节点都建有临时交通枢纽。居民只想建设使全部贸易中心连通所需的最少数量的枢纽。
随着时间推移,共有 个事件发生。请对每次重建求出所需临时交通枢纽的最少数量。
各次重建相互独立:上一轮重建的临时枢纽会关闭,若下一轮仍需要使用,就必须重新建设。贸易中心本身也属于必须建设的路径节点。
输入格式
第一行包含两个整数 (),分别表示节点数和事件数。
第二行包含 个整数,第 个整数为 ()。
接下来 行描述事件:
- 地震事件输入四个正整数
1 l r d,其中 ,。 - 重建事件先输入正整数
2 k,接着输入 个节点编号 ()。列表中可能有重复编号,将相同编号只保留一个即可。
保证所有重建事件的 之和不超过 。没有另外要求单次 ,重复编号仍计入此总和。
输出格式
对每次重建事件,输出一行一个正整数,表示使所有贸易中心连通所需的最少临时交通枢纽数。
地震事件不产生输出。若输入中没有重建事件,则不输出任何内容。不同贸易中心只有一个时,答案为 。
原样例
样例 1:
4 5
1 2 2
2 2 1 4
1 2 3 1
2 3 2 3 4
1 4 4 1
2 2 3 4
3
4
3
样例 2:
10 10
1 2 3 3 4 5 7 7 9
1 2 10 3
2 9 9 5 3 10 7 2 4 6 8
1 6 10 3
1 2 7 3
1 7 10 3
2 2 4 3
2 3 7 4 4
1 3 9 3
1 3 9 3
1 10 10 3
10
3
3