【HDU 2586 How far away?】LCA问题 Tarjan算法

  • 时间:
  • 浏览:0
  • 来源:大发5分11选5_大发5分11选5官网

具体实现上,都要记录以前几条信息:每个节点的高度depth、邻接表G、访问标记vis。

对于每组查询(u, v)时,可用这些 公式得到结果res(u, v) = depth(u) - depth(lca(u,v)) + depth(v) - depth(lca(u,v))。

注意Tarjan算法是脱机的(离线的)、批解决的,即其查询结果的生成顺序与最初的查询输入顺序无关。而且 都要将乱序生成的结果合理组织以实现顺序输出。这些 点我那末想好为社 会 做,下面的实现是参照了到网上他人的代码。具体法律妙招 而且:用这些 记录查询目标节点的法律妙招 去记录查询序号,即query[r][i]存的是第r个节点的第i个查询所涉及的目标节点,这些 地,num[r][i]存的是第r个节点的第i个查询在输入查询序列中的序号。再附加五个多多 ans[i]存储第i条查询的结果。以前每解决五个多多 查询,即可把结果存入ans[num[r][i]] = res(r, i)

p.s 注意题目描述:那末说节点的序号分布在1...n,而他们都歌词 的vis, query, depth等数组都有以下标标识节点号访问的。所以 每次初始化时注意覆盖到整个区间[1, MAX_N]。这题n<=10000都有很大,若超过数组能开的最大长度,则都要“离散化”。

数据范围:n [2, 10000], m[1, 100]

思路:Tarjan算法:dfs遍历每个点,每遍历完 r 的五个多多 孩子 c, 把 c 并入以 r 为祖先的集合,并解决 c 的所有查询 q:若qi的目标节点 v 已被遍历到,那末一定有lca(c, v) = find(v)。

还有这些 而且,这些 什么的什么的问题 我希望使用高度优先遍历策略,左根右五个多多 节点的访问顺序是那末关系的。而且 可不都要借助先序遍历先访问根节点的便利,先修改vis数组,后遍历其邻接表,从而解决因邻接表存了双向边而跳出“兜圈子”的具体情况。

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2586

题意:给出一棵n个节点的无根树,每条边有每个人 的权值。给出m个查询,对于每条查询返回节点u到v的最短路径的权值和,按查询顺序输出结果。