### PROBLEM LINKS

### DIFFICULTY

MEDIUM

### EXPLANATION

We present two important observations of the problem:

- The corresponding graph is a tree, because it is connected and has N-1 edges.
- After we move a chef from city a to city b, it is useless to move it to city a again.

Those observations make the problem possible to be solved using DP in tree. To simplify the DP, we first transform the tree into child-sibling representation rooted at node 1. Let DP(n, c, d) be the maximum profit achieved in the subtree rooted at the parent[n], with c chefs available in parent[n], and we are given d days remaining. The recurrence is given in this pseudocode:

DP(n, c, d) = max (

DP(sibling[n], c, d), // doesn’t transfer any chefs from parent[n] to n

max ({DP(child[n], rc, rd) + DP(sibling[n], c - rc, d - 1 - rd) : 1 <= rc <= c and 0 <= rd <= d - 1}) // transfers rc chefs to n and gives rd days

)

The base case is when n is null (sentinel node that is the sibling of the last sibling of a node). We can build a restaurant in parent[n] if c and d are positive, and also if S[parent[n]] is not negative. So, DP(n, c, d) = max(0, S[parent[n]]) if n is sentinel node and c and d are positive.

The solution to the problem is then available in DP(child1, C, D). We can then use all information in the DP table to reconstruct an optimal expansion plan.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.