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.
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 was thinking about:
- Storing all the childrens, indirect and direct childrens, for example, that the node 3 has got 5 childrens, node 9 has got 2 childrens. But I think it's quite slow if I would get the max number n = 500000, and all of the nodes would have got 1 direct parent, that would be probably too slow.
- Making a normal tree data structure with std::vector, but I don't have any further idea to this.