Hints: Dynamic Values And Maximum Sum

Fix a root of the tree. For each non-leaf $u$, the statement sends its current value to a single leaf in its subtree: among leaves of maximum depth from $u$, pick the smallest-index leaf. Leaves keep their own values until possibly receiving from ancestors.

What do you need to precompute for every node $u$ downward in one DFS when the tree is rooted at $1$?

Answer to Hint 1: For each $u$, compute the leaf downLeaf[u] at maximum distance below $u$ (tie-break smallest leaf index) and the distance downDist[u]. For leaves, downLeaf[u]=u, downDist[u]=0; for internal nodes, merge candidates from children (keep two best by $(\text{dist}, -\text{leaf})$ logic as in relaxBest).

To reroot the tree at a child $v$, you must know where the parent’s mass would go if $v$’s subtree were removed—i.e.\ the farthest leaf from the parent not in $v$’s subtree. How can you compute parentToChildLeaf[v] for every child using the top-two candidates (mx1, mx2) at each node?

Answer to Hint 3: At each node $u$, keep the two best downward candidates $(\text{dist}, \text{leaf}, \text{child src})$; for child $v$, the best leaf outside $v$’s subtree is the better of the global best not coming from $v$ (use mx2 when mx1 came from $v$) together with the upward candidate through the parent. A second DFS fills upDist/upLeaf and sets parentToChildLeaf[v] to the chosen leaf for routing from the parent when entering $v$.

With the tree fixed at root $1$, how do you initialize one aggregate value per leaf from the initial $a[u]$ and the `downLeaf[u]$ routing?

Answer to Hint 4: For every $u \ge 2$, add $a[u]$ to leafSum[leafId[downLeaf[u]]] where leafId maps leaf vertices to $0..L-1$. The root’s value is handled when you score a[u] + ds.query() at vertex $u$.

While you walk the tree and virtually change which vertex behaves like the root of the operation, what should TopKSum(k-1) track over the buckets leafSum?

Answer to Hint 5: TopKSum maintains the sum of the largest $(k-1)$ values among current leafSum buckets (or all if fewer). Intuitively, after fixing which vertex acts as the root of an operation, the remaining $(k-1)$ operations contribute the best possible totals drawn from the other leaves’ aggregated values—formalized by the multiset in the solution.

Answer to Hint 6: During an Euler/DFS walk, when you move from parent $p$ to child $v$, the routing destinations change: subtract $a[v]$ from the bucket of downLeaf[v] (remove $v$’s contribution under the old routing), and add $a[p]$ to the bucket of parentToChildLeaf[v] (the parent’s mass now follows the edge into $v$’s side). Recurse; undo both changes when backtracking.

Why evaluate answer = max(answer, a[u] + ds.query()) before recursing to children at $u$?

Answer to Hint 7: That update runs at the entry snapshot for $u$: it corresponds to choosing $u$ as the root of the operation while leafSum already reflects all routing updates along the path from the global root $1$—matching the model’s idx == 0 hook before pushing children.

How does TopKSum support insertValue / eraseValue in $O(\log n)$ while keeping the sum of the $(k-1)$ largest bucket values?

Answer to Hint 9: Keep two multisets: big holds the $(k-1)$ largest values seen (when $K>0$), small holds the rest; on insert, possibly evict the smallest from big to small; on erase, pull the largest from small into big if needed. query() returns sumBig.

Answer to Hint 10: After the full traversal, print the maximum of a[u] + ds.query() over all $u$ visited at entry time. (A full optimality proof matches the reference solution’s aggregation of the $k$ operations.)

Answer to Hint 11: Map leaves to ids, build leafSum and TopKSum, run the iterative DFS with modifyLeaf on enter/exit; handle $n=1$ as a leaf. Complexity $O(n \log n)$ from multiset updates along the walk.