网络分析_(并查集，树上差分）

原题链接：2069. 网络分析 - AcWing题库

题意：一堆电脑，可以做两个操作，链接两个电脑或在一个电脑上发消息，发送的消息可以在有链接的电脑上传递，并且每台电脑记录发送消息的值，问经过多次操作后每台电脑记录的值是多少

思路

明显的并查集，

也不是那么明显，入手发现像是BFS或DFS，只要邻接就记录，每次加就每次遍历查找

但是时间复杂度很紧张，操作数多到要求每次操作的遍历要有优化

转变为 快速判断两个电脑有没有链接 链接两个电脑 与 每个集合电脑快速加权 的问题：

• 由此想出并查集才是正确的 要快速判断两个电脑是否是链接的，可以想到判断是否是一个集合，利用并查集优化查找时间

• 链接两个电脑 方法很多，但是要与加权一起考虑，如果是并查集的合并，那每次操作都可能要遍历一遍来加上权值，避免与之后的合并加权相互影响 但是时间复杂度就是 $10^9$

  要怎么样才可以不遍历每一台，或者不在每次操作都遍历每一台？

  将权值记录在根节点，并且每次合并往上扩展根节点，新合并进来的数，与旧合并进来的数在新的根节点上合并，这样可以用子树把合并的顺序区分开，如果将权值加在每次合并的根节点，就可以在最后下放权值求和来得到结果

实现

#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
//多加了一倍的节点，且两两可能组成一组，最坏情况每个新点都有两个分支
const int N = 20010, M = N << 1;
 
int p[N];
int f[N];
 
int h[N], e[M], ne[M], idx;
int root;
 
//并查集
int find(int a)
{
    if(p[a] != a)
        p[a] = find(p[a]);
        
    return p[a];
}
 
void add(int a, int b)
{
    e[idx] = b; ne[idx] = h[a]; h[a] = idx ++;
}
 
//节点记录其子节点加了多少
void dfs(int s, int fa)
{
    f[s] += f[fa];
    for(int i = h[s]; i != -1; i = ne[i])
    {
        int j = e[i];
        dfs(j, s);
    }
    
    return;
}
 
 
int main()
{
    int n, m;
    cin >> n >> m;
    root = n + 1;
    
    for(int i = 1; i <= 2 * n; i ++)
        p[i] = i;
    
    
    memset(h, -1, sizeof h);
    
    int a, b, d, t;
    for(int i = 0; i < m; i ++)
    {
        cin >> d;
        if(d == 1)
        {
            cin >> a >> b;
            a = find(a);
            b = find(b);
            //不是一个集合中，就创建新节点，用来表示两者连接了，同时用来分割当前合并的节点与之后可能合并的节点
            if(a != b)
            {
                p[a] = p[b] = root;
                add(root, a);
                add(root, b);
                
                root ++;
            }
        }
        else 
        {
            cin >> a >> t;
            
            int k = find(a);
            //根节点记录其当前子节点共同加数
            f[k] += t;
        }
    }
    
    //遍历根节点
    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;
}
 

在这样的实现中要注意，并查集与新节点的数量要统一，即对所有可能范围赋初值，作为判断创造新节点，合并之后，其与其他节点是否在同一集合的判断依据。

同时注意分析数据范围

树上差分

实际上dfs函数实现的是类似差分的操作，将每个点的权值分给根节点，通过累加（前缀和）来求每个点的真实权值。

并查集

用来查找是否属于一个节点，也可以用来合并集合。但是一旦当前的根节点改为其他根节点时，要对子树全部遍历一遍才可以全部更新根节点