以一道区间和查询来说明板子如何使用

1.merge的时候只需要维护两个根节点的距离，利用的是合并时题目给的信息
2.find的时候更新维护是子节点到根的距离
3.需要加一个查询函数，因为距离数组是开在结构体内部的。

题目描述

对于一个长度为 NN 的整数数列 A1,A2,⋯ANA_{1}, A_{2}, \cdots A_{N}，小蓝想知道下标 ll 到 rr 的部分和 ∑i=lrAi=Al+Al+1+⋯+Ar\sum\limits_{i=l}^{r}A_i=A_{l}+A_{l+1}+\cdots+A_{r} 是多少?

然而，小蓝并不知道数列中每个数的值是多少，他只知道它的 MM 个部分和的值。其中第 ii 个部分和是下标 lil_{i} 到 rir_{i} 的部分和 ∑j=liri=Ali+Ali+1+⋯+Ari\sum_{j=l_{i}}^{r_{i}}=A_{l_{i}}+A_{l_{i}+1}+\cdots+A_{r_{i}}, 值是 SiS_{i} 。

对于所有评测用例, 1≤N,M,Q≤105,−1012≤Si≤1012,1≤li≤ri≤N1 \leq N, M, Q \leq 10^{5},-10^{12} \leq S_{i} \leq 10^{12}, 1 \leq l_{i} \leq r_{i} \leq N, 1≤l≤r≤N1 \leq l \leq r \leq N 。数据保证没有矛盾。

蓝桥杯 2022 省赛 A 组 J 题。

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

#include <bits/stdc++.h>
using namespace std;
#define ll long long
# define int long long
#define ull unsigned long long
#define pii pair<int,int>

#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl  "\n"
#define debug1(x) cerr<<x<<" "
#define  debug2(x) cerr<<x<<endl
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
int n, m;
int a[N];
struct DSU {
  vector<int> f, siz,d;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
        d.resize(n);
        for(int i=0;i<n;i++)d[i]=0;
    }
    
   int find(int x)
{
    if (f[x] != x)
    {
        int root = find(f[x]);
        d[x] += d[f[x]];//f[x]到根距离已经被更新
        f[x] = root;//让x指向根
    }
    return f[x];
}
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int l, int r,int add) {
        int x = find(l);
        int y = find(r);
        if (x == y) {
            return false;
        }
   d[y]=d[l]+add-d[r];
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
  int  query(int u,int v){
    	int ans=d[v]-d[u];
    	return ans;
    }
};
void solve(){
	int q;
	cin>>n>>m>>q;
	DSU dsu(n+5);
	for(int i=1;i<=m;i++){
		int sum=0;
		int u,v;cin>>u>>v>>sum;
		u--;
		dsu.merge(u,v,sum);//根节点是最小值
	}
	for(int i=1;i<=q;i++){
		int u,v;cin>>u>>v;
		u--;
		if(dsu.same(u,v)){
		int ans=dsu.query(u,v);
		cout<<ans<<endl;
		}
		else {
			cout<<"UNKNOWN"<<endl;
		}
	}
}
signed main() {
    cin.tie(0);
    
    ios::sync_with_stdio(false);

    int t;
   //cin>>t;
     t=1;
    while (t--) {
solve();
    }
    return 0;
}