解説スライドの小課題 \(5\) の重心分解で満点解法を作れない理由は作用の可逆性がないことですが、仮に重心分解の過程を表す根付き木が二分木である場合は可逆性がなくても効率的に作用できます。

重心分解の各ステップで、新しく現れる部分木を Huffman coding の要領でマージし、その過程を組み合わせて二分木を構築します。 Huffman coding によって重み \(w\) の要素が数回マージされて重み \(W\) となるときに巻き込まれるマージは高々 \(a\log(W/w)+b\) 回（ \(a\) , \(b\) は定数）ですから、重心分解に Huffman coding を導入して構築される二分木の高さは高々 \(a\log(N)+b\log_2(N)\) です。

以上より、計算量 \(O(N \log N + Q \log N \log D)\) を達成できます。

解答例 ※実装の平易のため、長さ \(O(D)\) の BIT を \(O(N)\) 個構築します。