Codeforces Round #362 Lorenzo Von Matterhorn

题目链接：http://codeforces.com/problemset/problem/696/A

题意：给我们一个二叉树，一开始每条边的权值都是0，现在给我们两个操作，第一个是讲从点u到点v这条路上的每一条边边权都加上w，第二个操作是询问我们从u到v这条路上的权值和。

很显然，如果我们能用一个二维数组来存储两两之间的关系的话，那么问题会非常简单，但是很明显我们是开不出10^18次方的数组的，所以这里我们用一个神奇的map来代替二维数组，map<LL, map<LL,LL> >，这样的map就和二维数组用起来没什么区别。

#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
map<LL, map<LL,LL> > Map;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
LL op,u,v,w,ans;
scanf("%I64d%I64d%I64d", &op, &u, &v);
if(op == 1)
{
scanf("%I64d", &w);
while(u != v)
{
if(u > v)
{
Map[u/2][u] += w;
u /= 2;
}
else
{
Map[v/2][v] += w;
v /= 2;
}
}
}
else
{
ans = 0;
while(u != v)
{
if(u > v)
{
ans += Map[u/2][u];
u /= 2;
}
else
{
ans += Map[v/2][v];
v /= 2;
}
}
cout << ans << endl;
}
}
}