Codeforces 697C Lorenzo Von Matterhorn 题解

题意

现有若干城市，编号为i的城市与编号为2*i和2*i+1的城市之间有双向路，刚开始所有路都是免费的，有q次操作，每一次可能是将从v到u的最短路（经过的路段最少）的每一个路段收费增加某个值，或者是求从v到u走最短路需要花费多少

思路

因为数据范围较大，所以要用map做个离散化，map[i]表示从i到i/2的路的花费，求最短路就是不断取v和u之中较大的除以2，直到两数相等就是它们的LCA，增加路段收费和求最短路收费都可以这么操作，前者是将前者的map值增加，后者是统计map值之和

代码

#include <cstdio>
#include <map>
using namespace std;
map<long long,long long> mp;
int main()
{
    int q,type;
    long long v,u,w,ans;
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d",&type);
        if(type==1)
        {
            scanf("%I64d%I64d%I64d",&v,&u,&w);
            while(v!=u)
            {
                if(v>u)
                {
                    mp[v]+=w;
                    v/=2;
                }
                else
                {
                    mp[u]+=w;
                    u/=2;
                }
            }
        }
        else
        {
            scanf("%I64d%I64d",&v,&u);
            ans=0;
            while(v!=u)
            {
                if(v>u)
                {
                    ans+=mp[v];
                    v/=2;
                }
                else
                {
                    ans+=mp[u];
                    u/=2;
                }
            }
            printf("%I64d\n",ans);
        }
    }
    return 0;
}