Official Editorial (Chinese)

Explanation

Naive Solution

We observe that any operation will only affect nodes of the same depth. Thus, instead of solving for all depths at once, we can take the sum of the minimum cost to fill in each depth.

Consider the set of nodes at depth $d$ relative to the root. Define $\texttt{dp}[v]$ as the minimum cost to fill in all vertices of depth $d$ in the subtree of $v$, only considering operations selecting vertices at $v$ or lower.

• If $v$ is of depth $d$ (relative to the root), then we must fill it in with cost $a_0$

• Otherwise, we can either select to incur a cost of $a_{d-\text{depth}[v]}$ by operating on $v$, or not operate on $v$ and instead solve for each subtree:

Our answer will be the sum of $\texttt{dp}[0]$ for each value of $d$, yielding a solution in $\mathcal{O}(n^2)$ time.

Virtual Tree Optimization

One observation we can make is for a long chain ending at $v$, we can process it quickly by taking

We will aim to leverage this fact. Define $S_d$ as the set of vertices at depth $d$, and take $S$ to be the virtual tree of $S_d$.

We continue in a similar fashion to previously, but we only compute dynamic programming values for nodes in $S$. The range minimum query can be answered using data structures in logarithmic or linear time.

Implementation

Time Complexity: $\mathcal{O}(N \log N)$

Copy
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr int MAX_N = 1e5 + 1;
constexpr int LG = 17;

int tin[MAX_N], tout[MAX_N], d[MAX_N], lift[MAX_N][LG], timer;
ll dp[MAX_N];