パッケージ library

クラス Tree.LowestCommonAncestor

java.lang.Object

library.Tree.LowestCommonAncestor

含まれているクラス:

Tree

private static class Tree.LowestCommonAncestor
extends java.lang.Object

最小共通祖先

根付き木の二つの頂点の内，どちらの祖先でもありなおかつ最も近い（最も根から遠い）頂点を返す． 内部でセグ木を使う． 構築がO(n log n)，クエリがO(log n)

木は辞書を用いた隣接リストで渡す．

ネストされたクラスの概要

ネストされたクラス

修飾子とタイプ	クラス	説明
private static class	Tree.LowestCommonAncestor.Node
private static class	Tree.LowestCommonAncestor.SegmentTree<T>

フィールドの概要

フィールド

修飾子とタイプ	フィールド	説明
private int[]	id
private Tree.LowestCommonAncestor.SegmentTree<Tree.LowestCommonAncestor.Node>	segmentTree

コンストラクタの概要

コンストラクタ

コンストラクタ	説明
LowestCommonAncestor(java.util.Map<java.lang.Integer,java.util.List<java.lang.Integer>> tree, int root, int numOfNodes)

メソッドの概要

修飾子とタイプ	メソッド	説明
private void	dfs(int current, java.util.Map<java.lang.Integer,java.util.List<java.lang.Integer>> tree, java.util.List<Tree.LowestCommonAncestor.Node> list, int[] id, int depth)
(package private) int	getLCA(int nodeA, int nodeB)	二つの頂点の最小共通祖先の頂点番号を返す．

クラスから継承されたメソッド java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

フィールドの詳細

segmentTree

private final Tree.LowestCommonAncestor.SegmentTree<Tree.LowestCommonAncestor.Node> segmentTree

id

private final int[] id

コンストラクタの詳細

LowestCommonAncestor

LowestCommonAncestor(java.util.Map<java.lang.Integer,java.util.List<java.lang.Integer>> tree,
                     int root,
                     int numOfNodes)

パラメータ:

tree - 木．各頂点が子の頂点を持つ隣接リスト．

root - 根の番号

numOfNodes - 木に含まれる頂点の個数

メソッドの詳細

getLCA

int getLCA(int nodeA,
           int nodeB)

二つの頂点の最小共通祖先の頂点番号を返す．

パラメータ:

nodeA - 頂点A

nodeB - 頂点B

戻り値:

最小共通祖先の頂点番号

dfs

private void dfs(int current,
                 java.util.Map<java.lang.Integer,java.util.List<java.lang.Integer>> tree,
                 java.util.List<Tree.LowestCommonAncestor.Node> list,
                 int[] id,
                 int depth)