#P6754. [2019山东冬令营]会议
[2019山东冬令营]会议
[2019山东冬令营]会议
题目描述
某单位及其下属单位共 个,编号为 到 ,第 个单位最初有 人。 号单位是最高单位;每个 的单位都有直属上级 ,这些关系组成一棵以 为根的树。
号单位要召开会议,各单位可以选择是否参加,但须满足:
- 号单位必须参加。
- 除 号单位外,一个单位只有在直属上级也参加时才能参加。
- 每个参加的单位必须派出恰好一人。
若两种方案的参会人员集合不同,就视为不同方案。因此,人数为 的单位无法参加。
现在有 条互不影响的人事变动消息。每条消息指定若干单位人数的临时变化,请分别计算该消息成立时的会议方案数,对 取模。
每次询问都以最初的人数为基础,未被本条消息提及的单位仍有 人;本次变动不影响后续询问。
输入格式
第一行两个整数 ,表示单位数和询问数。
第二行 个非负整数 。
第三行 个正整数 。
接下来 行,每行先给出一个非负整数 ,随后给出 对整数 ,表示本次询问中第 个单位的人数变为 。
同一次询问中的所有 互不相同。 表示没有单位的人数变化。
输出格式
输出 行,每行一个整数,表示相应询问的会议方案数对 取模的结果。
样例输入 1
3 1
1 2 3
1 1
0
样例输出 1
12
样例解释 1
单位 都不参加,有 种方案;只有单位 参加,有 种;只有单位 参加,有 种;两者都参加,有 种。因此共有 种方案。
样例输入 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
第二次询问中, 号单位人数为 ,无法派人参加,故答案为 。
原题另有下发文件中的第三组样例,当前附件未包含该样例文件。
数据范围
所有数据满足
$$1\le n\le3\times10^5,\qquad 1\le q\le10^5,\qquad 0\le k\le n,\qquad \sum k\le5\times10^5,$$以及 ,,。
- 的数据满足 。
- 的数据满足 (包含上述 )。
- 另外 的数据中, 在 到 中等概率随机生成。
- 另外 的数据满足每次询问 。