# Tree - how much elements have the subtree got?

It's the continuation of the exercise: https://cs.stackexchange.com/questions/65384/tree-elements-influence-on-another-elements-searching-for-specific-elements

I need to say how many elements do I have in specific subtrees.

Input: n - how many elements are in the tree, k - around how many elements should be in the subtree, and then I have got n-1 numbers p, which are saying who is the parent from the node. Node number is the number of the line.

Example Input:

11 4
1
1
2
2
2
3
7
3
9
9
1
/   \
2     3
/ | \   | \
4  5  6  7  9
|  | \
8  10 11


The question is: how many elements have got the subtree(1) and subtree(2). The subtree(2) should be also the subtree of subtree(1). Subtree(1) has got a number of elements which is greater than k, but the number of elements should be as near as possible to k. Subtree(2) should be the subtree of subtree(1) and its number of elements is equal or less than k, also it should be the as near as possible to k.

                    3
| \
7  9               subtree(1) - 6 elements >k
|  | \
8  10 11

9               subtree(2) - 3 elements <= k
| \
10 11


For the Example Input, the answer is: 6 - subtree(1) and 3 - subtree(2).

Why not the subtree which starts from 2? Because:

            2      It has got 4 elements <= k, so I must then take the whole
/ | \    tree which has got 11 elements >k. The subtree(1) has got
4  5  6   less elements - 6, where k = 4. 6-4 < 11-4.


Why not the subtree which starts from 7? Because:

        7     It has got 2 elements <= k, this is the subtree of
|     subtree(1), where k = 4. But beside we have got a subtree(2),
8     which has got 3 elements. 4-3 < 4-2.


• I can't understand the problem you're trying to solve. What do you mean when you say that $k$ is "around how many elements should be in the subtree"? What subtree? You haven't mentioned any subtree. How "around"? Also, talking about std::vector makes it sound like you're looking for coding help, which is off-topic, here. – David Richerby Nov 7 '16 at 20:28