Issue Description A tree with N nodes rooted at 1 is given to you. Each node in the tree has a special number Se associated with it. Additionally, each node has a certain Power. The power of each node in the tree is defined as the count of heavy nodes in the subtree of that node (including the node itself). In this context, a heavy node is one for which the sum of divisors of its special number is a multiple of 3. You have been provided with Q queries.
There are two types of queries:
- Type 1: Update special number of a node.
- Type 2: Determine the power of a specific node.
Input Format
First line: Two space-separated integers N and Q denoting the number of nodes in the tree and the number of queries respectively. Each of the next N-1 lines: Two space-separated integers U and V indicating an edge between them. Next line: N space-separated integers where i-th integer denotes the special number related to node i. First integer in the next Q lines is T (the type of query). If T is 1, it is followed by 2 integers X and Y representing the update of special number S of node X to Y. If T is 2, it is followed by a single integer X.
Output Format
For each query of type 2, output the power of the given node X. Each answer for a query should be displayed on a new line.
Explanation of the Problem Statement Essentially, we are dealing with a tree structure with numbered nodes (Si) and possibly some children nodes due to the tree's nature.
The problem requires us to calculate the "Power" of a node, where power is determined by counting the number of "heavy nodes" within its children.
A "heavy node" is defined as a node whose sum of its divisors for Si is divisible by 3.
Various computations that need to be conducted include:
- Identifying all child nodes for a given node.
- Determining the divisors for each child node's number.
- Summing up the divisors and checking if they are multiples of 3.
Given Sample Input and Outputs:
Sample input
5 5
1 2
1 3
3 4
3 5
16 8 17 3 18
2 1
2 3
1 3 7
2 1
2 3
Sample output:
3
2
2
1
The code I attempted:
function BinarySearchTree() {
this.root = null;
}
BinarySearchTree.prototype.insertNode = function (val) {
var node = {
data : val,
left : null,
right : null
};
var currentNode;
if (!this.root) {
this.root = node;
} else {
currentNode = this.root;
while (currentNode) {
if (val < currentNode.data) {
if (!currentNode.left) {
currentNode.left = node;
break;
} else {
currentNode = currentNode.left;
}
} else if (val > currentNode.data) {
if (!currentNode.right) {
currentNode.right = node;
break;
} else {
currentNode = currentNode.right;
}
} else {
break;
}
}
}
};
var BST = new BinarySearchTree();
BST.insertNode(16);
BST.insertNode(8);
BST.insertNode(17);
BST.insertNode(3);
BST.insertNode(18);
console.log(BST);
My Output:
BinarySearchTree {
root:
{ data: 16,
left: { data: 8, left: [Object], right: null },
right: { data: 17, left: null, right: [Object] } } }
Now, I wish to convert this data into an array [16, 8, 17, 3, 18]
and find the divisors for each node, checking whether the divisors are divisible by 3 or not. How can I approach this?
Is my current approach correct?