题目描述
解题思路
并查集 树上差分
我们通过并查集合并连通块，保证同一个连通块内的点同属一个集合
对于每一个合并操作，找到两个点所属的集合
如果这两个点不在同一连通块，那么我们构造一个新点，使这个新点成为集合合并后的根节点
这样进行 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; }
