A viable configuration of the given tree can be divided into two trees, each consists of vertices of the same color (if we compress edges and add a dummy root node when needed). Let's call them $T_B$ and $T_W$, respectively. Note that $T_B$ and $T_W$ are independent of each other with respect to satisfying the conditions. For each vertex $u$ in $T_A$, it must hold that the total weight of $u$'s proper descendants is no more than $X_u$, and in that case it is always possible make the total weight of vertices in subtree $u$ be $X_u$ by setting $u$'s weight appropriately. The same can be said for $T_B$. Ideally, we can configure the given tree such that in each subtree $u$, the total weight of vertices with a different color than $u$ are minimized.
Official editorial:
The hard part of this problem is to understand the highlighted sentence.
code
int main() { int n; scan(n); vv
g(n); rng (i, 1, n) { int p; scan(p); g[p - 1].pb(i); } vi x(n); scan(x); vi dp(n); function dfs = [&](int u) { vi f(x[u] + 1, INT_MAX); f[0] = 0; FOR (v, g[u]) { dfs(v); down (i, x[u], 0) { if (f[i] != INT_MAX) { int t = f[i]; f[i] = INT_MAX; if (i + x[v] <= x[u]) { chkmin(f[i + x[v]], t + dp[v]); } if (i + dp[v] <= x[u]) { chkmin(f[i + dp[v]], t + x[v]); } } } dp[u] = *min_element(all(f)); if (dp[u] == INT_MAX) { println("IMPOSSIBLE"); exit(0); } } }; dfs(0);
println("POSSIBLE");
return 0;
}
I find this editorial in Chinese helpful.