Christmas Tree Un-decoration

Research checked: I used the official ICPC APAC analysis PDF and an independent traP Static Top Tree writeup. Both point to the same intended core: subtree DP, HLD, and function composition. Public accepted-submission pages were not reliably indexed quickly, so those two were the useful evidence.

Fixed Tree

Let $dp[u]$ be the minimum number of operations needed to clear the subtree rooted at $u$, if we view an operation as choosing a descendant of $u$ and removing one ornament along that downward path.

For a node $u$, there are two lower bounds:

• Every child subtree $c$ needs $dp[c]$ operations with endpoints inside that child subtree. One operation cannot go into two different child subtrees, so these add up to $\sum_c dp[c]$.
• Vertex $u$ itself needs at least $a_u$ operations passing through or ending at $u$.

So $dp[u] \ge \max(a_u, \sum_c dp[c])$.

This bound is also achievable. Run optimal plans for all child subtrees. Let their total count be $S=\sum_c dp[c]$. If $S<a_u$, add $a_u-S$ operations ending exactly at $u$. If $S>a_u$, the extra passes through an already-empty $u$ are harmless because the operation removes one ornament only if there is one left. That gives

$dp[u]=\max\left(a_u,\sum_{c \text{ child of } u} dp[c]\right).$

The false assumption to kill here is that child answers should be maximized. They should be summed. Branches do not share endpoint operations; Christmas magic is not a data structure.

Making Updates Fast

Choose a heavy child $h[u]$ for every non-leaf vertex using standard HLD by subtree size. Define

$light[u]=\sum_{c\ne h[u]} dp[c],$

where the sum is over light children only. Then

$dp[u]=\max(a_u, light[u]+dp[h[u]]),$

with $dp[h[u]]=0$ if $u$ has no heavy child.

Now define a function for each vertex:

$f_u(x)=\max(a_u, light[u]+x).$

Along one heavy chain $v_1,v_2,\ldots,v_k$ from top to bottom,

$dp[v_1]=(f_{v_1}\circ f_{v_2}\circ\cdots\circ f_{v_k})(0).$

Each function has the form $f(x)=\max(A,x+B)$. This form is closed under composition. If

$f(x)=\max(A_f,x+B_f),\qquad g(x)=\max(A_g,x+B_g),$

then

$(f\circ g)(x)=\max(A_f,A_g+B_f,x+B_g+B_f).$

So the composed function is represented by

$(\max(A_f,A_g+B_f),\;B_f+B_g).$

Store all vertex functions in HLD order in a segment tree. A heavy chain is contiguous, so a range query gives the chain composition, and evaluating it at $0$ gives the $dp$ value of the chain top.

Processing An Update

When $a_v$ changes:

1. Update the function stored at $v$.
2. Let $t=top[v]$. Recompute $dp[t]$ by querying the segment tree over that whole heavy chain.
3. If $t$ has parent $p$, then $t$ is a light child of $p$, so update $light[p]$ by the delta in $dp[t]$.
4. Now the function at $p$ changed, so continue from $p$.

Each climb crosses one light edge. In HLD, going upward across light edges at least doubles the subtree size, so this happens only $O(\log n)$ times. Each step does one point update and one range query on the segment tree, both $O(\log n)$.

Complexity

Preprocessing is $O(n)$. Each query is $O(\log^2 n)$. Memory is $O(n)$.

The implementation avoids recursive DFS. Since $p_i<i$, every descendant has a larger index, so subtree sizes and initial DP values can be computed by scanning vertices backwards. That avoids stack overflow on a chain, which is a deeply uncool way to lose a tree problem.