Indian Computing Olympiad

Dynamic programming on trees→Catering contracts

We have a railway network with no cycles with expected profit at each station. Contractors bid for a subset of stations to maximize profit. A caterer may not bid for two adjacent stations. What is the best way to pick the stations?

For instance, here is a network:

       10                    20
         \                  /
          30--------------40
         /                  \
       20                    30
      

In this case, the best choice are the outer four nodes with value 10+20+20+30 = 80.

We know the network is a tree. How can we use this fact to evaluate the best profit?

We root the network at some station to get a tree. For a vertex v, let T(v) denote the subtree rooted at v and P(v) denote the maximum profit in the stations in T(v).

  P(v) = max {    Sum        P(w),          // we exclude v
              w child of v

                  Sum        P(w) + V(v)    // we include v
             w grandhild of v
             }
      

An alternative formulation

  P1(v) = max in T(v) including v
  P2(v) = max in T(v) excluding v


  P1(v) = V(v) +     Sum        P2(w)
                 w child of v

  P2(v) =      Sum        max(P1(w),P2(w))
           w child of v
      

The second formulation more explicitly captures the case when we include and exclude v and is probably clearer in terms of understanding the structure of the problem.

How do we program this? We can a dfs like computation.

Version 1: With global arrays:

  eval(v){  /* updates global arrays P1 and P2 */

     Mark v as visited;

     P1[v] = V(v);  /* Initialize both values */
     P2[v] = 0;

     if (v is a leaf){ return; }

     for all unvisited neighbours w of v {
        eval(w);
        P1[v] += P2[w];
        P2[v] += max(P1[w],P2[w]);
     }
  }
      

Version 2: Each call to eval returns pair (P1(v),P2(v)).

  eval(v){  /* returns ((P1(v),P2(v)) */

     Mark v as visited;

     if (v is a leaf){ return(V(v),0); }

     for all unvisited neighbours w of v {
        (p1,p2) = eval(w);
        myp1 += p2;
        myp2 += max(p1,p2);
     }

     return(p1+V(v),p2);
  }
      

---