頂点 \(p_j\) を根とする部分木に含まれる頂点の数 \(s_{p_j}\) をあらかじめ計算しておく.

そうすることで, クエリごとに全頂点のコストは \(x_j s_{p_j}\) 増えることになる.