#P6754. [2019山东冬令营]会议

    ID: 6574 传统题 1500ms 512MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>树算法虚树LCA排序与序列处理倍增贪心CF2600树形DP树的重心前缀和

[2019山东冬令营]会议

[2019山东冬令营]会议

题目描述

某单位及其下属单位共 nn 个,编号为 11 到 nn,第 ii 个单位最初有 aia_i 人。11 号单位是最高单位;每个 i>1i>1 的单位都有直属上级 fai\mathit{fa}_i,这些关系组成一棵以 11 为根的树。

11 号单位要召开会议,各单位可以选择是否参加,但须满足:

  • 11 号单位必须参加。
  • 除 11 号单位外,一个单位只有在直属上级也参加时才能参加。
  • 每个参加的单位必须派出恰好一人。

若两种方案的参会人员集合不同,就视为不同方案。因此,人数为 00 的单位无法参加。

现在有 qq 条互不影响的人事变动消息。每条消息指定若干单位人数的临时变化,请分别计算该消息成立时的会议方案数,对 109+710^9+7 取模。

每次询问都以最初的人数为基础,未被本条消息提及的单位仍有 aia_i 人;本次变动不影响后续询问。

输入格式

第一行两个整数 n,qn,q,表示单位数和询问数。

第二行 nn 个非负整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

第三行 n−1n-1 个正整数 fa2,fa3,…,fan\mathit{fa}_2,\mathit{fa}_3,\ldots,\mathit{fa}_n。

接下来 qq 行,每行先给出一个非负整数 kk,随后给出 kk 对整数 t1,p1,t2,p2,…,tk,pkt_1,p_1,t_2,p_2,\ldots,t_k,p_k,表示本次询问中第 tit_i 个单位的人数变为 pip_i。

同一次询问中的所有 tit_i 互不相同。k=0k=0 表示没有单位的人数变化。

输出格式

输出 qq 行,每行一个整数,表示相应询问的会议方案数对 109+710^9+7 取模的结果。

样例输入 1

3 1
1 2 3
1 1
0

样例输出 1

12

样例解释 1

单位 2,32,3 都不参加,有 11 种方案;只有单位 22 参加,有 22 种;只有单位 33 参加,有 33 种;两者都参加,有 66 种。因此共有 1+2+3+6=121+2+3+6=12 种方案。

样例输入 2

6 2
2 1 5 3 3 6
1 2 2 3 1
2 1 3 4 6
1 1 0

样例输出 2

3108
0

样例解释 2

第二次询问中,11 号单位人数为 00,无法派人参加,故答案为 00。

原题另有下发文件中的第三组样例,当前附件未包含该样例文件。

数据范围

所有数据满足

$$1\le n\le3\times10^5,\qquad 1\le q\le10^5,\qquad 0\le k\le n,\qquad \sum k\le5\times10^5,$$

以及 1≤ti≤n1\le t_i\le n,0≤ai,pi<109+70\le a_i,p_i<10^9+7,1≤fai<i1\le\mathit{fa}_i<i。

  • 10%10\% 的数据满足 n≤20, q≤10n\le20,\ q\le10。
  • 40%40\% 的数据满足 n≤1000, q≤1000n\le1000,\ q\le1000(包含上述 10%10\%)。
  • 另外 10%10\% 的数据中,fai\mathit{fa}_i 在 11 到 i−1i-1 中等概率随机生成。
  • 另外 20%20\% 的数据满足每次询问 k=1k=1。

原题面 PDF