 # RESTEXP - Editorial

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.

//