D Christmas Tree Un-decoration
First, consider the problem without updates. We can perform a DP on the tree. Define \(\mathrm{dp}(u)\) as the minimum number of operations to remove all ornaments in the subtree rooted at vertex \(u\). The transition is
\[\mathrm{dp}(u) = \max\left(a_u, \sum_{c \text{ child of } u} \mathrm{dp}(c)\right).\]Thus, the answer can be computed in \(O(n)\) time.
To handle updates, we use heavy-light decomposition. Define:
- \(b_u\): the sum of \(\mathrm{dp}(c)\) for all light children \(c\) of \(u\).
- \(h(u)\): the heavy child of \(u\).
The transition becomes \(\mathrm{dp}(u) = \max(a_u, b_u + \mathrm{dp}(h(u)))\).
Next, consider a chain in the heavy-light decomposition from its topmost vertex \(c_1\) to a leaf \(c_k\): \((c_1, c_2, \ldots, c_k)\). We have
\[\begin{aligned} \mathrm{dp}(c_1) &= \max(a_{c_1}, b_{c_1} + \mathrm{dp}(c_2)) \\ &= \max(a_{c_1}, b_{c_1} + a_{c_2}, b_{c_1} + b_{c_2} + \mathrm{dp}(c_3)) \\ &\;\;\vdots \\ &= \max_{i=1}^{k} \left(a_{c_i} + \sum_{j=1}^{i-1} b_{c_j}\right). \end{aligned}\]Note that the only important value we need to compute is \(\mathrm{dp}(c_1)\), since it either becomes the final answer (if \(c_1 = 1\)) or contributes to \(b_{p_{c_1}}\) (if \(c_1 \ne 1\)). Therefore, we can maintain each term inside the \(\max\) function above for each chain using a lazy segment tree.
To update the number of ornaments in vertex \(u_i\) to \(x_i\), we update \(a_{u_i}\) in \(u_i\)’s chain, then move up while updating the values of \(b\) for the chains’ roots’ parents. In this way, an update can be performed in \(O(\log^2 n)\) time.
Therefore, the problem has been solved in \(O(n \log n + q \log^2 n)\) time.