文章目录

1. 题目描述

1.1. Limit

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

1.2. Problem Description

我们建造了一个大项目！这个项目有 n n n 个节点，用很多边连接起来，并且这个项目是连通的！
两个节点间可能有多条边，不过一条边的两端必然是不同的节点。
每个节点都有一个能量值。

现在我们要编写一个项目管理软件，这个软件呢有两个操作：

  1. 给某个项目的能量值加上一个特定值。
  2. 询问跟一个项目相邻的项目的能量值之和。（如果有多条边就算多次，比如 a a a 和 b b b有 2 2 2 条边，那么询问 a a a 的时候 b b b 的权值算 2 2 2 次）。

1.3. Input

第一行一个整数 T ( 1 < = T < = 3 ) T(1 <= T <= 3) T(1<=T<=3),表示测试数据的个数。
然后对于每个测试数据，第一行有两个整数 n ( 1 < = n < = 100000 ) n(1 <= n <= 100000) n(1<=n<=100000) 和 m ( 1 < = m < = n + 10 ) m(1 <= m <= n + 10) m(1<=m<=n+10)，分别表示点数和边数。

然后 m m m 行，每行两个数 a a a 和 b b b，表示 a a a 和 b b b 之间有一条边。

然后一个整数 Q Q Q。

然后 Q Q Q 行，每行第一个数 c m d cmd cmd 表示操作类型。如果 c m d cmd cmd 为 0 0 0，那么接下来两个数 u <mtext>   </mtext> v u\ v u v表示给项目 u u u 的能量值加上 v ( 0 < = v < = 100 ) v(0 <= v <= 100) v(0<=v<=100)。
如果 c m d cmd cmd 为 1 1 1，那么接下来一个数 u u u 表示询问 u u u 相邻的项目的能量值之和。

所有点从 1 1 1 到 n n n 标号。

1.4. Output

对每个询问，输出一行表示答案。

1.5. Sample Input

1
3 2
1 2
1 3
6
0 1 15
0 3 4
1 1
1 3
0 2 33
1 2

1.6. Sample Output

4
15
15

1.7. Source

BestCoder Round #1

2. 解读

看到题目中的节点和连边，我们很自然地会想到用图去存储，但是
节点最大数量是 10万，要存一个10万x10万的二维数组非常容易爆内存。而从题目中我们可以发现，这个图的连边是比较稀疏的，所以我们可以采用邻接表的方式进行存储。

用邻接表存储了点和连边的关系之后，我们再用一个数组去存储每一个节点的相邻节点能量之和。在某一个节点能量增加之后，增加所有与其相邻的节点的能量，有查询请求时直接输出即可。

我查了网上的一些其他解读，据说这里用到了一种算法叫做分块算法，感兴趣的同学可以了解一下。

3. 代码

#define mill 100010
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
int main()
{
    // test case
    int t;
    scanf("%d", &t);
    // Buffer
    long long list[mill];
    // 声明邻接表
    vector<int> vec_list[mill];
    for (int j = 0; j < t; j++) {
        // 清空邻接表
        memset(vec_list, 0, sizeof(vec_list));
        // 清空Buffer
        memset(list, 0, sizeof(list));
        // 读数据
        int n, m;
        scanf("%d %d", &n, &m);
        // 连边
        int a, b;
        // 循环m次，读入连边
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &a, &b);
            // ---存入ab-----------
            vec_list[a].push_back(b);
            // ---存入ba-----------
            vec_list[b].push_back(a);
        }
        // 读取query
        // query个数
        int q;
        scanf("%d", &q);
        // query 类型
        int qType;
        // query内容
        int u, v;
        // 读入query
        for (int i = 0; i < q; i++) {
            scanf("%d", &qType);
            if (qType == 0) {
                scanf("%d %d", &u, &v);
                // 操作query 0
                // 读连边
                vector<int> vec = vec_list[u];
                // 为每个与u相连的点加v能量
                for (unsigned long k = 0; k < vec.size(); k++) {
                    list[vec[k]] += v;
                }
            } else {
                scanf("%d", &u);
                // 操作query 1
                printf("%lld\n", list[u]);
            }
        }
    }
}