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.
Given a tree with N vertices, and 1 ≤ K ≤ N, we want to find the number of connected subgraphs of K vertices. Clearly every such subgraph will also be a tree.
We root the given tree arbitrarily and use dynamic programming. For every vertex v and 1 ≤ a ≤ K, we compute the number of subtrees of size a whose "topmost" vertex (vertex closest to the root of the original tree) is v. Let's say this quantity is C(v,a).
A subtree rooted at v with a vertices could have its remaining a-1 vertices distributed across the subtrees rooted at the children of v in any way. v could have a large number of children, so we cannot enumerate all such possibilities. Instead, we do a further DP on the children of v which will tell us D(v,a) for all a.
Suppose v has c children. Order them arbitrarily. Let D(r,b) be number of ways of using the first r children to use b vertices. More precisely, D(r,b) is the number of ways of choosing for each of the first r children either a subtree rooted at that child, or nothing, such that a total of b vertices are used (for all 0≤r≤c and 0≤b≤K-1). Note that this DP is specific to calculating C(v, everything), but we write D(r,b) for simplicity instead of D(v,r,b). After having calculated D, we have C(v,a) = D(c, a-1) for all 1≤a≤K.
For the base case, we have D(0,0) = 1 and D(0,x) = 0 for all other x. For calculating D(r,b) with r > 0, we look at all possible ways of splitting b into the first r-1 children, and the rth child. So
D(r,b) = sumi, 0≤ i ≤ b D(r-1,i) × C(rth child, b-i)
For a particular v with c children, this takes O(cK2) time. Overall, the algorithm takes O(NK2) time.
©IARCS 2012–2016
Pěstujeme web | visit: Skluzavky