題干：

巴尼住在NYC。NYC具有從1開始的正整數編號的無數個交叉點。在交叉點?i?和?2i?之間以及?i和?2i?+?1?之間存在雙向道路，對任意整數?i?都滿足。在任意兩點之間都有且只有一條最短路。

?

最初任何人都可以通過任何道路免費。 但是后來發生了 q 個事件。 有兩種類型的事件:

1. 政府制定新規。 一個規則可以用三個整數表示?v,?u?和?w。經過這次操作，點?u?到點?v?路徑上的所有點增加?w?元路費。

2. 巴尼從點?v?通過最短路移動到點?u。

現巴尼想知道，他的每一次移動需要花多少錢

Input

第一行包含一個整數?q?(1?≤?q?≤?1?000).

之后?q?行，每行包含一個事件。加路費的事件都被描述成?1?v?u?w?，代表將點?u?到點?v?路徑上所有點路費增加?w?元。移動的事件都被描述成?2?v?u，表示巴尼從點?v?走到點?u.

1?≤?v,?u?≤?1018,?v?≠?u,?1?≤?w?≤?109。

Output

對于第二類的每個事件，打印Barney在此事件中通過的所有道路的通行費的總和，一行。 以相應事件的時間順序打印答案。

Example

Input

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

Output

94 0 32

Note

In the example testcase:

Here are the intersections used:

?

Intersections on the path are?3,?1,?2?and?4.

Intersections on the path are?4,?2?and?1.

Intersections on the path are only?3?and?6.

Intersections on the path are?4,?2,?1?and?3. Passing fee of roads on the path are?32,?32?and?30?in order. So answer equals to?32?+?32?+?30?=?94.

Intersections on the path are?6,?3?and?1.

Intersections on the path are?3?and?7. Passing fee of the road between them is?0.

Intersections on the path are?2?and?4. Passing fee of the road between them is?32?(increased by?30?in the first event and by?2?in the second).

解題報告：

? ?注意到i,2i與 i,2i+1的搭配，考慮二叉樹。因為最大的值是1e18，所以層數一定不會很多（最多也就60層吧？）所以對于更新和查詢均可以暴力。用點權代表他和父節點的邊權，一維map就可以解決。（二維map也可以，但是因為孩子節點的父節點是唯一的，所以孩子節點就可以當做這條邊的特征元）

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; map<ll,ll> mp; void add(ll u,ll v,ll w) {while(u!=v) {if(u>v) mp[u] += w,u /= 2;else mp[v] += w,v /= 2;} } ll sum(ll u,ll v) {ll res = 0;while(u!=v) {if(u>v) res += mp[u],u /= 2;else res += mp[v],v /= 2;}return res; } int main() {int q,op;ll u,v,w;cin>>q;while(q--) {scanf("%d",&op);if(op == 1) {scanf("%lld%lld%lld",&u,&v,&w);add(u,v,w);}else {scanf("%lld%lld",&u,&v);printf("%lld\n",sum(u,v));}}return 0 ; }

?

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【CodeForces - 697C】Lorenzo Von Matterhorn（二叉树，思维）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。