Python to CPP

[STD8C542]

I have a code snippet of tree in python but I can't change it to C++ so I need help here

 def max_profit(node):
    return max(-X, node.value + sum(map(max_profit, node.children)))

[keskiverto]

What does that code do?

(Assume that we know nothing about Python. Explain your algorithm in language-independent manner.)

[helios]

int Node::max_profit() const{
    int sum = this->value;
    for (auto &child : this->children)
        sum += child->max_profit();
    return std::max(-X, sum);
}

[STD8C542]

Node is structure in my code as

struct node 
{ 
	int key; 
	vector<node *>child; 
}; 

so the error is saying

error: no ‘int node::max_profit()’ member function declared in class ‘node’
int node::max_profit(){

[keskiverto]

Declare the missing member:

struct node 
{ 
	int key; 
	vector<node *> child;
	int max_profit() const;
};

[STD8C542]

its giving the following error

prog.cpp:53:5: error: prototype for ‘int node::max_profit()’ does not match any in class ‘node’
int node::max_profit(){
^~~~
prog.cpp:11:6: error: candidate is: int node::max_profit() const
int max_profit() const;
^~~~~~~~~~

1st error in the max_profit() function and 2nd error in the node structure

[keskiverto]

Do you spot a difference between these?

int node::max_profit()
int node::max_profit() const

Do you know its meaning?
https://en.cppreference.com/w/cpp/language/member_functions#const-.2C_volatile-.2C_and_ref-qualified_member_functions
https://www.learncpp.com/cpp-tutorial/810-const-class-objects-and-member-functions/

Const correctness is a good thing:
https://isocpp.org/wiki/faq/const-correctness

[STD8C542]

thanks i got it!

but the max_profit() function which @helios converted to cpp is giving the wrong answer and different answer for same input

Here's the full code of the question https://www.codechef.com/APRIL19B/problems/SUBREM

// CPP program to do level order traversal 
// of a generic tree 
#include <bits/stdc++.h> 
using namespace std; 

// Represents a node of an n-ary tree 
struct node 
{ 
	int key; 
	vector<node *>child;
	int max_profit() const;
}; 
int x;
// Utility function to create a new tree node 
node *newNode(int key) 
{ 
	node *temp = new node; 
	temp->key = key; 
	return temp; 
} 

// Prints the n-ary tree level wise 
void LevelOrderTraversal(node * root) 
{ 
	if (root==NULL) 
		return; 

	// Standard level order traversal code 
	// using queue 
	queue<node *> q; // Create a queue 
	q.push(root); // Enqueue root 
	while (!q.empty()) 
	{ 
		int n = q.size(); 

		// If this node has children 
		while (n > 0) 
		{ 
			// Dequeue an item from queue and print it 
			node * p = q.front(); 
			q.pop(); 
			cout << p->key << " "; 

			// Enqueue all children of the dequeued item 
			for (int i=0; i<p->child.size(); i++) 
				q.push(p->child[i]); 
			n--; 
		} 

		cout << endl; // Print new line between two levels 
	} 
} 

int node::max_profit() const{
    int sum = this->key;
    for (auto &child : this->child)
        sum += child->max_profit();
    return std::max(-x, sum);
}
    
int main() 
{ 
    int t;
    cin >> t;
    while(t--){
    int n;
    cin >> n >> x;
    int a[n]; //array to store values of nodes
    for(int i = 0; i < n; i++) cin >> a[i];
    n-=1; //to get n-1 edges
    int i = 1, u, v; node *root = newNode(a[0]); 
    while(n--){
	cin >> u >> v; //edges
	if(u == 1)
	    (root->child).push_back(newNode(a[i])); 

	else
	(root->child[u-2]->child).push_back(newNode(a[i])); 
    i++;
    }
	cout << "Level order traversal\n"; 
	LevelOrderTraversal(root); 
	node np;
	cout << np.max_profit();
	
 }
	return 0; 
}