2069. 网络分析

题目描述

给出一个 $n$个孤立点的图，每个点上的权值都是 $0$，进行 $m$ 次操作
操作 1 ：把两个点所在的连通块合并起来
操作 2 ：向某个点所在的连通块的所有点累加一个值
$n\le 10^4,m\le 10^5,n\le 10^4,m\le 10^5$
最后输出每个点上的权值

解题思路

• 并查集 树上差分

我们通过并查集合并连通块，保证同一个连通块内的点同属一个集合
对于每一个合并操作，找到两个点所属的集合
如果这两个点不在同一连通块，那么我们构造一个新点，使这个新点成为集合合并后的根节点

这样进行 k 次有效合并操作后，就会产生 k 个新点
我们所构造的图是若干棵树，编号为 1−n 的节点都是树的叶子节点

对于每次连通块累加操作，我们只需要向集合的根节点累加一个值即可
最后对我们所构造出来的一堆树DP（只是遍历一下），把每个点的权值下放到子树中的所有节点中
然后依次输出编号为 1−n 的节点的权值即可

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 200010, M = N << 1;
int h[N], e[M], ne[M], idx;
void add(int a, int b)  // 添加一条边a->b
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}int n, m;int p[N];
int find(int x) {if (x != p[x]) {p[x] = find(p[x]);}return p[x];
}int f[N];
void dfs(int u, int fa) {for (int i = h[u]; ~i; i = ne[i]) {int j = e[i];f[j] += f[u];dfs(j, u);}
}int main()
{cin >> n >> m; memset(h, -1, sizeof h);for (int i = 0; i < N; i++) p[i] = i;int root = n + 1;int op, a, b;while (m -- ) {cin >> op >> a >> b;if (op == 1) {int fx = find(a), fy = find(b);if (fx != fy) {add(root, fx), add(root, fy);p[fx] = p[fy] = root;root++;}} else {int fx = find(a);f[fx] += b;}}for (int i = n + 1; i < root; i++) if (p[i] == i) dfs(i, 0);for (int i = 1; i <= n; i++) cout << f[i] << ' '; cout << endl; return 0;
}