木を HL 分解して分解したパスごとに行列の積を計算する Segment Tree を用意する. 行列は辺の子の方にもたせる.

これだけなのだが, 行列の掛け算, SegmentTree, HL 分解と実装が重い.