带权并查集

引入

并查集实际上是由若干棵树构成的森林,每棵树的根节点就是这棵树的所有满足
某一性质的代表元素!!!例如在求连通块的中点的数量的时候我们其实就是用这个根节点来维护。
我们可以在树中的每条边记录一个权值,即维护一个数组d,用d[x]保存节点x到父节点p[x]之
间边权,在每次路径压缩后,每个访问过的节点都会直接指向树根,如果我们同时更新这些节点
的d值,就可以利用路径压缩来统计每个节点到树根节点之间的信息,这就是所谓的带边权并查集.

一些例子

银河英雄传说那种找两个船之间有多少艘船!!!
还有就是接下来的题了

题目描述 来源

暂时先写到这qwq