Hi,
as I understand, this is a problem on dynamic programming. I see only one solution - go through the whole tree and compute the values for each node from the leaves up to the root of the tree.
And on each level the full search should be done. For example, if we want to compute value for a node with p childs with already computed x_1, x_2, .., x_p values, then try 1/p, 2/p, ... p/p as a possible solution for this node.

please, give me any hint on this problem.

Edited by author 29.03.2011 20:27

Try to think about how the answer for every node (and for the whole tree) depends on x?

Use dichitomy (binary search), Luke!

ОK, what answer to this test:
106 10
1 1
1 5
1 5
1 5
1 5
2 1
...
2 1 (70 times: 2 1)
2 100
...
2 100 (30 times: 2 100)

The answer is 80.0000000, but I think, it's incorrect a little bit. Because it is said in the condition "the king needs as many soldiers as possible". If x = 80, then the king will have only 4 soldiers, while if x = 70, the king will have 74 soldiers. So I thought binary search doesn't work there, i.e. the numebr of soldiers is more important, than the total time of preparing to the war (the only thing is necessary is the total time should be not greater than max allowed time). But it's not true. The most important is to maximize the percent in the answer.