标题真长。。。
HDU 2586 How far away ?——树上节点最短距离,LCA, 双亲表示法+暴力从下至上追溯,孩子链表示法+(Tarjan 或 欧拉环游RMQ+(ST 或 SegmentTree))
http://acm.hdu.edu.cn/showproblem.php?pid=2586
四种解法:
- 双亲表示法+暴力从下至上追溯
- 孩子链表示法+Tarjan
- 孩子链表示法+欧拉环游RMQ+ST
- 孩子链表示法+欧拉环游RMQ+SegmentTree
对于建树的问题,要解决父节点和子节点的问题:
- 第一种解法中,双亲表示法,用一个一维数组houses来储存所有节点,houses[x].fa表示该节点的父节点,当两个子树被合并造成冲突时,将其中一棵树倒置
如:
1 2
↑ ↑
3 4
↑ ↑
5 6
此时要连接3和4,必定会造成冲突,因为,若将3作为4的父节点(3 → 4),4就会有两个父节点,于是把4 ← 6这一支倒置成 4 → 6
于是:
1 2
↑ ↑
3 → 4
↑ ↓
5 6
(5成为合并以后的根元素)
- 剩下三种解法则利用孩子链表示法,记录所有与目标节点相连接的节点(包括一个父节点和一个子节点),然后随便选取一个节点作为父节点,用dfs遍历这些连接的节点,同时用visited数组来跳过其中的父节点
解法1:
1 | #include <iostream> |
解法2:
1 | #include <iostream> |
解法3:
1 | #include <iostream> |
解法4:
1 | #include <iostream> |