各頂点に全順序モノイドが載っている木を考える。2種類のクエリがある。一点更新クエリ。頂点 v を始点とする有向パスのモノイドの総積について重み最小となるものを答えるクエリ。

x を動かしたときのモノイドの重み最小のパス a → b → x はパス b → x の重みを最小化することで得られる。
頂点 v を更新したときにモノイドの重み最小となる根からのパス r → x のモノイドの候補が O(F(n)) で更新できる。F は優加法的とする。

このとき2種のクエリが HLD と重心分解により O(log(n)^2 + log(n)F(n)) で処理できる。
パス P の列から可換モノイドへの準同型写像 f がある。n 頂点 r-根付木について f(Π_{r ∈V(P)}P) が O(W(n)) で求まるとする。W が優加法的ならば重心分解により O(W(n log n)) で f(Π P) が求まる。