cf 697 C

链接：http://codeforces.com/problemset/problem/697/C

  每次操作都查找两点的最近的公共祖先，查找的同时更新路径权值或者求最短路径代价

#include <bits/stdc++.h>
using namespace std;
#define ll long long

map<pair<ll,ll>,ll>m;


int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        ll ty,u,v,w;
        scanf("%I64d",&ty);
        if(ty==1)
        {
            scanf("%I64d%I64d%I64d",&u,&v,&w);
            if(v<u)swap(u,v);
            while(v!=u)
            {
                if(v>u)
                {
                    m[{v,v/2}]+=w;
                    m[{v/2,v}]+=w;
                    v/=2;
                }
                else if(u>v)
                {
                    m[{u,u/2}]+=w;
                    m[{u/2,u}]+=w;
                    u/=2;
                }
            }
        }
        else
        {
            ll sum=0;
            scanf("%I64d%I64d",&u,&v);
            if(v<u)swap(u,v);
            while(v!=u)
            {
                if(v>u)
                {
                    sum+=m[{v,v/2}];
                    v/=2;
                }
                else if(u>v)
                {
                    sum+=m[{u,u/2}];
                    u/=2;
                }
            }
            printf("%I64d\n",sum);
        }
    }

    return 0;
}