cf#362-C. Lorenzo Von Matterhorn

http://codeforces.com/contest/697/problem/C

给你一个完全二叉树

两个操作

1： u,v,w 把u到v上的路都加w权值

2：u,v  查询u到v的权值和

uv最多1e18，log一下也就是60层左右

那么直接用map模拟即可

mp[i]表示的是 i到其父亲的这条路的权值

类似倍增算法模拟一下即可

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iostream>
using namespace std;

const double pi=acos(-1.0);
double eps=0.000001;


map<long long,long long>mp;
int main()
{

     int q;cin>>q;
     long long  op,u,v,w;
     for (int i=1;i<=q;i++)
     {
         scanf("%lld",&op);
         if (op==1)
         {
             scanf("%lld%lld%lld",&u,&v,&w);
             while(u!=v)
             {
                 if (u>v)
                     mp[u]+=w,u/=2;
                 else
                     mp[v]+=w,v/=2;
             }
         }
         else
         {
             scanf("%lld%lld",&u,&v);
             long long ans=0;
             while(u!=v)
             {
                 if (u>v)
                    ans+=mp[u],u/=2;
                 else ans+=mp[v],v/=2;
             }
             printf("%lld\n",ans);
         }
     } 
    return 0;

}