JOI 王国由编号从
每个城市有一个定义好的危险等级。首都(城市
当前,城市
- 迁移:当时刻所有居住在危险等级为
的城市的海狸会迁移到危险等级为 的城市,该城市需满足从当前城市出发沿道路行进可达。保证 。根据 JOI 王国的结构,每只海狸的迁移目的地唯一确定。 - 迁入:由于王国外的迁入,城市
的海狸数量增加 。 - 调查: 调查当前时刻城市
居住的海狸数量。
作为 Bitaro 的下属,你发现无需实地考察即可根据迁移计划信息计算出每次调查事件时的海狸数量。
给定 JOI 王国的结构、各城市当前的海狸数量及迁移计划详情,请编写程序计算每次调查事件的结果。
输入格式
- (查询
) - (查询
) - (查询
)
每个(查询
输出格式
对于每个满足
样例一
input
4 1 1 2 1 3 4 3 6 3 1 1 1 0 3 1 3 2 1 2 1 3 2
output
1 8 0 3
explanation
初始时,城市
- 第
天发生调查事件。第一行输出 ,表示城市 的海狸数量。 - 第
天发生迁移事件。城市 和 的海狸全部迁移到城市 。第 天结束时,城市 , , , 分别有 , , , 只海狸。 - 第
天发生调查事件。第二行输出 。 - 第
天发生调查事件。第三行输出 。 - 第
天发生迁移事件。城市 的海狸全部迁移到城市 。第 天结束时,城市 , , , 分别有 , , , 只海狸。 - 第
天发生调查事件。第四行输出 。
该样例满足子任务
样例二
input
3 1 1 3 1 4 11 2 2 5 1 2 0 3 1 1 1 0 3 1 3 2 2 3 4 3 3 1 1 0 3 3 3 1
output
3 13 0 4 0 17
explanation
初始时,城市
- 第
天发生迁入事件。城市 的海狸数量增加 。第 天结束时,城市 , , 分别有 , , 只海狸。 - 第
天发生迁移事件。无海狸迁移,因为不存在危险等级为 的城市。 - 第
天发生调查事件。第一行输出 。 - 第
天发生迁移事件。城市 和 的海狸全部迁移到城市 。第 天结束时,城市 , , 分别有 , , 只海狸。 - 第
天发生调查事件。第二行输出 。 - 第
天发生调查事件。第三行输出 。 后续事件类似发生,此处省略具体描述。
该样例满足子任务
样例三
input
7 1 2 1 3 3 2 5 2 8 9 4 0 5 10 1 3 1 2 4 10 3 2 1 6 3 1 2 0 3 1 3 4 2 5 6 3 5 3 3
output
6 18 19 6 0
explanation
该样例满足子任务
数据范围
。 ( )。 ( )。 。 的取值为 , 或 ( )。- 若
,则 ( )。 - 若
,则 , ( )。 - 若
,则 ( )。 - 至少存在一个
( )满足 。 - 所有输入值为整数。
子任务
设城市最大危险等级为
: 。 : 。 : 。 :不存在 的查询,且最多有 个 的查询。 :最多有 个 的查询。 :不存在 的查询。 :无额外限制。