SOLVE
LATER
You are given a binary tree rooted at 1. Initially, all the nodes of the tree have some initial values V_{i}. Wave operation is to be applied on the tree.
After applying the wave operation,
Value of each node in the tree = Sum of all initial values of nodes in its subtree.
You are required to add 1 more node with value X to the tree such that:
1. The tree remains binary after adding the node to the tree.
2. After applying the wave operation to this tree (the tree after adding node with value X), the sum of tree is minimum.
Sum of tree = sum of values of all nodes in the tree.
Print the minimum sum of the tree.
Input :
Output :
Constraints :
Tree after adding new node (say it 3):
Adding node 3 to root node and applying wave operation,
Value of node 1= 1+1+1= 3 (sum of initial value of nodes 1,2 and 3 as they form the subtree of node 1)
Value of node 2 = 1
Value of node 3 = 1
Sum of tree = 3+1+1 = 5 which is the minimum possible sum we can get.