← 返回题目列表

Codeforces · 696/A

A. 洛伦佐·冯·马特宏峰

中文机器翻译题面 查看原题

巴尼住在纽约。纽约市有无数个从 1 开始编号的正整数交叉路口。对于每个正整数 i,在交叉路口 i 和 2i 之间存在一条双向道路,在 i 和 2i + 1 之间存在另一条道路。您可以清楚地看到,任意两个交叉点之间都存在唯一的最短路径。

最初任何人都可以免费通过任何道路。但由于 SlapsGiving 就在我们前面,很快就会有 q 个连续的事件发生。有两种类型的事件:

1. 政府制定新规则。规则可以用整数v、u和w表示。这一行动的结果是,从 u 到 v 的最短路径上所有道路的通行费增加了 w 美元。

2. 巴尼开始从某个十字路口 v 出发,前往十字路口 u,那里有一个他想拥抱的女孩(使用他的假名 Lorenzo Von Matterhorn)。他总是使用两个交叉路口之间的最短路径(访问最少数量的交叉路口或道路)。

政府需要你的计算。巴尼每次去抱女孩,你都需要告诉政府他应该付多少钱(他经过的所有道路的通行费之和)。

输入

输入的第一行包含单个整数 q (1 ≤ q ≤ 1 000)。

接下来的 q 行包含按时间顺序排列的事件信息。如果每个事件是政府制定新规则,将从 u 到 v 的最短路径上所有道路的通行费增加 w 美元,则用表格 1 v u w 描述;如果是 Barnie 从交叉路口 v 拥抱到交叉路口 u 的事件,则用表格 2 v u 描述。

每个描述行有 1 ≤ v、u ≤ 1018、v ≠ u、1 ≤ w ≤ 109 个状态。

输出

对于第二类型的每个事件,在一行中打印 Barney 在该事件中经过的所有道路的通行费总和。按相应事件的时间顺序打印答案。

示例

输入 #1

7
1 3 4 30
1 4 1 2
1 3 6 8
2 4 3
1 6 1 40
2 3 7
2 2 4

输出 #1

94
0
32

注意

在示例测试用例中:

以下是使用的交叉点:

1. 路径上的交叉点为 3、1、2 和 4。
2. 路径上的交叉点为 4、2 和 1。
3. 路径上的交叉点只有 3 个和 6 个。
4、路径上的交叉口为4、2、1、3。路径上的道路通行费依次为32、32、30。所以答案等于 32 + 32 + 30 = 94。
5. 路径上的交叉点为 6、3 和 1。
6.路径上的交叉口为3和7。它们之间的道路通行费为0。
7. 路径上的交叉口为 2 和 4。它们之间的道路通行费为 32(第一个事件增加 30,第二个事件增加 2)。