Educational Codeforces Round #105 Dogeforces - 并查集 + 构造

题意

有一家公司，出了最底层员工，每个员工至少有个2个下属，且其工资一定严格高于其下属。

现在给你$n$个底层员工。以及任意两个员工的最近的公共上司的工资。要你构造出这个公司的整体结构。

题解

直接对上司的工资排序。（可怕~）

也就是根据value进行排序。

static class Node {
    int x, y, value;
}

我们维护一个动态的并查集。一开始，只有$n$个员工在里面，这$n$个员工的父亲是空（注意，不是自己。）

因为工资是排过序的。所以按工资顺序，依次将node.x和node.y放到一个集合里是合理的。

如果$x$往上和$y$往上最大的boss的工资一样，且这个工资恰好等于node.value。那说明两个人本来就是一个boss。

如果两个中，只有一个boss的工资等于value。那么说明，另一个boss应该是这个boss的下属。

再如果，如果这两个boss的工资都小于value。那么说明这两个boss的直接上司的工资是node.value。于是我们在并查集里创建一个新的员工，且这个员工的工资是node.value，且这个员工是那两个boss的boss。

代码