We are given a graph with n nodes.

For every pair of nodes i,j (i!=j) there is an edge from i to j and an edge from j to i. Note that both these edges may have different cost.

There is also a node S (source node). For every node i (i!=S) there is an edge from S to i. (No edge from i to S).

A wheel tree is a tree which has several linear chains connected to S. (meaning that every node except S has atmost one child.)

We are given an array D[i]. We have to construct a wheel tree from the given graph such that distance of ith node from S is <= D[i]. Distance is obviously the sum of edges.

Each chain connected to S is called a "spoke".

We have to remove some edges from the initial graph such that the distance conditions are satisfied ALSO we need to MINIMIZE the number of spokes.

I think this might be a flow problem. But am not able to solve it.

Any ideas?

EDIT:

contraints: N is <=40.

Any algorithm ( apart from brute :P )??

I have been studying link cut trees nowadays but don't seem to figure out how to find the kth ancestor of a particular node. Can this be done? If yes then how?