【HDU 4547 CD操作】LCA问题 Tarjan算法

  • 时间:
  • 浏览:0
  • 来源:uu快3计划_uu快3官方_单双

思路:用Tarjan算法求LCA,补救查询需要分类讨论:

这道题还其他细节问题需要补救好:

2. 同HDU2586这道题,多个查询,注意记录查询序列号。这道题我用邻接表项query_id[r][i]记录节点r的第i个查询所持有的查询序列号,用邻接表项query_tar[r][i]记录节点r的第i个查询的目标节点。

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

  1. if tar == lca,则res(cur, tar) = depth(cur) - depth(lca); (饱含 tar == cur的情况报告)

1. 每个查询要记录好目标目录是谁。原困分析tarjan算法是批补救的,即每完成对两个 棵子树的遍历,补救其树根所涉及到的查询。为使查询补救不遗漏,亲们 把查询也以邻接表的形式存成双向边,然而每次补救需要知道本次查询原始的“单向边”,另两个 可不都都还可以根据上边的分类计算结果。统统有我另设了两个 数组ans_tar[i]记录第 i 个查询所给定的tar。

注意这里的cd命令是多样化版,只能进行如下四种 操作:

  1. cd   ..                                        //返回父目录

3. 给出的目录是字符串,要用两个 map<string, int>存储名称到节点号的映射关系。

  3. 其他,则res(cur, tar) = depth(cur) - depth(lca) + 1;

题意:模拟DOS下的cd命令,给出n个节点的目录树以及m次查询,每个查询饱含 两个 当前目录cur和两个 目标目录tar,返回从cur切换到tar所要使用的cd命令次数:

  2. else if cur == lca, 则res(cur, tar) = 1;

  2. cd   cur\一系列目录\tar                 //由当前目录跳转到目标目录,注意上边的“一系列目录”只能饱含 父目录..,也假如说,自底向上需要一步步走,而自顶向下可不都都还可以一步到位

 这里又了解到了map两个 用法,即对[]的重载:对于map<string, int> m,原困分析调用一次m[s],而s在m中不处在时,会自动插入s并将它的value置为0。你你是什么设计对于这道题很大慨,可不都都还可以维护全局计数变量seq_num,原困分析返回0搞笑的话,派发下两个 序号给它即可。