#P18253. Master of Both VI

Master of Both VI

Master of Both VI

这是“Master of Both”系列的第六题,这次的故事自然与海克斯科技有关。

为了夺取海克斯飞门并完成他的光荣进化,Viktor 正在进攻皮尔特沃夫。城市有 nn 个路口,由 n−1n-1 条双向道路连接,任意两个路口之间都能互相到达。也就是说,这些路口和道路构成一棵树。

Viktor 用海克斯射线攻击城市,Jayce 则发明了海克斯护盾。每次攻击有一个伤害值,每个护盾有一个生命值。伤害值为 aa 的攻击命中当前生命值为 bb 的护盾后,护盾生命值变成 b−ab-a。当生命值小于或等于 00 时,护盾被摧毁。

护盾受到攻击时,可以选择过载,将本次伤害减半。因此实际伤害可能不是整数;例如伤害为 33 的攻击,减半后造成 1.51.5 点伤害。同一个护盾不能在它连续受到的两次攻击中都使用过载。 这里的连续指该护盾实际受到的攻击;对其他路口的攻击不会重置这个限制。

Jayce 在路口部署了许多护盾。一个护盾部署后,将承受所有针对该路口的攻击。接下来有 qq 个事件,按照输入顺序依次发生:

  • A x y z:Viktor 发射一条海克斯射线,对从路口 xx 到路口 yy 的最短路径上的所有路口造成伤害 zz。路径包含两个端点;x=yx=y 时只攻击该路口。
  • D x h:Jayce 在路口 xx 检测到一个尚未被摧毁的护盾。由于战场混乱,他忘了这个护盾是什么时候部署的,只记得其初始生命值是 hh。请计算,在此前的攻击事件中,这个护盾最多可能承受过多少次攻击。

护盾可以部署在不同的时刻,也可以选择合法的过载时机。检测时它的生命值必须仍严格大于 00。每次检测只要求回答这个最大次数。请帮助 Jayce 完成所有计算。

输入格式

第一行包含两个整数 n,qn,q,分别表示路口数和事件数。

接下来 n−1n-1 行,每行包含两个整数 u,vu,v,表示路口 u,vu,v 之间有一条双向道路。保证这些道路构成一棵树。

接下来 qq 行,每行描述一个事件:

  • 攻击事件的格式为 A x y z;
  • 检测事件的格式为 D x h。

输出格式

对于每个检测事件,按照出现顺序输出一行一个整数,表示答案。

数据范围

  • 1≤n≤5×1051\le n\le5\times10^5;
  • 1≤q≤3×1051\le q\le3\times10^5;
  • 道路端点和事件中的路口编号均在 [1,n][1,n] 内;
  • 对每个攻击事件,1≤z≤3701\le z\le370;
  • 对每个检测事件,1≤h≤1091\le h\le10^9。

输入只有一组数据。事件序列可以不包含攻击,也可以不包含检测;没有检测事件时不需要输出任何整数。

样例

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