使用等级组的不相交联合发现分析
不相交联合 - 找到压缩分析。使用等级组的不相交联合发现分析
我们将按照它们的等级划分节点。然后我们将队伍分成 等级组。在每次查找时，我们会将一些美国硬币存入一般小猫和一些加拿大硬币到 到特定的顶点。以 计算存入的加拿大硬币总数，我们将计算每个节点的存款数量 。通过累加 等级r中的每个节点的所有存款，我们将获得每个等级r的总存款。然后我们将g组中的每个等级r的所有存款加起来，从而获得每个等级组g的存款总额 。最后，我们将每个等级组g的所有存款加起来，以获得存放在森林中的加拿大硬币总数 。把这个数字加到美国猫币的数量上给我们答案。
如果v为根，或如果父：
对于每个顶点，V，从表示i到 根顶点的路径上，我们下的两个账户一个沉积一个便士的v是根，或者如果v的父亲处于与v不同的等级组中，则在该规则下向一个单位 收费。这将美国便士存入小猫。
否则将加拿大分钱存入顶点。
要获得所有加拿大存款很好的估计根据规则2，我们 将顶点，而不是通过查找指令加起来的存款。 如果按照规则2将硬币存入顶点v，则v将被移动 路径压缩并且获得比其父亲旧的 更高等级的新父亲。 （这是我们使用路径压缩完成的事实的地方）。因此，等级组g> 0中的顶点v可以在它的父亲之前移动最多 F（g）-F（g-1）次被排挤出列组 克，因为这是该级别组的大小。*发生这种情况后，到v所有 的费用都会按照规则去1.
我上面的文字问题是
- 作者如何得出结论：“排名组g> 0的顶点v最多可以移动F（g）-F（g-1）次”
谢谢！
在原来的，你所引用的部分的上方，它说， “行列的任何秩组g> 0的数量，因此，F（克） - F（克 - 1）”
的作者不会完全确定您查询的内容，并且节点确实可以移动任意次数。作者的结论是，一旦节点通过路径压缩被移动了F（g）-F（g-1）次，那么移动到的父节点不能与该节点处于同一个等级组中，因为每当一个节点被移动时，它就会得到一个更高级别的父节点。发生F（g） - F（g - 1）次后，其父母不能在同一等级组中。
这样做的意义在于，该节点的所有进一步路径压缩移动都在Rule（1）之下，存放美国便士，而不是加拿大便士。