b_lq_网络分析（读题+换公共根带权并查集）

在某个节点发送一条信息，信息会发送到每个相邻的节点，之后这些节点又会转发到自己相邻的节点，直到所有直接或间接相邻的节点都收到了信息。
所有发送和接收的节点都会将信息存储下来。一条信息只存储一次。
给出小明连接和测试的过程，请计算出每个节点存储信息的大小。

思路
这题要跟着输入数据一步一步模拟才不容易出错，就是你不能连完边再跑逻辑；正解是并查集
先让一个附加的公共根统率一堆连通块的结点，初始情况下发送数据包时只让这个公共根存储，最后树形遍历的时候，就让公共根发送自己存储的数据包给子节点存储

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int> g[N];
int fa[N], dp[N];
int find(int u) {
    return fa[u]==u ? u : fa[u]=find(fa[u]);
}
void dfs(int u, int fa) {
    dp[u]+=dp[fa];
    for (int v : g[u]) if (v!=fa) {
        dfs(v, u);
    }
}
int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,m; cin>>n>>m;
    for (int i=1; i<N; i++) fa[i]=i;
    int root=n+1;
    for (int i=0; i<m; i++) {
        int op,u,v; cin>>op>>u>>v;
        if (op==1) {
            int fu=find(u), fv=find(v);
            if (fu!=fv) {
                fa[fu]=fa[fv]=root;
                g[root].push_back(fv);
                g[root++].push_back(fu);
            }
        } else {
            dp[find(u)]+=v;
        }
    }
    for (int i=n+1; i<root; i++) if (fa[i]==i) dfs(i,0);
    for (int i=1; i<=n; i++) cout<<dp[i]<<‘ ‘;
    return 0;
}

b_lq_网络分析（读题+换公共根带权并查集）

原文：https://www.cnblogs.com/wdt1/p/13779661.html