CF Round362div2 C

文章目录

1. 1. 题意
2. 2. 分析

原题

题意

给你一个二叉树，任意两点之间双向可达，有两个操作：

1.将任意两点之间的做短路径上面所有路的权值全部加w。
2.询问任意两点之间最短距离值为多少。

分析

因为是二叉树，所以最短距离就是两个点之间的最近公共祖先到两个点的距离之和。数据范围非常大，但是我们发现是路径上所有路的权值整体加一个值，所以每次O(logn)复杂度的更新单路，查询也是从下往上加就可以了。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
map<ll,ll> h;
int main(){

    ll p,u,v,w,oby,ans;
    while(scanf("%I64d",&p)!=EOF){
        while(p--){
            scanf("%I64d",&oby);
            if(oby==1){
                scanf("%I64d%I64d%I64d",&v,&u,&w);
                while(u!=v){
                    if(u>v){
                        h[u]+=w;
                        u>>=1;
                    }
                    else{
                        h[v]+=w;
                        v>>=1;
                    }
                }
            }
            else{
                ans=0;
                scanf("%I64d%I64d",&v,&u);
                while (u!=v){
                    if(u>v){
                        ans+=h[u];
                        u>>=1;
                    }
                    else{
                        ans+=h[v];
                        v>>=1;
                    }
                }
                printf("%I64d\n",ans);
            }
        }
    }
    return 0;
}