当前位置: 首页 > news >正文

lca(倍增)

例题:https://acm.hdu.edu.cn/showproblem.php?pid=2586

点击查看代码
#include <bits/stdc++.h>using namespace std;const int N = 40010;vector<int> v[N];
vector<int> w[N];int fa[N][31],cost[N][31],dep[N];
int n,m;
int a,b,c;void dfs(int root, int fno){fa[root][0] = fno;dep[root] = dep[fa[root][0]] + 1;for(int i = 1; i < 31; i ++){fa[root][i] = fa[fa[root][i - 1]][i - 1];cost[root][i] = cost[fa[root][i - 1]][i - 1] + cost[root][i - 1];}int sz = v[root].size();for(int i = 0; i < sz; i ++){if(v[root][i] == fno)continue;cost[v[root][i]][0] = w[root][i];dfs(v[root][i],root);}
}int lca(int x,int y){//令 y 比 x 深if(dep[x] > dep[y])swap(x,y);int tmp = dep[y] - dep[x];int ans = 0;for(int j = 0; tmp; j ++, tmp >>= 1){if(tmp & 1) ans += cost[y][j],y = fa[y][j];}if(x == y) return ans;for(int j = 30; j >=0 && y != x; j --){if(fa[x][j] != fa[y][j]){ans += cost[x][j] + cost[y][j];x = fa[x][j];y = fa[y][j];}}//x和y都在lca(x,y)前一步了ans += cost[x][0] + cost[y][0];return ans;
}void solve(){memset(fa,0,sizeof(fa));memset(cost,0,sizeof(cost));memset(dep,0,sizeof(dep));cin >> n >> m;for(int i = 1; i <= n; i ++){v[i].clear();w[i].clear();}for(int i = 1; i <= n - 1; i ++){cin >> a >> b >> c;v[a].push_back(b);v[b].push_back(a);w[a].push_back(c);w[b].push_back(c);}dfs(1,0);for(int i = 0; i < m; i ++){cin >> a >> b;cout << lca(a,b) << '\n';}
}int main(){ios::sync_with_stdio(0);cin.tie(0);int t;cin >> t;while(t --){solve();}return 0;
}
http://www.hskmm.com/?act=detail&tid=27937

相关文章:

  • [SpringCloud][7]负载均衡介绍,以及一些搭建
  • BERT模型简化技术提升效率与容量
  • 251010
  • Redis 64字节分界线与跳表实现原理 - 实践
  • 新手报道
  • VUE---await的运用
  • 供应链业务架构设计概览
  • VS Code保存.vue文件自动格式化标签的问题
  • 基于最小二乘(LS)信道估计的MATLAB实现
  • 让老弟做个数据同步,结果踩了 7 个大坑!
  • 2025焊接件加工制造厂家口碑最新推荐榜:实力工艺与市场口碑
  • 2025机械加工厂家实力排行榜:技术精度与供货效率权威测评
  • 2025 年最新推荐!依托优质运输网络的国际搬家海运公司排行榜:覆盖澳洲多地家具海运需求澳洲/悉尼/墨尔本/大型家具海运公司推荐
  • 完整教程:计算机环境、用户与系统变量
  • 2025耐磨轮胎厂家TOP5推荐:超强抓地力与持久耐用性深度
  • CF做题记录
  • 2025 年中国搬家服务公司最新推荐榜:聚焦海运移民家具运输等需求,精选优质企业实测解析国际/国际海运/国际移民/家具海运/回国搬家海运公司推荐
  • NVIDIA CUDA 镜像 Docker 容器化部署全流程
  • AI时代,程序员的核心竞争力:从“编码工匠”到“元问题架构师”的终极进化
  • 小雅
  • 易基因:JEM(IF10.6):单细胞转录组测序(scRNA-seq)揭示过敏性肺部疾病的调控网络|项目文章
  • Services.AddRazorPages解释
  • 2025 年金属线槽厂家最新推荐排行榜:涵盖不锈钢、铝合金、防火等多类型产品,助您精准挑选优质厂家企业
  • 02_通讯录实现
  • 2025 空气离合器生产厂家最新推荐榜:电网冲击缓解技术测评与可靠性排行,含单片多片机型及核心部件企业
  • 2025 气动离合器厂家最新推荐榜权威发布:聚焦博得 PLC 技术与新兴品牌降本优势多片式气动离合器/气动离合器电磁阀/气动离合器气缸/气动离合器摩擦片/单片式气动离合器厂家推荐
  • Unicode 编码解码工具类
  • 2025 木粉源头厂家最新推荐榜:全品类适配 / 稳定供应 / 技术赋能品牌权威解析,采购必看杂/刨花/木塑/化工/造纸/香/猫砂木粉厂家推荐
  • mergeGDS
  • 读书笔记