#P18572. Mafia and Candies
Mafia and Candies
Mafia and Candies
某个王国有 座城市,编号为 ,其中城市 是首都。王国恰有 条双向道路,所有城市都能通过这些道路到达首都。因此,道路构成一棵树。
王国的每座城市中都有黑手党团伙。城市 中最初恰有 名黑手党成员。你是一位糖果商人,会不时把糖果从一座城市运往另一座城市,但经营过程中会发生以下事情。
- 每当装有糖果的车到达城市 ,当地团伙就会抢走糖果,尽可能地在全部成员之间均分。不能均分的剩余糖果留给车夫。也就是说,若车到达时有 颗糖果,离开该城市时就剩下 颗糖果。
- 相邻城市的团伙可能发生冲突,导致连接它们的道路被毁。与首都断开的连通块中会出现混乱:其中每座城市的团伙都会增加一些成员。随后,国王会修建一条新路,从仍与首都连通的一座指定城市,连接到被毁道路中与首都断开的那个端点,恢复整个王国的连通性。
- 团伙的宣传或国王的清剿可能改变一座城市的团伙人数;此时人数会被直接设为指定值。
你已经提前得知所有这些事件。对每次从城市 运送 颗糖果到城市 的运输,你想知道最终能送到顾客手中的糖果数。
输入格式
第一行包含两个整数 (,),分别表示城市数和事件数。
第二行包含 个整数 (),表示各座城市最初的黑手党人数。
接下来 行描述道路,每行包含两个整数 (),表示城市 之间有一条道路。保证这些道路构成一棵有 个顶点的树。
接下来 行按时间顺序描述事件。每行的第一个整数为 。
- 若 ,该行格式为
1 u v x,其中 ,。把一车 颗糖果从 运往 。车辆按照从 到 的方向经过当前树上的简单路径,路径上的每座城市都会抢夺一次,包括起点 和终点 。运输不改变团伙人数;即使糖果数变成 ,这次运输的最终结果也是 。 - 若 ,该行格式为
2 x y z d,其中 ,。先毁掉城市 之间的道路,使王国分成两个连通块。在不包含首都的连通块中,每座城市的团伙人数都增加 。随后,从城市 向 中位于这个断开连通块内的那个端点修建新道路。 - 若 ,该行格式为
3 i y,其中 ,。把城市 的团伙人数设为 。
对每个第二类事件,保证当时城市 之间确有道路,并且该道路被毁后,城市 仍能到达首都。
注意,第二类事件中的增加可能让实际团伙人数超过初始人数的上界 。输入只有这一组树和事件,不含测试组数。
输出格式
对每个第一类事件,输出一行一个整数,表示从 运到 后剩余的糖果数。
对每个第二类事件,输出一行一个整数,表示人数增加之后、新道路修建之前,与首都断开的那个连通块内的团伙人数总和。
第三类事件不输出任何内容。
样例
输入
4 11
5 6 2 5
1 2
4 2
2 3
1 4 4 7
1 3 4 5
1 4 3 5
3 4 4
1 2 4 11
1 2 4 9
2 4 2 3 3
1 2 4 9
2 3 4 1 0
1 2 4 9
1 2 4 11
输出
2
1
0
1
3
7
1
7
3
0