(并查集) $O(n+m)$

C++ 代码

#include<iostream>
#include<vector>

using namespace std;
const int N=1e4+10;

//并查集的应用，时间复杂读O(n+m)
//f[N]为并查集，ans[N]为独立每个点存的数,f_num[N]为一个集合存的整体
//学过并查集应该知道，给一个集合加权，只需要加给祖宗节点即可
//最后算的时候只需个体的值+祖宗节点的值即可
int f[N],ans[N],f_num[N],n,m;

//son存每个集合的节点
vector<int> son[N];

//find函数
int find(int x){
    if(f[x]!=x)f[x]=find(f[x]);
    return f[x];
}
//两个集合合并
void merge(int x,int y){
    //我们将小集合合并到大集合，这样复杂度最小
    if(son[x].size()>son[y].size())swap(x,y);
    f[x]=y;

    //将小集合的节点加入大集合中，并且下放小集合祖宗节点的值
    //使得下放后小集合祖宗节点的值等价于大集合祖宗节点的值
    //比如大集合祖宗节点的值为2，小集合祖宗节点的值为1，我们只需
    //将小集合的节点值全部减1即可
    for(auto i:son[x]){
        son[y].push_back(i);
        ans[i]+=(f_num[x]-f_num[y]);
    }
    //清空小集合，保证空间不爆
    son[x].clear();

}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    //初始化
    for(int i=1;i<=n;i++)f[i]=i,son[i].push_back(i);

    while(m--){
        int p,x,y;
        cin>>p>>x>>y;
        if(p==1){
            //已经是在同一集合的跳过
            int fx=find(x),fy=find(y);
            if(fx==fy)continue;
            else merge(fx,fy);
        }
        else f_num[find(x)]+=y;
    }

    //输出答案
    for(int i=1;i<=n;i++)cout<<ans[i]+f_num[find(i)]<<' ';
    return 0;
}