各頂点 \(i\) について、その頂点を根とする部分木を \(R_i \) とし、\(S_i=\sum_{v \in R_i} (A_{v}-C_{v})\) とおきます。

全ての \(i\) について \(0 \le S_i\) となることが、全ての目標を同時に達成するための必要十分条件となっています。

木をheavy light decompositionします。heavy light decompositionによってできたpathに適当に順番付けをし、\(i\) 個目のpath \(P_i\) に対して \(X_i=\min_{v \in P_i}(S_v)\) と置きます。

いま、\(0 \le \min_{i}(X_i)\) となることが、全ての目標を同時に達成するための必要十分条件となっています。

ここで、値 \(C_x\) を変更したとします。このとき \(S_v\) に変更のある頂点 \(v\) は \(C_x\) の先祖のみとなっており、したがって \(X_i\) に変更のある添え字 \(i\) は \(O(logN)\) 個 となっています。

各pathについて遅延セグ木を持っておくことで、それぞれのpathについて \(X_i\) の値を \(O(logN)\) で更新することができるため、\(X_i\) の値を全てmultiset等で保管しておくことで、\(\min_{i}(X_i)\) の値を高速に更新することができます。

時間計算量は \(O(NlogN+Q(logN)^2)\) です。