Codeforces Round #362 (Div. 2) C. Lorenzo Von Matterhorn（LCA思想）

题目链接：http://codeforces.com/contest/697/problem/C

【中文题意】给你一棵完全二叉树，第一层为 1，第二层从左到右为2，3。依次往下…….一共有n个操作，有两种操作。
第一种操作：1 u,v,w。将u到v之间的路径上的每一条边的值+w。
第二种操作：2 u,v。输出从u到v之间的路径上的边的权值和。
【思路分析】首先对于完全二叉树来说，1e18这个数据范围太大，如果构建一棵这样的二叉树，不仅时间上会超过限制，而且空间上也会超过限制。所以呢，我们没有必要把所有的结点都表示出来，只需用到哪个表示哪个即可。那么怎么更新路径和查找路径呢，更新路径的话类似我们查找两个结点的最近公共祖先，把结点的值存入map里面即可，另外一条边的权值可以加在一个点上面，因为要查找边肯定从点开始。
【AC代码】

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<algorithm>
using namespace std;
#define LL long long

map<LL,LL >ma;
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        ma.clear();
        int choice;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&choice);
            LL u,v,w;
            if(choice==1)
            {
                scanf("%lld %lld %lld",&u,&v,&w);
                while(u!=v)
                {
                    if(u>v)
                    {
                        ma[u]+=w;
                        u/=2;
                    }
                    else
                    {
                        ma[v]+=w;
                        v/=2;
                    }
                }
            }
            else
            {
                scanf("%lld%lld",&u,&v);
                LL re=0;
                while(u!=v)
                {
                    if(u>v)
                    {
                        re+=ma[u];
                        u/=2;
                    }
                    else
                    {
                        re+=ma[v];
                        v/=2;
                    }
                }
                printf("%lld\n",re);
            }
        }
    }
    return 0;
}