#P18253. Master of Both VI
Master of Both VI
Master of Both VI
这是“Master of Both”系列的第六题,这次的故事自然与海克斯科技有关。
为了夺取海克斯飞门并完成他的光荣进化,Viktor 正在进攻皮尔特沃夫。城市有 个路口,由 条双向道路连接,任意两个路口之间都能互相到达。也就是说,这些路口和道路构成一棵树。
Viktor 用海克斯射线攻击城市,Jayce 则发明了海克斯护盾。每次攻击有一个伤害值,每个护盾有一个生命值。伤害值为 的攻击命中当前生命值为 的护盾后,护盾生命值变成 。当生命值小于或等于 时,护盾被摧毁。
护盾受到攻击时,可以选择过载,将本次伤害减半。因此实际伤害可能不是整数;例如伤害为 的攻击,减半后造成 点伤害。同一个护盾不能在它连续受到的两次攻击中都使用过载。 这里的连续指该护盾实际受到的攻击;对其他路口的攻击不会重置这个限制。
Jayce 在路口部署了许多护盾。一个护盾部署后,将承受所有针对该路口的攻击。接下来有 个事件,按照输入顺序依次发生:
- A x y z:Viktor 发射一条海克斯射线,对从路口 到路口 的最短路径上的所有路口造成伤害 。路径包含两个端点; 时只攻击该路口。
- D x h:Jayce 在路口 检测到一个尚未被摧毁的护盾。由于战场混乱,他忘了这个护盾是什么时候部署的,只记得其初始生命值是 。请计算,在此前的攻击事件中,这个护盾最多可能承受过多少次攻击。
护盾可以部署在不同的时刻,也可以选择合法的过载时机。检测时它的生命值必须仍严格大于 。每次检测只要求回答这个最大次数。请帮助 Jayce 完成所有计算。
输入格式
第一行包含两个整数 ,分别表示路口数和事件数。
接下来 行,每行包含两个整数 ,表示路口 之间有一条双向道路。保证这些道路构成一棵树。
接下来 行,每行描述一个事件:
- 攻击事件的格式为 A x y z;
- 检测事件的格式为 D x h。
输出格式
对于每个检测事件,按照出现顺序输出一行一个整数,表示答案。
数据范围
- ;
- ;
- 道路端点和事件中的路口编号均在 内;
- 对每个攻击事件,;
- 对每个检测事件,。
输入只有一组数据。事件序列可以不包含攻击,也可以不包含检测;没有检测事件时不需要输出任何整数。
样例
5 7
1 2
1 3
2 4
2 5
A 1 4 2
A 3 5 2
D 1 4
D 2 3
D 2 1
A 5 5 10
D 5 100
2
1
0
2