n 個の頂点を持つツリーが与えられます。すべてのノードには整数の重みが関連付けられています。指定されたツリーには膨大な数のクエリ (~n^2) があります。A、B がツリーの 2 つの頂点であるクエリ (A、B) の場合、A と B を含む、A から B への一意のパス上のノードの重みの合計を計算する必要があります。
個々のクエリに対して dfs/bfs を実行できますが、クエリごとに O(n) 未満のより良いものを提案できますか?
ありがとう..
n 個の頂点を持つツリーが与えられます。すべてのノードには整数の重みが関連付けられています。指定されたツリーには膨大な数のクエリ (~n^2) があります。A、B がツリーの 2 つの頂点であるクエリ (A、B) の場合、A と B を含む、A から B への一意のパス上のノードの重みの合計を計算する必要があります。
個々のクエリに対して dfs/bfs を実行できますが、クエリごとに O(n) 未満のより良いものを提案できますか?
ありがとう..