The maximum happiness of the party

1、 subject

Employee information is defined as follows ：

class Employee {
    
	public int happy; // The happiness that this employee can bring 
	List<Employee> subordinates; // Which direct subordinates does this employee have 
};

Every employee of the company meets Employee Class description , The personnel structure of the whole company can be regarded as a standard 、 A multitree without rings . The root node of the tree is the only boss of the company . Every employee except the boss has a unique direct superior . Leaf nodes are grassroots employees without any subordinates （subordinates The list is empty. ）, In addition to grass-roots employees , Each employee has one or more direct subordinates .

The company is going to do party, You can decide which employees come to , Which employees don't come , The rules ：

1. If an employee comes , Then all the direct subordinates of this employee can't come ;
2. The overall happiness of the queue is the accumulation of the happiness of all employees present ;
3. Your goal is to maximize the overall happiness of the queue .

Given the root node of a multitree boss, Please return the maximum happiness of the queue .

2、 analysis

Recursive routines using binary trees ：
① The goal is ： With X Get the maximum for the whole tree with roots happy value
② possibility ：
  1）X What happened here ： hypothesis X Your direct subordinate is a,b,c, So happy value = X.happy + a No way max + b No way max + c No way max;
  2）X The situation of not coming ： Happiness value = 0 + max{a Come on ,a Not coming } + max{b Come on ,b Not coming } + max{c Come on ,c Not coming }

You can get , The information that needs to be obtained from the left and right subtrees is ：① The largest node does not come happy value ;② The largest number of nodes happy value .

3、 Realization

C++ edition

/************************************************************************* > File Name: 042. The greatest pleasure of the party .cpp > Author: Maureen > Mail: [email protected] > Created Time:  Two  7/ 5 14:59:05 2022 ************************************************************************/

#include <iostream>
#include <vector>
#include <ctime>
using namespace std;


class Employee {
    
public:
    int happy;
    vector<Employee*> subordinates;

    Employee(int h) : happy(h) {
      }
};

// The current node is called cur
// Parameters up Express cur Whether your superior will come 
// The meaning of function ：
// up by true,  Express cur The superior of determines the situation of coming ,cur  The whole tree can provide the largest happy value 
// up by false, Express cur Your superiors are not sure about the situation ,cur  The whole tree can provide the largest happy value 
int process1(Employee *cur, bool up) {
    
    if (up) {
    
        int ans = 0;
        for (Employee *next : cur->subordinates) {
    
            ans += process1(next, false);
        }
        return ans;
    } else {
    
        int p1 = cur->happy;
        int p2 = 0;
        for (Employee *next : cur->subordinates) {
    
            p1 += process1(next, true);
            p2 += process1(next, false);
        }
        return max(p1, p2);
    }
}

int maxHappy1(Employee *boss) {
    
    if (boss == nullptr) 
        return 0;

    return process1(boss, false);
}

// Method 2 ：
class Info {
    
public:
    int no; // The root node does not come to the largest happy value 
    int yes; // The root node is the largest happy value 

    Info (int n, int y) : no(n), yes(y) {
    }
};

Info *process(Employee *x) {
    
    if (x == nullptr) {
    
        return new Info(0, 0);
    }

    int no = 0;
    int yes = x->happy;

    for (Employee *next : x->subordinates) {
    
        Info *nextInfo = process(next);
        //x When you don't come , Children can come or not 
        no += max(nextInfo->no, nextInfo->yes);
        //x when , Children cannot come 
        yes += nextInfo->no;
    }

    return new Info(no, yes);
}

int maxHappy2(Employee *boss) {
    
    Info *allInfo = process(boss);
    return max(allInfo->no, allInfo->yes);
}

//for test 

void generateNexts(Employee *e, int level, int maxLevel, int maxNexts, int maxHappy) {
    
    if (level > maxLevel) return ;

    int nextsSize = rand() % (maxNexts + 1);

    for (int i = 0; i < nextsSize; i++) {
    
        Employee *next = new Employee(rand() % (maxHappy + 1));
        e->subordinates.push_back(next);
        generateNexts(next, level + 1, maxLevel, maxNexts, maxHappy);
    }
}

Employee *generateBoss(int maxLevel, int maxNexts, int maxHappy) {
    
    if ((rand() % 100 / (double)101) < 0.02) return nullptr;

    Employee *boss = new Employee(rand() % (maxHappy + 1));
    generateNexts(boss, 1, maxLevel, maxNexts, maxHappy);
    return boss;
}


