Lorenzo Von Matterhorn（map的用法）

http://www.cnblogs.com/a2985812043/p/7224574.html

解法:这是网上看到的

因为要计算u->v的权值之和，我们可以把权值放在v中，由于题目中给定的u、v特性，我们可以从最后一个v开始倒回来每次除以2，然后把权值加起来就好了，注意输入的区间大小值

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <map>
 4 using namespace std;
 5 #define LL long long
 6 map<LL, LL>node;
 7 int q, com;
 8 LL u, v, w;
 9 int main()
10 {
11     while(~scanf("%d", &q)){
12         while(q--){
13             scanf("%d", &com);
14             if(com==1){
15                 scanf("%lld%lld%lld", &u, &v, &w);
16                 while(u!=v){
17                     if(u>v){
18                         node[u]+=w;
19                         u/=2;
20                     }
21                     else{
22                         node[v]+=w;
23                         v/=2;
24                     }
25                 }
26             }
27             else{
28                 scanf("%lld%lld", &u, &v);
29                 LL ans=0;
30                 while(u!=v){
31                     if(u>v){
32                         ans+=node[u];
33                         u/=2;
34                     }
35                     else{
36                         ans+=node[v];
37                         v/=2;
38                     }
39                 }
40                 printf("%lld\n", ans);
41             }
42         }
43     }
44     return 0;
45 }

 

http://www.cnblogs.com/fightfordream/p/5672915.html

 

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <iostream>
 5 #include <map>
 6 using namespace std;
 7 #define N 10005
 8 map<long long,long long> mp;
 9 
10 void add(long long a,long long w)
11 {
12     if(mp.find(a)==mp.end()) mp[a]=0;
13     mp[a]+=w;
14 }
15 
16 long long val(long long a)
17 {
18     if(mp.find(a)==mp.end()) return 0;
19     return mp[a];
20 }
21 
22 int main()
23 {
24     int t;
25     cin>>t;
26     while(t--){
27         int s;
28         cin>>s;
29         if(s==1){
30             long long u,v,w;
31             cin>>u>>v>>w;
32             while(u!=v){
33                 //对节点进行更新，直到更新到根节点
34                 if(u>v){
35                     add(u,w);
36                     u>>=1;
37                 }
38                 else{
39                     add(v,w);
40                     v>>=1;
41                 }
42             }
43         }
44         else{
45             long long u,v,ans=0;
46             cin>>u>>v;
47             while(v!=u){
48                 //查询
49                 if(u>v){
50                     ans+=val(u);
51                     u>>=1;
52                 }
53                 else{
54                     ans+=val(v);
55                     v>>=1;
56                 }
57             }
58             cout<<ans<<endl;
59         }
60     }
61     return 0;
62 }