带权并查集

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
typedef long long LL;
int p[N];
LL d[N];
int find(int x)
{
    if(p[x]!=x)
    {
        int root = find(p[x]);
        d[x] += d[p[x]];
        p[x] = root;
    }
    return p[x];
}
void Union(int a,int b,LL s) // 从a连一条指向b的边
{
    int fa = find(a), fb = find(b);
    if(fa==fb) return;
    p[fa] = fb;
    d[fa] = d[b] + s - d[a];
}
int n,m,q;
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> m >> q;
    for(int i = 1 ; i <= n ; i ++) p[i] = i;
    while(m--)
    {
        int l,r;
        LL s;
        cin >> l >> r >> s;
        Union(l-1,r,s);
    }
    while (q--)
    {
        int l,r;
        cin >> l >> r;
        if(find(l-1)!=find(r)) cout << "UNKNOWN" << '\n';
        else cout << d[l-1]-d[r] << '\n';
    }
    return 0;
}