#P18436. Quake and Rebuild

Quake and Rebuild

Quake and Rebuild

Calamita 王国是一个经常遭受自然灾害的小国。居民把村庄与城镇建在王国中心的大榕树荫下。庞大的树根稳固着土地,人们也一直把它视为指引与庇护。

这棵大树是一棵根为节点 11 的有根树。对于每个节点 i>1i>1,其父亲为 fa[i]\mathrm{fa}[i],满足 1≤fa[i]<i1\le\mathrm{fa}[i]<i,两者之间有一条边。王国中会发生两类事件:地震和重建。

  1. 地震。 一场影响编号区间 [l,r][l,r]、强度为 dd 的地震,会将该区间内各节点的父亲编号减少 dd,但最小为 11。即同时更新

    $$\forall i\in[l,r],\quad\mathrm{fa}'[i]=\max(1,\mathrm{fa}[i]-d).$$

    此后使用更新后的树结构。

  2. 重建。 为了在灾后恢复经济,居民选出了节点列表 [b1,b2,…,bk][b_1,b_2,\ldots,b_k] 作为新的贸易中心,并准备在若干节点上建设临时交通枢纽。两个贸易中心连通,当且仅当它们之间简单路径上的每一个节点都建有临时交通枢纽。居民只想建设使全部贸易中心连通所需的最少数量的枢纽。

随着时间推移,共有 mm 个事件发生。请对每次重建求出所需临时交通枢纽的最少数量。

各次重建相互独立:上一轮重建的临时枢纽会关闭,若下一轮仍需要使用,就必须重新建设。贸易中心本身也属于必须建设的路径节点。

输入格式

第一行包含两个整数 n,mn,m(2≤n,m≤2×1052\le n,m\le2\times10^5),分别表示节点数和事件数。

第二行包含 n−1n-1 个整数,第 ii 个整数为 fa[i+1]\mathrm{fa}[i+1](1≤fa[i+1]<i+11\le\mathrm{fa}[i+1]<i+1)。

接下来 mm 行描述事件:

  • 地震事件输入四个正整数 1 l r d,其中 2≤l≤r≤n2\le l\le r\le n,1≤d≤n1\le d\le n。
  • 重建事件先输入正整数 2 k,接着输入 kk 个节点编号 b1,…,bkb_1,\ldots,b_k(1≤bi≤n1\le b_i\le n)。列表中可能有重复编号,将相同编号只保留一个即可。

保证所有重建事件的 kk 之和不超过 6×1056\times10^5。没有另外要求单次 k≤nk\le n,重复编号仍计入此总和。

输出格式

对每次重建事件,输出一行一个正整数,表示使所有贸易中心连通所需的最少临时交通枢纽数。

地震事件不产生输出。若输入中没有重建事件,则不输出任何内容。不同贸易中心只有一个时,答案为 11。

原样例

样例 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