We have a network of sensors organized in tree form, where the sensors occupy the nodes. Most of the time the sensors are turned off, until the root sensor wakes up the rest of the sensors. This process of awakening the nodes requires a certain amount of time since, in a unit of time, a sensor can awaken only one of its children. Obviously, the total wake-up time for all sensors depends on the order in which each sensor wakes up your children.
It is asked to design an efficient algorithm that gives a sorting of the children of each node in the tree providing the minimum time to wake up all the sensors.
The solution must use dynamic programming.
I have got no clue where to start from; I know dynamic programming exercises are based on suboptimal structure and overlapping problems, and in this case, at least, overlapping problems is quite obvious since the tree structure is used.
Have you got any clue about the underlying recurrence? -- I am not asking you the solution since those are my homework :)