A connected unweighted undirected graph with N nodes and N-1 edges (tree) was given where each node were labled from 0 to N-1, Also a value K were given as well. Each node were having a value, given in an array, where ith index would tell the value of the ith Node where 0<=i<N. The tree was rooted at 0th Node. You need to collect points from all the node values. Points can be calculated from node values using any two of the given methods.

type 1: Go to a Node say x and collect array[x]-K to add it in points. type 2: Go to a Node x divide node value and all of it's subtree node's values by 2 permanently, then add the current node value post dividing (i.e. arr[x]/2) to points.

Calculate the maximum Points which can be collected by using any of the Types (In each node you can choose any type to collect points independently).

1<=N<=10^5 -10^5<=array[i]<=10^5 -10^9<=K<=10^9