int main() {
    
    srand(time(0));
    int maxLevel = 4;
    int maxNexts = 7;
    int maxHappy = 100;
    int testTimes = 100000;
    for (int i = 0; i < testTimes + 1; i++) {
    
        Employee *boss = generateBoss(maxLevel, maxNexts, maxHappy);
        if (maxHappy1(boss) != maxHappy2(boss)) {
    
            cout << "Failed!" << endl;
            return 0;
        } 

        if (i && i % 1000 == 0) cout << i << " cases passed!" << endl;
    }

    cout << "Success！" << endl;
    return 0;
}

Java edition

import java.util.ArrayList;
import java.util.List;

public class MaxHappy {
    
    public static class Employee {
    
		public int happy;
		public List<Employee> nexts;

		public Employee(int h) {
    
			happy = h;
			nexts = new ArrayList<>();
		}

	}


    // Method 1 ：
    public static int maxHappy1(Employee boss) {
    
		if (boss == null) {
    
			return 0;
		}
		return process1(boss, false);
	}

    //  The current node is called cur,
	// up Express cur Whether your superior will come ,
	//  This function means ：
	//  If up by true, It means that cur The superior has decided to come , Under the circumstances ,cur What is the maximum happiness value that the whole tree can provide ？
	//  If up by false, It means that cur The superior has decided not to come , Under the circumstances ,cur What is the maximum happiness value that the whole tree can provide ？
	public static int process1(Employee cur, boolean up) {
    
		if (up) {
     //  If cur If your superior comes ,cur No choice , Can only not come 
			int ans = 0;
			for (Employee next : cur.nexts) {
    
				ans += process1(next, false);
			}
			return ans;
		} else {
     //  If cur If your superior doesn't come ,cur You can choose , You can come or not 
			int p1 = cur.happy;
			int p2 = 0;
			for (Employee next : cur.nexts) {
    
				p1 += process1(next, true);
				p2 += process1(next, false);
			}
			return Math.max(p1, p2);
		}
	}

    // Method 2 ：
    public static int maxHappy2(Employee head) {
    
		Info allInfo = process(head);
		return Math.max(allInfo.no, allInfo.yes); // The biggest benefit from the biggest boss , The biggest benefit of not coming to the biggest boss 
	}

    public static class Info {
    
        public int no; // The maximum when the root node does not come happy value 
        public int yes;// The maximum when the root node comes happy value 

        public Info(int n, int y) {
    
            no = n;
            yes = y;
        }
    }

    public static Info process(Employee x) {
    
        if (x == null) {
    
            return new Info(0, 0); // Happiness value is 0
        }

        int no = 0;
        int yes = x.happy;

        for (Employee next : x.nexts) {
    
            Info nextInfo = process(next);
            no += Math.max(nextInfo.no, nextInfo.yes); //x When you don't come , Children can come , Or not , Find the maximum of both 
            yes += nextInfo.no;// Children cannot come 
        }

        return new Info(no, yes);
    }

    // for test
	public static Employee genarateBoss(int maxLevel, int maxNexts, int maxHappy) {
    
		if (Math.random() < 0.02) {
    
			return null;
		}
		Employee boss = new Employee((int) (Math.random() * (maxHappy + 1)));
		genarateNexts(boss, 1, maxLevel, maxNexts, maxHappy);
		return boss;
	}

	// for test
	public static void genarateNexts(Employee e, int level, int maxLevel, int maxNexts, int maxHappy) {
    
		if (level > maxLevel) {
    
			return;
		}
		int nextsSize = (int) (Math.random() * (maxNexts + 1));
		for (int i = 0; i < nextsSize; i++) {
    
			Employee next = new Employee((int) (Math.random() * (maxHappy + 1)));
			e.nexts.add(next);
			genarateNexts(next, level + 1, maxLevel, maxNexts, maxHappy);
		}
	}

	public static void main(String[] args) {
    
		int maxLevel = 4;
		int maxNexts = 7;
		int maxHappy = 100;
		int testTimes = 100000;
		for (int i = 0; i < testTimes; i++) {
    
			Employee boss = genarateBoss(maxLevel, maxNexts, maxHappy);
			if (maxHappy1(boss) != maxHappy2(boss)) {
    
				System.out.println("Oops!");
			}
		}
		System.out.println("finish!");
	}   
}