带权并查集

牛客小白月赛123F

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i128=__int128;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using db = double;
using ldb = long double;
#define F first
#define S second
#define debug(x) cerr<<#x<<":"<<x<<"\n";
#define int ll
const int N=5e5+10;
int s[N];
ll d[N];
void init(int n){
    for(int i=0;i<=n;i++){
        s[i]=i,d[i]=0;
    }
}
ll find(int x){
    if(x!=s[x]){
        int t=s[x];
        s[x]=find(s[x]);
        d[x]+=d[t];
    }
    return s[x];
}
bool merge(int x,int y,ll k){
    int rtx=find(x),rty=find(y);
    if(rtx==rty){
        if(d[x]-d[y]!=k){
            return false;
        }
    }else{
        s[rtx]=rty;
        d[rtx]=d[y]-d[x]+k;
    }
    return true;
}
void solve(){
    int n,q;cin>>n>>q;
    init(n);
    while(q--){
        int op;cin>>op;
        if(op==1){
            int u,v;cin>>u>>v;
            ll k;cin>>k;
            if(!merge(u,v,k)){
                cout<<"CONTRADICTION\n";
                continue;
            }
            cout<<"OK\n";
        }else if(op==2){
            int u;cin>>u;
            ll k;cin>>k;
            if(!merge(u,0,k)){
                cout<<"CONTRADICTION\n";
                continue;
            }
            cout<<"OK\n";
        }else{
            int u,v;cin>>u>>v;
            int rtu=find(u),rtv=find(v);
            if(rtu!=rtv){
                cout<<"UNKNOWN\n";
                continue;
            }
            ll ans=d[u]-d[v];
            cout<<ans<<"\n";
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int t=1;
    cin>>t;
    while(t--) solve();
    return 0;
}