ARC083E. Bichrome Tree

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] dfs(0);

println("POSSIBLE");


return 0;


}

I find this editorial in Chinese helpful.

巴特西

ARC083E. Bichrome Tree

最新文章

热门文章