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

  • 时间:
  • 浏览:1

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

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

 这里又了解到了map有两个用法,即对[]的重载:对于map<string, int> m,可能性调用一次m[s],而s在m中不居于时,会自动插入s并将它的value置为0。五种设计对于这道题很大概,还能不能 维护全局计数变量seq_num,可能性返回0励志的话 ,整理下有两个序号给它即可。

1. 每个查询要记录好目标目录是谁。可能性tarjan算法是批除理的,即每完成对有两个棵子树的遍历,除理其树根所涉及到的查询。为使查询除理不遗漏,让当当他们都 把查询也以邻接表的形式存成双向边,然而每次除理前要知道本次查询原始的“单向边”,曾经并能根据里面的分类计算结果。就是我另设了有两个数组ans_tar[i]记录第 i 个查询所给定的tar。

这道题还就是细节什么的问题前要除理好:

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

  1. if tar == lca,则res(cur, tar) = depth(cur) - depth(lca); (暗含tar == cur的状态)

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

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

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

注意这里的cd命令是多样化版,还能不能 了进行如下五种 操作:

思路:用Tarjan算法求LCA,除理查询前要分类讨论:

  2. cd   cur\一系列目录\tar                 //由当前目录跳转到目标目录,注意里面的“一系列目录”还能不能 了暗含父目录..,也就是说,自底向上前要一步步走,而自顶向下还能不能 一步到位

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