[数据结构与算法]acwing 2069. 网络分析（蓝桥杯）（并查集+树上差分）

题目：2069. 网络分析

思路：大佬思路，参考了大佬的解题思路。
使用并查集对节点进行分组

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N=1e5+10;
int n,m;
int p[20010],f[20010];
vector<int >g[20010];
int find(int u){
    if(p[u]!=u) p[u]=find(p[u]);
    return p[u];
}
void dfs(int u,int fa){
    f[u]+=f[fa];
    for(int i=0;i<g[u].size();i++){
        if(p[g[u][i]]!=g[u][i])
            dfs(g[u][i],u);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<=20005;i++){
        p[i]=i;
    }
    int root=10001;
    while(m--){
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        if(op==1){
            int xx=find(x),yy=find(y);
            if(xx!=yy){
                p[xx]=root;
                p[yy]=root;
                g[root].push_back(xx);
                g[root++].push_back(yy);

            }
        }else{
            int t=find(x);
            f[t]+=y;
        }
    }
    for(int i=10001;i<root;i++){
        if(p[i]==i) dfs(i,0);
    }
    for(int i=1;i<=n;i++){
        printf("%d ",f[i]);
    }
    return 0;
}