Educational Codeforces Round #105 Dogeforces - Disjoint set + Construction
Solution:
Sort the salary. So that sort the value for this structure:
static class Node {
int x, y, value;
}
We build a dynamic disjoint set. In the beginning, there only be $n$ lower-level employees. And the father of these employees is empty. (Note that, the father is not himself.)
Because salary is sorted. Therefore, it is ok to put node.x and node.y into a set in order of salary.
We get the root father of x and y. Let's call it boss_x and boss_y. If the salary of these two bosses is the same and their salary is equal to node.value. Then x and y already under the same boss.
Else if, only one of the salaries of bosses is equal value. Then we know, another boss should be the subordinates of these boss.
Else if again, if the salaries of boss is less than value. Then we know, we create a new boss. The salary of this new boss is node.value. And this new boss is the boss of boss_x and boss_y.