n 頂点 0 辺のグラフを生成します。

tree = EulerTourTree.new(n)

無向辺 (u, v) を追加します。

tree = EulerTourTree.new(n)
tree.add_edge(u, v)

実際にオイラーツアーします。

itinerary などが正しく構築されます。

tree = EulerTourTree.new(n)
tree.build
tree.build(root: 3)

根からのパスに現れる辺のコストの総和を求めるためのリストを返します。

zero には「総和」の単位元を渡してください。

リストの i 番目には時刻 i に訪れた頂点と、 時刻 i - 1 に訪れた頂点を結ぶ辺のコストが格納されています。 ただし、その辺が時刻 i 以前に訪問済みだった場合は、マイナス倍された値が格納されます。 また、時刻 0 と時刻 itinerary.size には zero が格納されます。

辺 (u, v) のコストが w 変更される場合は、 頂点 u, v のうち、 後に 訪れる方の頂点 bwd をとして、 このリストの @login[bwd] 番目を w に、@logout[bwd] 番目を -w にしてください。

tree = EulerTourTree.new(n)
tree.build
tree.edge_costs_on_root_path { |u, v| edge_cost[{u, v}] }

頂点 u と頂点 v の最小共通祖先を返します。

tree = EulerTourTree.new(n)
tree.build
tree.lca(u, v)

根からのパスに現れる頂点のコストの総和を求めるためのリストを返します。

リストの i 番目には時刻 i に訪れた頂点のコストが格納されています。 ただし、その頂点が時刻 i 以前に訪問済みだった場合は、マイナス倍された値が格納されます。

頂点 v のコストが w 変更される場合は、 このリストの @login[v] 番目を w に、それ以降で v が現れる時刻番目を -w にすると良いです。 （つまり、計算量がそこそこかかりそう？）

tree = EulerTourTree.new(n)
tree.build
tree.node_costs_on_root_path { |v| node_costs[v] }

根を x とする部分木の辺のコストの総和を求めるためのリストを返します。

zero には「総和」の単位元を渡してください。

リストの i 番目には時刻 i に訪れた頂点と、 時刻 i - 1 に訪れた頂点を結ぶ辺のコストが格納されています。 ただし、その辺が時刻 i 以前に訪問済みだった場合は zero が格納されます

無向辺 (u, v) のコストが w に変更される場合は、 頂点 u, v のうち、 後に 訪れる方の頂点を bwd として、 このリストの @login[bwd] 番目を w にすると良いです。

tree = EulerTourTree.new(n)
tree.build
edge_cost = Hash({Int32, Int32}, Int64).new
tree.subtree_edge_costs { |u, v| edge_cost[{u, v}] }

根を x とする部分木の頂点のコストの総和を求めるためのリストを返します。

zero には「総和」の単位元を渡してください。

リストの i 番目には時刻 i に訪れた頂点のコストが格納されています。 ただし、その頂点が時刻 i 以前に訪問済みだった場合は zero が格納されます。

頂点 v のコストが w 変更される場合は、 このリストの @login[v] 番目を w にすると良いです。

tree = EulerTourTree.new(n)
tree.build
node_cost = Array.new(n)
tree.subtree_node_costs { |v| node_costs[v] }

根から頂点 v へのパスに現れる辺のコストの総和を返します。

ブロックでは整数 l, r が与えられるので、 root_path_edge_costs の [l, r) までの総和を返してください。

tree = EulerTourTree.new(n)
tree.build
costs = tree.root_path_node_costs { |v| node_costs[v] }
csum = StaticRangeSum.new(costs)
tree.sum_edge_cost_on_path_to(v: 3) { |l, r| csum[l...r] }

根から頂点 v へのパスに現れる頂点のコストの総和を返します。

ブロックでは整数 l, r が与えられるので、 root_path_node_costs の [l, r) までの総和を返してください。

tree = EulerTourTree.new(n)
tree.build
costs = tree.root_path_node_costs { |v| node_costs[v] }
csum = StaticRangeSum.new(costs)
tree.sum_node_cost_on_path_to(v: 3) { |l, r| csum[l...r] }

根を subroot とする部分木の辺のコストの総和を返します。

ブロックでは整数 l, r が与えられるので、 subtree_edge_costs の [l, r) までの総和を返してください。

tree = EulerTourTree.new(n)
tree.build
edge_cost = Hash({Int32, Int32}, Int64).new
costs = tree.subtree_node_costs { |u, v| edge_cost[{u, v}] }
csum = StaticRangeSum.new(costs)
tree.sum_subtree_edge_cost(subroot: 3) { |l, r| csum[l...r] }

根を subroot とする部分木の頂点のコストの総和を返します。

ブロックでは整数 l, r が与えられるので、 subtree_node_costs の [l, r) までの総和を返してください。

tree = EulerTourTree.new(n)
tree.build
node_cost = Array.new(n)
costs = tree.subtree_node_costs { |v| node_costs[v] }
csum = StaticRangeSum.new(costs)
tree.sum_subtree_node_cost(subroot: 3) { |l, r| csum[l...r] }