LCA最近公共祖先-- HDU 2586
2019-05-08 07:23:32来源:博客园 阅读 ()
题目链接
For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 lines each consisting three numbers i,j,k, separated by a single space, meaning that there is a road connecting house i and house j,with length k(0<k<=40000).The houses are labeled from 1 to n.
Next m lines each has distinct integers i and j, you are to answer the distance between house i and house j.
题意:有一棵有n个节点的树,每条边上有一个权值代表这两个点之间的距离,现在m次询问:从节点a到节点b的路径长?
思路:预处理所有节点到根节点(定为节点1)的距离,以及所有节点的祖先信息(fa[i][j]表示节点 i 向上距离为 (1<<j)的祖先节点编号),计算a和b到根节点的距离和,减去两倍的最近公共祖先的到根节点的距离值。
代码如下:
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; const int N = 4e4 + 5; int head[N], cnt; struct Edge { int to, next; int value; }e[2 * N]; struct Node { int fa[20]; int deep; int sum; bool state; }node[N]; void insert(int u, int v, int value) { e[++cnt].to = v; e[cnt].next = head[u]; e[cnt].value = value; head[u] = cnt; e[++cnt].to = u; e[cnt].next = head[v]; e[cnt].value = value; head[v] = cnt; } int cal(int x, int t) { for (int i = 0; i <= 19; i++) if (t&(1 << i)) x = node[x].fa[i]; return x; } void dfs(int x) { node[x].state = 1; for (int i = 1; i <= 19; i++) { if (node[x].deep<(1 << i))break; node[x].fa[i] = node[node[x].fa[i - 1]].fa[i-1];///倍增处理祖先信息 } for (int i = head[x]; i; i = e[i].next) { if (node[e[i].to].state) continue; node[e[i].to].deep = node[x].deep+ 1; node[e[i].to].fa[0] = x; node[e[i].to].sum = node[x].sum+e[i].value; dfs(e[i].to); } } int lca(int x, int y)///求lca { if (node[x].deep<node[y].deep) swap(x, y); x = cal(x, node[x].deep - node[y].deep); for (int i = 19; i >= 0; i--) if (node[x].fa[i] != node[y].fa[i]) { x = node[x].fa[i]; y = node[y].fa[i]; } if (x == y)return x; else return node[x].fa[0]; } void init() { cnt = 0; memset(head, 0, sizeof(head)); memset(node, 0, sizeof(node)); } int main() { int T; cin >> T; while (T--) { init(); int n, m; cin >> n >> m; for (int i = 0; i < n-1; i++) { int x, y, v; scanf("%d%d%d",&x,&y,&v); insert(x,y,v); } dfs(1); for (int i = 0; i < m; i++) { int x, y; scanf("%d%d",&x,&y); int pa = lca(x, y); int ans = node[x].sum - node[pa].sum + node[y].sum - node[pa].sum; cout << ans << endl; } } return 0; }
原文链接:https://www.cnblogs.com/chen9510/p/10809886.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 博弈--巴什博弈 2020-04-24
- 给定一个由 0 和 1 组成的矩阵,找出每个元素到最近的 0 的 2020-04-15
- 严格次小生成树 2020-03-08
- 结题报告 2020-03-07
- 树结构基础 2020-02-18
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash