algorithm - ルートのないツリーで複数の LCA を見つける

Question

ルートのないツリーに LCA を実装しようとしています。ツリー (循環のない接続された無向グラフ) と、いくつかのルートと 2 つの頂点に対する LCA に関する一連のクエリを指定しました。特定のクエリごとにルートが異なる可能性があるため、最初に任意のルートのツリーを前処理するアルゴリズムを使用することはできません。

これまでのところ、DFS を使用して両方の頂点からルートへのパスを見つけようとしましたが、分岐する場所を確認しましたが、やや遅い (O(nq)、q はクエリの数)。

クエリの準線形複雑性を持たせるためにツリーを前処理する方法について何か提案はありますか?

Answer 1

ルート u に関する v と w の LCA を LCA(u, v, w) とします。LCA(u, v, w) を計算するには、任意の固定 r に対して、

LCA(r, u, v)
LCA(r, u, w)
LCA(r, v, w)

そして、「奇数」を取り出します。つまり、2 つが等しく、3 番目が異なる場合、3 番目を取り出します。そうでない場合、それらはすべて等しいので、そのノードを取ります。

Answer 2

ルートとして任意の頂点を取り、LCA のためにツリーを前処理します。すべてのクエリ (u,v) と r をルートとして、w をツリー内の u と v の LCA とします。

• w が r のサブツリーにある場合、w が答えです。
• r が w のサブツリーにある場合、r が答えです。
• r が u または v のサブツリーにある場合、対応する頂点が答えになります。