并查集+标记数组

时间复杂度 o(n ^ 2)

因为最多进行n-1次有效合并

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef long long ll;
int p[N], sum[N], tag[N];
int n, m;
int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}
void add(int a, int b)
{
    tag[find(a)] += b;//加到父节点的tag中
}
void Union(int a, int b)//合并的时候考虑转移
{
    if(a == b) return;
    if(find(a) == find(b)) return;
    for(int i = 1; i <= n; i ++)
        if(find(i) == p[a] || p[i] == p[b])
        {
            sum[i] += tag[p[i]];
            //p[i] = p[b];
        }

    tag[p[a]] = tag[p[b]] = 0;//注意每次清空
    p[p[a]] = p[b];

}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) p[i] = i;
    while(m --)
    {
        int t, a, b;
        scanf("%d%d%d", &t, &a, &b);
        if(t == 1) Union(a, b);
        else add(a, b);
    }
    for(int i = 1; i <= n; i ++)
        sum[i] += tag[find(i)];//结算
    for(int i = 1; i <= n; i ++)
        if(i == n) printf("%d",sum[i]);
        else printf("%d ", sum[i]);
    return 0;
}