合并建立新节点

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n,m;
int p[N],d[N];

int find(int x){
    if(p[x] != x){
        if(p[p[x]] == p[x]) return p[x];
        int r = find(p[x]);
        d[x] += d[p[x]];
        p[x] = r;
    }
    return p[x];
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 0;i < N;++i)    p[i] = i;
    int k = n;
    while(m--){
        int t,a,b;
        scanf("%d%d%d",&t,&a,&b);
        if(t == 1){
            a = find(a),b = find(b);
            if(a != b){
                k++;
                p[a] = p[b] = k;
            }
        }else{
            a = find(a);
            d[a] += b;
        }
    }
    for(int i = 1;i <= n;++i){
        if(i == find(i))    printf("%d ",d[i]);
        else    printf("%d ",d[i] + d[find(i)]);
    }
    puts("");
    return 0;
}

合并不建立新节点

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n,m;
int p[N],d[N];

int find(int x){
    if(p[x] != x){
        if(p[p[x]] == p[x]) return p[x];
        int r = find(p[x]);
        d[x] += d[p[x]];
        p[x] = r;
    }
    return p[x];
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 0;i < N;++i)    p[i] = i;
    while(m--){
        int t,a,b;
        scanf("%d%d%d",&t,&a,&b);
        if(t == 1){
            a = find(a),b = find(b);
            if(a != b){
                d[a] -= d[b];
                p[a] = b;
            }
        }else{
            a = find(a);
            d[a] += b;
        }
    }
    for(int i = 1;i <= n;++i){
        if(i == find(i))    printf("%d ",d[i]);
        else    printf("%d ",d[i] + d[find(i)]);
    }
    puts("");
    return 0;
}