1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
using namespace std;
const int MAX_N = 100010;
int parents[MAX_N];
int weights[MAX_N];
int query(int x)
{
    int px = parents[x];
    if (px != x)
    {
        parents[x] = query(px);
        weights[x] += weights[px];
    }
    return parents[x];
}
void join(int a, int b, int w)
{
    // 合并两个集合
    int ga = query(a);
    int gb = query(b);
    if (ga == gb)
        return ;
    parents[ga] = gb;
    weights[ga] = w + weights[b] - weights[a];
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX