首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【CodeForces 697C】Lorenzo Von Matterhorn(LCA)

【CodeForces 697C】Lorenzo Von Matterhorn(LCA)

作者头像
饶文津
发布2020-06-02 15:45:32
3920
发布2020-06-02 15:45:32
举报
文章被收录于专栏:饶文津的专栏饶文津的专栏

Least Common Ancestors

节点范围是1~1e18,至多1000次询问。

只要不断让深的节点退一层(>>1)就能到达LCA。

用点来存边权,用map储存节点和父亲连边的权值。

#include<cstdio>
#include<map>
#define ll long long
using namespace std;
map<ll,ll>m;
ll u,v,w;
void add(){
    while(u!=v){
        if(u<v){
            m[v]+=w;
            v>>=1;
        }
        else{
            m[u]+=w;
            u>>=1;
        }
    }
}
ll query(){
    ll ans=0;
    while(u!=v){
        if(u<v){
            ans+=m[v];
            v>>=1;
        }else{
            ans+=m[u];
            u>>=1;
        }
    }
    return ans;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int op;
        scanf("%d",&op);
        if(op==1){
            scanf("%lld%lld%lld",&u,&v,&w);
            add();
        }else{
            scanf("%lld%lld",&u,&v);
            printf("%lld\n",query());
        }
    }
}
  
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2016-08-04 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档