1const parent = [0,1,2,3,4], dist = [0,0,0,0,0];
2function find(x) {
3 if (parent[x] !== x) {
4 const p = parent[x];
5 const root = find(p);
6 dist[x] += dist[p]; // 累加到根的距离
7 parent[x] = root; // 路径压缩
8 }
9 return parent[x];
10}
11function union(a, b, w) { // 断言 d[a] - d[b] = w
12 const ra = find(a), rb = find(b);
13 if (ra === rb) return;
14 parent[ra] = rb;
15 dist[ra] = w + dist[b] - dist[a]; // 权值推导
16}
17function query(a, b) {
18 const ra = find(a), rb = find(b);
19 if (ra !== rb) return null; // 关系未知
20 return dist[a] - dist[b]; // d[a] - d[b]
21}