概要 頂点の木の各頂点にモノイド の元 が乗っているとして、指定されたパス上の値の総積を計算するクエリが、前計算 、クエリ で処理できる。 アルゴリズム 重心分解を行う。 木の重心を とし、各 に対して、 パスから を除いたものに対するクエリ結果を計…