Tree problem

[theanswer]

Hey guys how would you solve this problem.

Lets say we have a tree structure:

A
/ \
B C
|
D


The tree shows company hierarchy A is the boss and B and C are his employees. B is the boss of D.
If I want to distribute 2000$ between all of them I must follow this rules:

-Each employee has the k-times higher salary than the sum of salaries of his directly subordinate staff.
-All employees that have the same superiors among themselves have the same wages.

For example above that means B and C will have the same salary which will be k-times bigger than what D has. A will have k-times bigger salary than B and C together.

Easier example: (budget is 2000$ and k is 2)

A
/ \
B C

Since A is superior to both B and C, they will have the same salary. So:

B = 333,...$;
C = 333,...$;
A = k*(333$ + 333$) = 2*(666) = 1332

A+B+C = 1998 (because I didn't count decimal numbers)

How would you solve this problem. I need some ideas.

[dhayden]

You need to do a little arithmetic and figure the salary of the subordinates based on the salary of the superior. If P is the salary of the parent node and it has N children making C then:
P = K*N*C
so
C = P/(K*N);

Now if you know a worker's salary, you can set the salaries of all the subordinates recursively:

double Worker::setSubordinateSalary()
{
    double total = this->salary;
    double subSalary = this->salary / (multiple* number_of_subordinates);
    for each subordinate {
        subordinate->salary = subSalary;
        total += subordinate->setSubordinateSalary();
    }
    return total;
}

This function returns the total salary of the worker and everyone working under him/her.

That's all well and good, but how do you distribute the budget?? The trick here is to call this function twice. The first time you assume the president (the top worker) makes $1. The function will distribute this and return the total salary of all workers. You can use the total to recompute the president's salary and distribute it again:

void distributeBudget(double amount)
{
    president->salary = 1.0;
    double total = president->setSubordinateSalary();

    // total now represents the total salary in units of the president's salary.
    // In other words, if total = 15.3 then that means the total salary
    // of all workers is 15.3 times the president's salary.
    // reset the president's salary based on this and distribute it:
    president->salary = amount / total;
    total = president->setSubordinateSalary();

    // Now the total should be equal to the budget (except for rounding errors)
    cout << "budget is " << amount << ". Actual is " << total << '\n';
}

[theanswer]

Thank you. I was doing something different by going bottom->up but your solution is better.

[theanswer]

How would you find the size of longest path in tree?

If you have:

A
/ \
B C
|
D

The size of longest path would be: 4 (D->B->A->C)

I was thinking that the longest bath is between nodes that have the biggest height. (how deep in the tree they are)

D has height: 2
B and C both have height: 1

so I must check which distance is bigger: D->B or D->C the solution is D->C

What do you think. Will this work for all the examples?

[dhayden]

How would you find the size of longest path in tree?

This is a different question from your first one right? You shouldn't need the longest path to do the original problem.

The trick to doing algorithms in a tree structure is to think recursively. In this case, the longest path of a tree is the max of:
- the longest path of a subtree
- the sum of the two deepest subtrees, plus 1

The second case is for a new longest path that goes through the root of the subtree.