#P16025. [Lot2017]Meow

[Lot2017]Meow

题目描述

信息学俱乐部里出现了一只新的宝可梦 Meow2。Meow2 喜欢树,因此它有一棵带根树,共有 NN 个节点,编号为 00 到 N−1N-1。

节点 00 是根。对于任意非根节点,它的父亲节点编号都严格小于它。每个节点 ii 初始有一个自然数标签 SiS_i,满足 1≤Si≤L1\le S_i\le L。

Meow2 想知道,在这棵初始树上,序列

1,2,…,L1,2,\ldots,L

作为“向下子序列”出现了多少次。

形式化地说,它关心有多少个节点序列

A0,A1,…,AL−1A_0,A_1,\ldots,A_{L-1}

满足:

  • 节点 AiA_i 的标签为 i+1i+1;
  • 对每个 0≤i<L−10\le i<L-1,节点 AiA_i 是节点 Ai+1A_{i+1} 的祖先,祖先不要求是直接父亲。

Meow2 正在不断进化,因此它会逐步修改树上节点的标签。它有一个长度为 QQ 的魔法修改序列 PP。在第 ii 次修改,0≤i<Q0\le i<Q,它会把节点

i mod Ni\bmod N

的标签改为 PiP_i,其中 1≤Pi≤L1\le P_i\le L。一次修改会对之后的所有步骤继续生效。

Meow2 想知道,每次修改之后,序列 1,2,…,L1,2,\ldots,L 作为“向下子序列”出现了多少次。设第 ii 次修改后的答案为 ansians_i,其中 0≤i<Q0\le i<Q。你需要输出:

$$O=\left(1\cdot ans_0+2\cdot ans_1+\cdots+Q\cdot ans_{Q-1}\right)\bmod (10^9+7).$$

输入格式

第一行包含三个自然数 N,L,QN,L,Q,含义如题所述。

第二行包含 N−1N-1 个整数,记为 F1,F2,…,FN−1F_1,F_2,\ldots,F_{N-1},其中 FiF_i 表示节点 ii 的父亲。

第三行包含长度为 NN 的序列 SS,表示各节点的初始标签。

接下来 QQ 行,每行一个整数,依次构成修改序列 PP。第 ii 行修改会把节点 i mod Ni\bmod N 的标签改为对应的 PiP_i。

输出格式

包含一个整数,表示题目要求的 OO,对 109+710^9+7 取模。

数据范围与约定

  • 1≤N≤1000001\le N\le 100000;
  • 1≤L≤N1\le L\le N;
  • 对任意 ii,0≤Fi<i0\le F_i<i;
  • 对任意 ii,1≤Pi,Si≤L1\le P_i,S_i\le L;
  • 1≤Q≤2000001\le Q\le 200000。

子任务:

分值 限制
20 N≤200, L≤30, Q≤400N\le 200,\ L\le 30,\ Q\le 400
50 N≤5000, L≤300, Q≤5000N\le 5000,\ L\le 300,\ Q\le 5000
100 原始限制

样例

输入

6 2 6
0 1 0 3 0
1 2 1 2 1 2
2
1
2
1
2
1

输出

29

解释

在初始树中,序列 1,21,2 出现 33 次。

但是在各次修改之后,答案依次为:

0,0,1,1,2,2.0,0,1,1,2,2.

所以最终输出:

$$1\cdot0+2\cdot0+3\cdot1+4\cdot1+5\cdot2+6\cdot2=29.$$