Training Material

Dynamic programming on trees→Catering Contracts Version 2π (IOITC 2008)

A new government has come to power after the elections in Siruseri and has promptly announced that it is reassigning all catering contracts on its rail network.

As is well known, the rail network of Siruseri is organized so that every station is connected to every other station by a unique path. The new scheme requires contractors to bid for a group of K stations at a time. However, the constraint is that all K stations that a contractor bids for must form a connected portion of the network. Having announced this, the government is now scratching its head to figure out how many different combinations of stations contractors can bid for.

For example, suppose the rail network is as given below, and contractors have to bid for 3 stations at a time. Then, there are six possible combinations, namely {1,2,3}, {1,2,5}, {2,3,5}, {2,4,5}, {2,5,6} and {4,5,6}. A combination such as {1,2,4}, for instance, is not permitted because these three stations are not all connected to each other.

```       3                      4
\                  /
2---------------5
/                  \
1                      6
```

You will be given a description of the rail network and the number of stations that a contractor has to bid for. You have to compute the number of different combinations of stations that the contractor can legally bid for, following the rule stipulated by the government.

Solution