典型例題

Acwing

權值

故名思義，在帶權并查集中，我們需要讓每個節點攜帶一個**“權值”**。
那么這個權值應該是什么呢？其實答案就在并查集當中。
由于在并查集當中我們可以在 $O(1)$ 時間內找到一個節點的根節點，那么我們可以讓這個權值表示為：某個節點到根節點的距離。

如何維護權值

首先我們需要一個“懶標記數組 $d$”，至于為什么稱其為“懶標記”，稍后再解釋。這個數組就是用來記錄我們權值的數組。
即，$d[i]$ 表示 $i$ 到根節點的距離。
其次，我們需要在 $find$ 函數中做一點手腳。這個也稍后解釋，

懶標記數組和find()

明明就是用來維護權值的數組，為什么我們要稱其為懶標記呢？
試想一下，當我們將以 $fb$ 為根的集合添加到以 $fa$ 為根的集合的尾部，我們是需要修改以 $fb$ 為根的子樹集合里面所有點的 $d[]$ 的，是不是想象就可怕呢？
好，現在我們試著正經分析一下，如果我們真的要一次性修改以 $fb$ 為根的子樹集合中的所有點，有什么辦法可以得到這些點嗎？
貪心的想，我們肯定希望直接找到集合中的所有點，然后修改，但這是不可能的！由于我們在并查集中只能找到根節點，而不能從根節點找孩子節點，所以我們只能遍歷所有點，判斷每一個點所在的集合是否為 $fb$，這么做的時間復雜度為 $O(N)$，如果執行 $N$ 次這樣的操作，就是平方級別的復雜度！這肯定無法接受！
但我們又無法回避這個問題，該如何做呢？ – 參考線段樹中懶標記的做法
當我們需要修改以 $fb$ 為根的集合中所有點的權值時，我們只修改該集合根節點 $fb$ 的權值，然后其余的點我們不做操作！
等我們對集合中的某個點 $x$（不是該集合的根節點） 執行 $find$ 操作時，$find$ 會找到 $x$ 的所有父節點，直到根節點。
我們發現，我們找到了一條從直接從底層節點到根節點的路徑，并且尋找這個路徑的過程是遞歸的（線性）！
既然遞歸的路徑是從底到根，那么回溯時的路徑必然是從根到底，而從根到底的過程就可以找到根的所孩子，這些孩子就是該根所在集合中的子樹節點！
這個時候（回溯），就可以用來修改我們的懶標記，將他們變成正確的值。
并且，從根到底的回溯也能保證答案的正確性，因為當某個節點的根被修改時，它所有的子節點也需要修改，子樹的值依賴于它的根的值，因此保證根的正確性，才能保證底的正確性。
例如，我們讓根節點指向一個新的根節點，那么不僅原來的根節點的 $d[]$ 變化了，它的所有子節點的 $d[]$ 也需要變化。
最后，還有一個疑問？如果你每次 $find(x)$ 都會修改 $x$ 到樹根的路徑上的 $d$，那么會不會導致一個點被重復多次修改，導致它的 $d[]$ 比實際更大呢？
答案是不會的，因為在第一次 $find(x)$ 之后，$x$ 會因為路徑壓縮，直接指向樹的根節點，這樣當下一次再 $find(x)$ 時，會直接返回 $pre[x]$，不會涉及到清除懶標記（修正它的 $d[]$）這一步。

圖解

順便解釋一下清除懶標記（修正 $d[]$）的公式：d[x] = d[x] + d[pre[x]]
具體含義：一個節點到根節點的距離 = 它到父節點的距離 + 父節點到根節點的距離
因此，在修正一個節點 $x$ 時，我們需要先修正它的父節點 $pre[x]$ 到樹根的 $d[pre[x]]$，這一點從公式也可以清晰的看出
這也就是我們在 $find(x)$ 中 int root = find(pre[x]); 做的事情，如果寫的更清楚一點，那就是：

int find(int x)
{if(pre[x] == x) return x;  // 原本的findfind(pre[x]);   // 1. 先修正所有祖先節點(父->根)s[x] = s[x] + s[pre[x]];    // 2. 修正自己return pre[x] = find(pre[x]);  // 原本的find
}

可以發現，不過是比原本的路徑壓縮 $find$ 多了兩條語句罷了！如果我們把最后一句return pre[x] = find(pre[x]); 再優化一下，那就是下面的形式，不過該優化對時間效率的提升很小，因為在我們執行 find(pre[x]) 之后，$pre[x]$ 便已經直接指向根節點 $root$，這樣當我們下次再執行 $find(pre[x])$ 時，由于已經路徑壓縮過了，實際查找速度是 $O(1)$ 的。

int find(int x)
{if(pre[x] == x) return x;int root = find(pre[x]);   // 1. 先修正所有祖先節點(父->根)s[x] = s[x] + s[pre[x]];    // 2. 修正自己return pre[x] = root;
}

代碼

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 30010;int pre[N];
int d[N], s[N];
// s[i] 表示 i 所在集合中點的個數
// d[i] 標識 i 到其集合中根節點的距離（帶有懶標記的權值數組int find(int x)
{// 當 pre[x] == x，即該節點就是集合的根節點時// 不存在歲回溯路徑，也就不需要也不能去除懶標記if(pre[x] == x) return x;// 存在回溯路徑，去除懶標記// 先遞歸，一直找到根節點int root = find(pre[x]);    // 從根節點開始往下回溯d[x] += d[pre[x]];  // d[x]_new = d[x]_old + d[pre[x]];，參考上面的圖 return pre[x] = root;   // 別忘了路徑壓縮
}void merge(int a, int b)
{int fa = find(a), fb = find(b);if(fa == fb)    return ;// 可以合并// 只修改a的根節點fapre[fa] = fb;d[fa] += s[fb];// 修改集合大小s[fb] += s[fa];
}int main()
{for(int i = 0; i < N; i ++ ){pre[i] = i;s[i] = 1;d[i] = 0;   // 初始狀態時，自己就是自己的根節點}int T;  cin >> T;while(T -- ){string op;  int a, b;cin >> op >> a >> b;if(op == "M")   merge(a, b);else    {int fa = find(a), fb = find(b);if(fa != fb)    cout << -1 << endl;// 注意a和b可能相等的情況else    cout << max(0, abs(d[a] - d[b]) - 1) << endl;}}return 0;
}

2024/3/11

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 30010;int pre[N], d[N], cnt[N];int find(int x)
{if(pre[x] == x) return x;int root = find(pre[x]);d[x] = d[x] + d[pre[x]];return pre[x] = root;
}int main()
{for(int i = 0; i < N; i ++ )    pre[i] = i, cnt[i] = 1;int q;  cin >> q;while(q -- ){string op;  int a, b;cin >> op >> a >> b;int fa = find(a), fb = find(b);if(op == "M"){if(fa != fb){pre[fa] = fb;d[fa] += cnt[fb];cnt[fb] += cnt[fa];}}else {if(fa != fb)    cout << -1 << endl;else {if(a == b)  cout << 0 << endl;else cout << abs(d[a] - d[b]) - 1 << endl;}}}return 0;
}